Tree 운행 법. [inorder, preorder, postorder] 개념 및 그림설명.

트리의 운행법
inorder, preorder, postorder
inorder, preorder, postorder
inorder, preorder, postorder

트리의 운행 법. (inorder, preorder, postorder)
left, center, right 이런식으로 하기도 하지만, 그냥 한국식으로 편하게 ^^
1개의 트리를 기준으로 각각의 방법에 대한 읽는 순서 입니다.
 - Inorder     : 좌측, 가운데, 우측.
 - preorder   : 가운데, 좌측, 우측.
 - postorder : 좌측, 우측, 가운데.

요놈들이 기본입니다.
 

이해하기 쉽게 그림을 이용해서 설명을 하겠습니다.
우선 Inorder. 좌측, 가운데, 우측. 라고 했는데
막상 좌측(B)에 가서 보니까 또 있죠?

여기서 좌측은 1개를 의미 하는 것이 아니라 "트리"를 의미 합니다.

즉, 요놈 좌측에 있는 트리 전체를 이야기 하는 것이지요.

당연히 요놈은 우측 트리가 되겠죠?
그렇다면, 좌측, 가운데, 우측  으로 본다면.


아래 처럼 되는 것이지요.

          A     

순서는. [좌측트리] - A - [우측트리]

자. 좌측트리를 봅시다.

그럼 이놈이 트리니까 다시 좌측, 가운데, 우측 순으로 읽어야 하겠죠?

 

그러면, 요렇게 됩니다.

      좌측은 D, 가운데는 B, 우측은 트리 입니다.
그러면 운행 순서는 D -  B - (우측트리) 겠죠?
트리 부분은 간단하죠? 좌측(G), 가운데(E), 우측(H)
그러면 결과적으로 D - B - G - E - H 가 나옵니다.
요놈이 위의 [좌측트리] - A - [우측트리] 에서 [좌측트리] 자리에 들어가게 되죠.
[D - B - G - E - H ] - A - [우측트리]




자. 우측트리를 봅시다.

그럼 이놈이 트리니까 다시 좌측, 가운데, 우측 순으로 읽어야 하겠죠?

 

그러면, 요렇게 됩니다.

 

     C     없음    

운행 순서는 (좌측트리) - C - 없음 이 되겠죠?
없는 경우는 무시하시면 됩니다.



여기서 다시 좌측트리를 보면

좌측은 I, 가운데는 F, 우측은 트리 입니다.

운행 순서는 I - F - (우측트리) 겠죠?
트리 부분은 좌측(K), 가운데(J), 우측(L)
그래서 결과적으로 I - F - K - J - L 이 나오게 됩니다.

요놈이 위의 좌측트리에 들어가서.
(I - F - K - J - L) - C - (없음) 이 되고.
전체 트리에서 [우측트리]가 되는 것이죠

[D - B - G - E - H ] - A - [우측트리]
[D - B - G - E - H ] - A - [I - F - K - J - L - C]

이런 방식으로 아래와 같은 결과가 나오게 됩니다.

직접 해보시고 비교해 보시면 많은 도웁이 될겁니다 ^^

기본적으로 Tree에서 알아야 할 것으로
B, C, E 같은 것을 node,
연결 되어진 선을 degree

node 중에서 더 이상 아래로 뻗지 않는 degree가 없는
 D, G, H 등과 같은 node를 단말 노드라고 합니다.
 가장 마지막이라는 의미이죠.

그리고 A 처럼 가장 상위에 있는 노드를 root 라고 합니다.

그리고 트리에는 몇가지 종류가 있습니다.
이진트리(binary tree) : node가 최대 2개인 트리.
즉, 가운데를 중심으로 아래로 없거나, 1개 또는 2개로 이루어진 트리 입니다.

위의 그림이 이진트리겠죠?

 전이진트리(full binary tree) : 단말노드를 제외한 node가 전부 2개씩인 트리.
단말노드를 제외하고 가운데를 중심으로 아래로 정확히 2개인 트리 입니다.
위 그림에서 C 에 우측에 node가 있었다면 전이진트리가 됩니다.

즉, 밑으로 2개이거나 전혀 없다면(단말노드가 되므로) 전이진트리가 됩니다.


그리고 모두 정확하게 2개씩 node가 있는 트리를 포화이진트리(perfect binary tree) 라고 합니다.
사실... 요놈은 영어랑 한글이랑 잘 매치가 안되긴 합니다;

완전이진트리(complete binary tree)가 있는데
이놈이 사실 좀 애매한데... 다음에 시간을 내서 한번 추가적으로 쓰거나.
트리들을 모아서 그림으로 새로 작성을 하도록 할 예정입니다.



유용한 정보가 되셨다면 아래 손가락 버튼 한번 눌러주세요 ^-^