나무,이 진 트 리(완전 이 진 트 리,만 이 진 트 리)개념 도해

1.나무의 정의
나 무 는 n 개의 결점 의 유한 한 집합 이 고 하나의 결점 만 있 으 며 나머지 결점 은 m 개의 결점 의 자나무 로 나 눌 수 있다.

2.나무의 개념 
4.567917.결점 의 도:하나의 결점 이 자 나 무 를 가 진 개 수 를 도 라 고 한다.예 를 들 어 A 의 도 는 3 이 고 C 의 도 는 2 이 며 H 의 도 는 0 이다.도 0 의 결점 을 잎 노드(D,F,G,H)라 고 한다.나무의 도 는 나무의 모든 결점 의 최대 치 이 며,이 나무의 도 는 3 이다4.567917.나무 에서 결점 의 최대 층 차 는 나무의 깊이 나 높이 가 된다.이 나무의 깊이 는 4 입 니 다

부모 노드 A 의 자 결점 B,C,D;B,C,D 도 형제 노드 입 니 다

4.567917.나무의 집합 을 숲 이 라 고 한다.나무 와 숲 은 밀접 한 관 계 를 가진다.한 나무의 뿌리 결점 을 삭제 하면 원래 의 나 무 는 모두 나무 로 숲 을 구성한다.하나의 결점 으로 숲 에 연 결 된 모든 나무의 뿌리 결점 으로 나 무 를 구성한다 3.이 진 트 리 
        이 진 트 리 는 각 노드 마다 최대 두 개의 키 노드 를 가지 고 있 으 며 왼쪽 나무 와 오른쪽 나 무 는 순서 가 있어 서 임의로 뒤 바 꿀 수 없다.

  4.이 진 트 리 옮 겨 다 니 기
앞 순서 옮 겨 다 니 기(앞 뿌리 옮 겨 다 니 기):뿌리―왼쪽―오른쪽
중 서 옮 겨 다 니 기(중 근 옮 겨 다 니 기):좌―근―우
후 순 옮 겨 다 니 기(후 근 옮 겨 다 니 기):좌―우―근
전 서 와 중 서 를 알 고 후 서 를 구 하 는 문제,  이전 순서 ABDGCEFH    중앙 순서 DGBAECHF
해법:앞의 순서,중간 순서 에 따라 나무의 노드 그림 을 종합 적 으로 판단 한 다음 에 뒤의 순 서 를 써 서 옮 겨 다 니 기:DGBEHFCA
(앞 순서 와 중간 순서 의 서브 트 리 도 앞 순서 나 중간 순서 의 규칙 을 만족 시 킵 니 다)

이 진 트 리 깊이 우선 옮 겨 다 니 기(DFS)와 넓이 우선 옮 겨 다 니 기(BFS)
      DFS 깊이 우선 옮 겨 다 니 기:뿌리 노드 에서 출발 하여 왼쪽 나무 방향 을 따라 잎 노드 를 찾 을 때 까지 세로 로 옮 겨 다 닙 니 다.그 다음 에 앞의 노드 로 거 슬러 올 라 가 오른쪽 서브 트 리 노드 를 옮 겨 다 니 며 모든 도달 가능 한 노드 를 옮 겨 다 닐 때 까지 한다.데이터 구 조 를 이용 하여'스 택',부모 노드 가 스 택 에 들 어가 고 부모 노드 가 스 택 에서 나 오 며 먼저 오른쪽 노드 가 스 택 에 들 어간 다음 에 왼쪽 노드 가 스 택 에 들 어 갑 니 다.모든 노드 를 반복 합 니 다.
DFS:ABDGCEFH
     BFS 넓이 우선 옮 겨 다 니 기:뿌리 노드 에서 출발 하여 가로로 이 진 트 리 세그먼트 노드 를 옮 겨 다 니 는 토대 에서 세로 로 이 진 트 리 의 층 차 를 옮 겨 다 닙 니 다.데이터 구조의'대기 열'을 이용 하여 부모 노드 가 대열 에 들 어가 고 부모 노드 가 대열 에 나 가 며 먼저 왼쪽 노드 가 대열 에 들 어간 다음 에 오른쪽 노드 가 대열 에 들어간다.모든 노드 를 반복 합 니 다.
BFS：ABCDGEFH 
5.이 진 트 리 가득 
높이 는 h 이 고 2^h-1 개 노드 로 구 성 된 이 진 트 리 를 만 이 진 트 리 라 고 합 니 다.
 
6.완전 이 진 트 리 
완전 이 진 트 리 는 만 이 진 트 리 에서 끌 어 낸 것 이다.이 진 트 리 의 깊이 를 h 로 설정 하면 h 층 을 제외 하고 다른 각 층(1～h-1)의 결 점 수 는 모두 최대 개수(즉 1~h-1 층 은 만 이 진 트 리)에 달 하고 h 층 의 모든 결 점 은 맨 왼쪽 에 연속 으로 집중 되 는데 이것 은 완전 이 진 트 리 이다.
무 더 기 는 일반적으로 완전 이 진 트 리 로 이 루어 진다.

총결산
이 글 은 여기까지 입 니 다.당신 에 게 도움 을 줄 수 있 기 를 바 랍 니 다.또한 당신 이 우리 의 더 많은 내용 에 관심 을 가 져 주 기 를 바 랍 니 다!