안 드 로 이 드 스 킬 트 리 - 트 리 기초 지식 소결 (1)

선언:
현재 안 드 로 이 드 면접 은 데이터 구조 에 대한 질문 도 점점 많아 지고 있 습 니 다. 다른 사람 이 보 내 는 면접 문 제 는 모두 무슨 붉 은 나무, 이 진 트 리 찾기 등 을 묻 는 것 도 자주 볼 수 있 습 니 다. 그래서 우 리 는 곧 여러 가지 어 려 운 면접 문 제 를 풀 지 는 않 지만 나무의 기초 지식 은 더 배 울 수 있 습 니 다.
최근 에 본 소개 그림 을 붙 입 니 다.
안 드 로 이 드 스 킬 북 시리즈:
안 드 로 이 드 기초 지식
안 드 로 이 드 스 킬 트 리 - 애니메이션 소결
안 드 로 이 드 스 킬 트 리 - 보기 소결
안 드 로 이 드 스 킬 트 리 - 액 티 비 티 소결
Android 스 킬 트 리 - 이벤트 시스템 소결 보기
Android 스 킬 트 리 - Android 저장 경로 및 IO 작업 소결
Android 스 킬 트 리 - 다 중 프로 세 스 관련 소결
Android 스 킬 트 리 - Drawable 소결
데이터 구조 기초 지식
Android 스 킬 트 리 - 배열, 링크, 해시 표 기본 소결
안 드 로 이 드 스 킬 트 리 - 트 리 기초 지식 소결 (1)
알고리즘 기초 지식
Android 스 킬 트 리 - 정렬 알고리즘 기초 소결
본 고 는 주로 나무 에 관 한 기초 지식 을 말한다.
나무 (Tree) 는 n (n > = 0) 개의 결점 의 유한 집합 이다.n = 0 시 를 빈 나무 라 고 합 니 다.빈 나무 가 아 닌 나무 중 하나: (1) 뿌리 (Root) 라 고 불 리 는 특정한 결점 만 있 습 니 다.(2) n > 1 시, 나머지 결점 은 m (m > O) 개의 서로 교차 하지 않 는 유한 집합 T1, T2,.....................................................
기초 지식
결점
위의 기초 지식 에 따라 나 는 전체적인 그림 을 그 렸 다.
트 리 구조 특성
아니면 자신 이 그린 그림 으로 설명 하 시 겠 습 니까?
기억 구조
안 드 로 이 드 스 킬 트 리 - 배열, 링크, 해시 표 기초 소결 에서 우 리 는 선형 저장 소, 체인 저장 소 를 소개 했다. 우리 의 나 무 는 두 가지 로 충분히 결합 하여 표시 할 수 있다.
우 리 는 위의 여러 가지 방식 으로 아래 의 이 나무의 저장 구 조 를 통일 적 으로 나타 낸다.
양친 표현법:
모든 노드 에 표시 기 를 설치 하여 부모 노드 가 배열 에 있 는 위 치 를 표시 합 니 다.
열 한 개의 결점 이 있 기 때문에 우리 의 index 는 0 - 10 이 고 index 위치 에 저 장 됩 니 다 (data + parent 의 index 값). 결 과 는 다음 그림 과 같 습 니 다.
여기 서 우 리 는 index 안의 parent 지침 에 따라 아버지의 결점 을 쉽게 알 수 있다 는 것 을 알 게 되 었 다. 그러나 예 를 들 어 나 는 E 결점 을 알 게 되 었 다. 그의 자 결점 이 몇 개 인지 알 고 싶 으 면 모 르 고 전체 구 조 를 통 해 옮 겨 다 닐 수 밖 에 없다.
물론 우 리 는 모양 을 바 꾸 어 지침 을 하나 더 추가 할 수 있다.
만약 에 우리 가 형제 결점 간 의 관계 에 관심 이 있다 면 오른쪽 형제 역 을 추가 하여 형제 관 계 를 나 타 낼 수 있다.
아이 링크 표시 법:
모든 결점 의 아이들 의 결점 을 배열 하여 하나의 사슬 표 로 저장 구 조 를 만 들 면 n 개의 결점 은 n 개의 아이들 의 체인 표 가 있 고 만약 에 잎 결점 이 라면 이 단일 사슬 표 는 비어 있다.그 다음 에 n 개의 머리핀 은 하나의 선형 표를 구성 하고 순서 저장 구 조 를 이용 하여 1 차원 배열 에 저장 합 니 다.
아이 표현법 으로 우리 위의 나 무 를 표시 하 는데 구 조 는 다음 과 같다.
그래서 우리 의 결점 구 조 는 두 가지 가 있다. 1. 표 두 배열 의 표 두 결점:

아이 체인 시계의 아이 결점:

하지만 이 는 어떤 결점 을 찾 는 아이 나 어떤 결점 을 찾 는 형 제 를 찾 는 데 도 편리 하지만, 어떤 결점 을 찾 는 양친 의 결점 을 찾 는 것 은 귀 찮 은 것 같다.그래서 우 리 는 위 에서 말 한 을 결합 할 수 있다.
양친
위의 두 가지 방법 을 결합 하면 된다.
아이 형제 표현 법:
어떤 나무 든 그 결점 의 첫 아이 가 존재 한다 면 유일한 것 이 고, 오른쪽 형제 가 존재 한다 면 유일한 것 이다.그래서 두 개의 지침 을 설정 하여 각각 이 결점 의 첫 아이 와 이 결점 의 오른쪽 형 제 를 가리킨다.
그래서 위 와 비슷 하 다. 다만 우 리 는 서로 다른 두 개의 지침 을 저장 했다.
우 리 는 위의 나 무 를 이런 방식 으로 실현 한다.
숲:
타 자 를 치지 않도록 그림 을 계속 그 려 서 설명 하 세 요. 헤헤:
분류 하 다.
나무 도 조건 에 따라 분류 되 어 있 으 니 알 아 보 자.
그 질서 있 는 나무 와 무질서 의 차 이 는 어디 에 있 습 니까?
나무 에 맺 힌 각 하위 나 무 를 왼쪽 에서 오른쪽으로 순서 가 있 고 바 꿀 수 없 으 면 질서 있 는 나무 가 됩 니 다. 그렇지 않 으 면 무질서 한 나무 입 니 다.
예 를 들 어 우 리 는 단순히 한 가족의 관 계 를 나 타 낼 뿐이다.
예 를 들 어 A 의 아이 가 B 와 C 가 있다 는 것 을 설명 할 뿐 이때 B 와 C 는 위치 가 바 뀌 어도 잎 이 괜 찮 고 이때 가 무질서 한 나무 이다.
그러나 우리 족보 가 나이 에 따라 순 위 를 매 긴 다 면 (장남, 차남) 이 럴 때 B 와 C 는 위 치 를 바 꿀 수 없다. 이 럴 때 는 질서 있 는 나무 다.
그러나 우리 가 흔히 말 하 는 나 무 는 질서 있 는 나 무 를 말 하 는데 질서 있 는 나 무 는 분류 가 많 고 비교적 많은 것 은 이 진 트 리 이다.
두 갈래 나무:
기본 형태:
이 진 트 리 성질:
사실 이것 은 우리 가 예전 에 수학 시간 에 외 워 야 했 던 수학 공식 과 비슷 하 다. 여러분 은 스스로 이 진 나 무 를 그린 다음 에 위의 공식 을 비교 해 보 세 요. 정확 한 지 아 닌 지.
두 갈래 나 무 를 옮 겨 다 니 기:
이 진 트 리 의 옮 겨 다 니 는 것 은 뿌리 노드 에서 출발 하여 특정한 순서에 따라 이 진 트 리 의 모든 노드 를 순서대로 방문 하여 모든 노드 가 순서대로 방문 되 고 한 번 만 방문 하 는 것 을 말한다.
이전 순서 옮 겨 다 니 기:
이 그림 만 봐 도 사실은 나 로 바 뀌 면 나 도 규칙 을 이해 할 수 없 지만 우 리 는 그 중의 규칙 만 알 면 된다.

   ：

  （     t）{
        if( t == null){
            return;
        }
        //   ，        ，            。
        print(t)
        //   ，                
          (t.   )
        //   ，                
          (t.   )
}

우 리 는 print 가 다른 방법의 앞 에 있 기 때문에 앞 순서 로 옮 겨 다 니 는 것 을 보 았 다.우 리 는 지금 뿌리 결점 을 이 방법 에 전달 한 후에 순서대로 인쇄 하고 재 귀 하면 바로 그림 의 순서 라 는 것 을 알 수 있 을 것 이다.
중간 순서 옮 겨 다 니 기:

   ：

  （     t）{
        if( t == null){
            return;
        }
        //   ，                
          (t.   )
        //   ，        ，            。
        print(t)       
        //   ，                
          (t.   )
}

우 리 는 우리 의 인쇄 문 구 를 중간 에 놓 으 면 중간 순서 가 옮 겨 다 니 는 것 을 발견 했다.
다음 순서 옮 겨 다 니 기:

   ：

  （     t）{
        if( t == null){
            return;
        }
        //   ，                
          (t.   )
        //   ，                
          (t.   )
        //   ，        ，            。
         print(t)       
}

우 리 는 우리 의 인쇄 문 구 를 마지막 에 놓 으 면 뒷 순서 가 옮 겨 다 니 는 것 을 발견 했다.
이 진 트 리 분류:
비스듬 한 나무:
완전 이 진 트 리 와 만 이 진 트 리:
한 그루 의 깊이 는 k 이 고 2 ^ (k + 1) - 1 개 노드 의 이 진 트 리 를 만 이 진 트 리 라 고 하 는데 이런 나무의 특징 은 각 층 의 노드 수가 최대 노드 수 라 는 것 이다.
한편, 이 진 트 리 에서 마지막 층 을 제외 하고 나머지 층 이 모두 꽉 차 있 고 마지막 층 이나 꽉 차 있 거나 오른쪽 에 몇 개의 노드 가 부족 하면 이 이 진 트 리 는 완전 이 진 트 리 이다.
두 갈래 로 된 나무
완전 이 진 트 리
밸 런 스 이 진 트 리:
이 지식 은 매우 많 으 니 후기 에 보충 해라.
정렬 이 진 트 리:
이 지식 은 매우 많 으 니 후기 에 보충 해라.
단서 이 진 트 리:
n 개의 결점 이 있 는 이 진 링크 에는 n + 1 (2n - (n - 1) = n + 1) 개의 공지 침 역 이 포함 되 어 있다.이 진 링크 의 빈 바늘 도 메 인 을 이용 하여 특정한 순서 에서 의 전구 와 후계 결점 을 가리 키 는 지침 을 저장 합 니 다.
여기 에는 반드시 하나의 지식 점 을 설명해 야 한다. 무엇이 선구자 와 후계 인가.
인터넷 상에 서 많은 사람들 이 이 해석 에 대해 너무 간단 해서 많은 사람들 이 잘못 을 이해한다. 예 를 들 어:
만약 에 우리 가 지금 이 두 갈래 나무 가 있다 고 가정 하면 나 는 지금 I 의 선구자 가 누구 인지, 후계 가 누구 인지 물 었 다. 많은 사람들 이 단순히 나무의 모양 을 보면 I 의 이전 결점 이 D 이기 때문에 앞 구 는 D 이 고 I 는 뒤의 자 결점 이 없 기 때문에 뒷구 는 비어 있다.이런 대답 은 잘못된 것 이다.우 리 는 안 드 로 이 드 스 킬 트 리 - 배열, 링크, 해시 표 기초 소결 문 에서 전구 와 후계 에 대해 언급 한 적 이 있다.
예 를 들 어 양 방향 링크 는 바로 전구 와 후계 가 있다.그러면 우 리 는 단순히 이 나 무 를 보면 알 수 없다. 우 리 는 먼저 나 무 를 특정한 방식 으로 옮 겨 다 닐 때 이런 링크 형식 으로 배열 한 다음 에 특정한 결점 의 전구 와 후계 가 무엇 인지 알 수 있다. 예 를 들 어 위의 그림 을 우 리 는 중간 순서 로 옮 겨 다 녀 야 한다. 우 리 는 얻 은 것 은 HDIBJEAFCG 이다. 이때 I 의 전 계 는 D 이 고 후 계 는 B 이다.
우 리 는 이 진 트 리 저장 구조 에서 두 개의 지침 이 그것 의 두 개의 자 결점 을 가리킨다.
그러나 한 개의 결점 만 있 거나 결점 이 없 을 수도 있다. 그러면 이 빈 지침 저장 소 는 낭비 된다. 우 리 는 이 지침 안에 이 결점 의 전구 나 후계 결점 의 지침 을 저장 할 수 있다.
그러나 이때 또 하나의 문 제 는 우리 가 이 점 이 현재 전구 의 지침 인지 왼쪽 결점 의 지침 인지 모 르 기 때문에 우 리 는 현재 이 위치 에 놓 인 지침 이 어느 것 인지 설명 하 는 매개 변수 가 필요 하 다 는 것 이다.

ltag 가 0 일 때 lchild 는 이 결점 의 왼쪽 아이의 지침 이 고 1 일 때 lchild 가 이 결점 의 선구자 라 는 것 을 설명 한다.

rtag 가 0 일 때 rchild 는 이 결점 의 오른쪽 아이의 지침 이 고 1 일 때 rchild 는 이 결점 의 후계 임 을 설명 한다.

메모리 구조:
이 진 트 리 순서 저장 구조:
우 리 는 이 진 트 리 를 이 진 트 리 로 보충 한 후에 해당 하 는 1 차원 배열 을 채 우 면 된다.
이 진 링크:
이 진 트 리 는 노드 마다 최대 두 명의 아이 가 있 기 때문에 데이터 필드 와 두 개의 지침 도 메 인 을 설계 합 니 다.
세 갈래 체인 테이블:
이 진 링크 를 개선 하고 부모 노드 의 안 내 를 증가 하면 노드 간 의 방문 을 더욱 잘 실현 할 수 있 습 니 다.
결어:
본문 은 결코 다 쓰 지 못 했 고, 내용 이 너무 많 으 니, 뒤에 다시 계속해서 보충 하 자.뭐 가 틀 렸 어 요? 지적 해 주세요...감사합니다.
참고:
《 큰소리 데이터 구 조 》.
《 위 키 피 디 아 》.