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

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

728x90

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/

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

728x90

반응형

from http://we1cometomeanings.tistory.com/178 by ccl(A) rewrite - 2021-11-04 15:26:50