트리 이론 기본편2 -이진 트리 용어 + 트리의 순회 -

1. 이진트리

 

모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리

 

모든 노드들이 자식 노드를 "최대" 2개까지만 가질 수 있는 트리

 

각 자식 노드를 왼쪽 자식 노드(left child node), 오른쪽 자식 노드(right child node)

 

 

이진 트리 예시 4가지..

 

모든 노드가 자식 노드를 "최대" 2개만 가지면 이진 트리가 된다

 

자식 노드가 아예 없어도 된다는 소리

 

 

2. 특징

 

레벨 i에서(높이 i에서) 노드의 최대 개수는 $2^{i}$개

 

높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 h+1개

 

최대 개수는 $2^{h+1}-1$개

 

 

3. 종류

 

 

이진트리의 종류에 따라 저장, 표현, 알고리즘 등이 달라질 수 있으므로 잘 구분해야한다

 

3-1) 포화 이진 트리(full binary tree)

 

모든 레벨에 노드가 포화 상태로 가득 찬 이진 트리

 

모든 노드의 자식 노드가 2개라는 소리

 

높이가 h이면 최대 노드의 수인 $2^{h+1}-1$개의 노드를 가지는 이진 트리

 

루트 1번에서 $2^{h+1}-1$번까지 정해진 위치에 대한 노드 번호를 가진다

 

노드의 번호를 매기는 방식이 주요 특징인데

 

루트를 1번으로 해서, 왼쪽부터 오른쪽 순서로 1,2,3,4,5,6,7,...., $2^{h+1}-1$번을 매긴다.

 

 

3-2) 완전 이진 트리(complete binary tree)

 

높이가 h이고 노드 수가 n개일 때, (단 n은 h+1이상이며 $2^{h+1}-1$개 미만이다)

 

포화 이진 트리의 노드 번호 1번부터 n번까지 빈 자리가 없는 이진 트리

 

번호를 매기는 방식이 포화이진트리처럼 루트 1번부터 왼쪽부터 오른쪽으로 1,2,3,..., $2^{h+1}-1$번을 매긴다.

 

그런데, 정점의 수가 n개일때, 1번부터 n번까지 중간에 빠지는 노드가 없어야 완전 이진트리

 

마지막 n+1~$2^{h+1}-1$까지가 정점이 없는 트리

 

쉽게 말하면

 

마지막 레벨을 제외한 윗 레벨은 모두 빈 자리가 없이 자식 노드가 2개씩 가득 차있고

 

n번은 왼쪽 자식 노드여야한다.

 

혹은 포화이진트리에서 $2^{h+1}-1$번에서부터 n+1번까지 단말 노드를 오른쪽에서부터 차례대로 제거한 트리를 말한다

 

 

 

왼쪽 포화이진트리에서 15,14,13,12,11을 차례대로 제거하여 만든 오른쪽 이진트리가 완전 이진트리

 

 

이렇게 오른쪽에 자식 노드가 달려버린 트리는 완전 이진트리가 아니라는 소리

 

3-3) 편향 이진 트리(skewed binary tree)

 

높이 h에 대한 최소 개수의 노드인 h+1개의 노드를 가지면서, 모든 노드가 한쪽 방향으로만 자식 노드를 가지는 트리

 

이미 일렬 배열이라 트리라고 부르기엔 효율이 많이 떨어짐

 

 

 

4. 트리의 순회(traversal)

 

순회(traversal)는 트리의 각 노드를 중복되지 않게 전부 방문하는 것

 

트리는 비선형구조라서 선형구조와 같이 선후 연결관계를 알 수 없어가지고 특별한 방법으로 순회해야함

 

3가지의 기본 순회 방법으로 전위순회, 중위순회, 후위순회가 있다.

 

 

4-1) 전위순회(preorder)

 

부모 노드를 방문하고, 왼쪽 자식노드 - 오른쪽 자식노드를 방문

 

4-2) 중위순회(inorder)

 

왼쪽 자식노드 - 부모노드 - 오른쪽 자식노드를 방문함

 

4-3) 후위순회(postorder)

 

왼쪽 자식노드 - 오른쪽 자식노드 - 부모 노드 순서로 방문함

 

 

5. 전위순회(preorder traversal)

 

 

5-1)수행방법

 

1) 현재 노드 n을 방문 처리

 

2) 현재 노드 n의 왼쪽 서브 트리로 이동

 

3) 현재 노드 n의 오른쪽 서브 트리로 이동

 

 

5-2) pseudo code

 

def preorder_traverse(T):

    if T:                       #T가 존재한다면,

        visit(T)               #print(T.item)같은, T에서 방문하면 할 행동

        preorder_traverse(T.left)                   #T의 왼쪽으로 이동

        preorder_traverse(T.right)                 #왼쪽 이동이 끝나고 오른쪽으로 이동

 

 

5-3) 예시 그림

 

A를 방문하고, B를 방문한다

 

근데 이제 B 다음에 C를 방문하는게 아니라

 

B가 B부터 시작하는 서브트리의 부모 노드라서.. B부터 시작해서 B의 왼쪽 자식, 오른쪽 자식을 먼저 방문해줌

 

그래서 A - B - D - E를 방문하고...

 

다시 E는 H,J의 부모노드라서 A-B-D-E-H-I를 방문하고..

 

이제 C로 이동한다

 

그래서 최종적으로 A-B-D-E-H-I-C-F-G

 

 

6. 중위순회(inorder traversal)

 

 

6-1) 방법

 

1) 현재 노드 n의 왼쪽 서브트리로 이동한다

 

2) 현재 노드 n을 방문 처리한다

 

3) 현재 노드 n의 오른쪽 서브트리로 이동한다

 

 

6-2) pseudo code

 

def inorder_traverse(T):

    if T:         #T가 존재한다면

        inorder_traverse(T.left)      #T의 왼쪽 서브트리로 이동

        visit(T)         #부모 노드 T를 방문해서 할 행동 print(T.item)

        inorder_traverse(T.right)     #T의 오른쪽 서브트리로 이동

 

 

 

6-3) 예시 그림

 

A부터 시작을 하는데... 왼쪽 자식 노드로 이동을 해야함..

 

B로 왔지만.. 다시 왼쪽 자식 노드로 계속 이동을 하고...

 

그러면 D에는 자식이 없으니까 D를 먼저 방문하고

 

올라가서 부모인 B를 방문하고

 

오른쪽 자식인 E로 내려가는데 E의 왼쪽 자식이 존재하니까

 

H를 먼저 방문하고, E로 올라와서 방문하고, I를 방문함

 

D-B-H-E-I를 방문하고.. 이제 A로 이동해서 방문처리하고

 

그 다음 A의 오른쪽 서브트리인 C로 이동하는데 C의 왼쪽 자식이 존재하니까

 

F를 방문하고, C로 올라와서 방문하고, G를 방문함

 

그래서 D-B-H-E-I-A-F-C-G

 

 

7. 후위순회(postorder traversal)

 

 

7-1) 방법

 

1) 현재 노드 n의 왼쪽 서브트리로 이동

 

2) 현재 노드 n의 오른쪽 서브트리로 이동

 

3) 현재 노드 n을 방문 처리

 

 

7-2) pseudo code

 

def postorder_traverse(T):

    if T:                            #T가 존재한다면..

        postorder_traverse(T.left)       #T의 왼쪽 서브트리로 이동

        postorder_traverse(T.right)     #T의 오른쪽 서브트리로 이동

        visit(T)     #T에 방문해서 해야할 행동, print(T.item)

 

 

7-3) 예시 그림

 

A에서 시작해서... 왼쪽 자식 노드로 계속 이동한다

 

B로 갔다가.. D로 갔다가.. D에는 자식이 없으니까 D부터 방문하고

 

다음에 오른쪽 서브트리인 E로 이동을 하는데... E에 자식이 있으니까 왼쪽 서브트리로 이동

 

그래서 H를 방문하고 오른쪽 I를 방문하고 E로 올라와서 E를 방문하고

 

마침내 B를 방문해서 D - H - I - E- B를 방문하고..

 

오른쪽 서브트리인 C로 이동을 하는데

 

C에 자식이 있으니 왼쪽 자식인 F를 방문하고 오른쪽 G를 방문하고 C로 올라와서 C를 방문한 다음에

 

A를 방문한다

 

최종적으로 D-H-I-E-B-F-G-C-A

 

 

 

8. 연습해보기

 

 

전위순회는? 부모를 먼저 방문하고 왼쪽 자식으로 내려가기

 

A - B - D - H - I -E - J - C - F - K - G - L - M

 

중위순회는? 왼쪽 자식노드를 먼저 방문하고, 부모 - 오른쪽으로 가기

 

H - D - I - B - J - E -A - F - K - C - L - G - M

 

후위순회는?? 왼쪽 자식노드를 먼저 방문하고, 오른쪽 - 부모로 가기

 

H - I - D - J - E - B - K - F - L - M - G - C - A