이진 탐색 순회 개념

이진탐색  순회 방법은 3가지가 있습니다 .

24

15                    28

2      19            27          30

root 처리 순서를 기준으로 이름을 정했습니다.

preorder(전위): Root 부터  왼쪽 모든 노드 탐색 후 오른쪽 ( root , left , right)  

전위 순회는 깊이 우선 순회(depth-first traversal)라고도 한다.

24 , 15 , 2 , 19 , 28 , 27 , 30 

inorder(중위): 맨 왼쪽 아래노드 부터 Root ,  오른쪽 (left , root , right)

중위 순회는 대칭 순회(symmetric traversal)라고도 한다.

2 , 15 , 19 , 24 , 27 , 28 , 30  

Postorder(후위): 맨 왼쪽 아래노드 부터 오른쪽 탐색 후 Root  (left , right , root) 

2 , 19 , 15 , 27 , 30 , 28 , 24 

완전 트리로 이해했다고 다 해한건 아니다. 불균형이진트리로 이해해야

진정한 이해한것입니다.

참조사이트

http://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C

레벨 순서 순회(level-order)는 모든 노드를 낮은 레벨부터 차례대로 순회한다. 레벨 순서 순회는 너비 우선 순회(breadth-first traversal)라고도 한다.

이진 탐색 트리에서

• 전위 순회: F, B, A, D, C, E, G, I, H (root, left, right)
• 중위 순회: A, B, C, D, E, F, G, H, I (left, root, right)
• 후위 순회: A, C, E, D, B, H, I, G, F (left, right, root)
• 레벨 순서 순회: F, B, G, A, D, I, C, E, H

             A

B                            C

D            E                  F            G

H            I                                J        K

Preorder(전위)

A B D H E I C F G J K 

Inorder(중위) 

H D B I E  A F C J G K 

Postorder(후위) 

H D I E B F J K G C A