[트리개념] Binary Tree와 순회방법

Binary Tree

 

: childeren의 개수가 2개로 제한.

 

full binary tree

각각의 노드가 child가 없거나 2개의 children 갖고 있는 경우 

 

Complete binary tree

왼쪽 위에서부터 가득 차있는거 (마지막 레벨이 왼쪽으로 정렬되어있고, 그 위는 가득 차있는것)

Perfect binary tree

모든 내부 노드들이 두개의 children 을 가지고 있고 모든 트리 구조가 같은 레벨에 있을 때  

트리 순회 방법

트리 순회는 전위,중위,후위 순회 방법이 있는데 아래 그림을 예시로 하나씩 설명해보겠다.

전위 순회

NLR

1 -> 2 -> 4->5 -> 3 -> 6 -> 7

 

중위 순회

LNR

 

4->2->5->1->6->3->7

후위 순회 

LRN

 

4->5->2->6->7->3->1

 

참고자료

 

 

https://yaboong.github.io/data-structures/2018/02/10/1_binary-tree-1/

Binary Tree 종류 - Heap 구현 사전지식

https://www.youtube.com/watch?v=bOZhvOc5xlQ&list=PLDV-cCQnUlIaTA41swrZwgH4mX7iPxLH4&index=2