[ 자료구조 ] 트리와 이진트리

트리의 기본적인 성질

- 노드가 N개인 트리는 항상 N-1개의 링크(link)를 가진다.
- 트리에서 루트에서 어떤 노드로 가는 경로는 유일하다.

- 또한 임의의 두 노드간의 경로도 유일하다. (같은 노드를 두 번 이상 방문하지 않는다는 조건하에).

이진 트리 (binary tree)란?

- 이진 트리는 여러 개의 자식 노드를 가질 수 있는 일반 트리와 다르게, 최대 2개의 자식만을 가질 수 있다.

- 즉, 0개, 1개, 2개의 자식 노드만 가질 수 있다.

- 각각의 자식 노드는 자신이 부모의 왼쪽 자식인지 오른쪽 자식인지가 지정된다. (자식이 한 명인 경우에도)

이진 트리 응용의 예

1) Expression Tree

 

2) 허프만 코드

각각의 알파벳에 부여된 이진 코드를 이런 트리의 형태로 표현할 수 있다.

 

 Full 이진 트리 VS Complete 이진 트리 

Full 이진 트리는 모든 레벨에서 노드들이 꽉 차있는 트리

Complete 이진 트리는 마지막 레벨을 제외한 레벨의 노드들이 모두 꽉 차있는 트리

 

Heap은 Complete 이진 트리이다.

높이가 h인 full Binary Tree는 2^h - 1개의 노드를 가진다.

노드가 N개인 Full or Complete 이진 트리의 높이는 O(longN)이다.

but, 노드가 N개인 일반 이진 트리의 높이는 최악의 경우에 N이 될 수 있다.

 

 이진 트리의 표현 

Complete 이진 트리의 경우 낮은 레벨의 왼쪽부터 차근차근 채워나가기 때문에 배열로 표현할 수 있다.

부모 노드의 배열 인덱스가 i일 때, 왼쪽 자식은 2 * i, 오른쪽 자식은 2 * i + 1로 표현 가능하다.



하지만 일반 이진 트리는 한 쪽으로만 편향된 모양이 나올 수 있어 규칙성이 성립하지 않기 때문에

연결 구조(Linked Structure)로 표현할 수 있다.

각 노드에 하나의 데이터 필드와 왼쪽 자식(left), 오른쪽 자식(right) 그리고 부모노드(p)의 주소를 저장한다.

(부모노드의 주소는 반드시 필요한 경우가 아니면 보통 생략 함)

 

 이진 트리의 순회 

순회 : 이진 트리의 모든 노드를 방문하는 일

트리는 연결 리스트나 배열처럼 선형 구조가 아니기 때문에, 순회할 때 더 다양한 방법이 있다.

 중순위(inorder) 순회 

이진 트리의 루트 노드를 R, 왼쪽 서브트리를 TL, 오른쪽 서브트리를 TR로 나누어 생각

① 먼저 TL을 inorder 순회하고

② R을 순회하고

③ TR을 순회한다.

 

INORDER-TREE-WALK( x ) 
      if x ≠ NIL
      then
              INORDER-TREE-WALK( left[x] )     // 왼쪽 자식
              print key[x]                                     // x의 데이터         
              INORDER-TREE-WALK( right[x] )   // 오른쪽 자식

Expression Tree

inorder 순회하면?

=> x + y * a + b / c

각 부트리를 순회할 때 괄호를 추가해주면 올바른 수식이 출력

=> ( x + y ) * ( ( a + b ) ) / c )

 선순위(preorder) 순회 

① 먼저 R을 순회하고

② TL을 순회하고

③ TR을 순회한다.

 

PREORDER-TREE-WALK( x )
      if x ≠ NIL then
      then
            print key[x]                                        // x의 데이터            
            PREORDER-TREE-WALK( left[x] )     // 왼쪽 자식
            PREORDER-TREE-WALK( right[x] )   // 오른쪽 자식

 후순위(postorder) 순회 

① 먼저 TL을 순회하고

② TR을 순회하고

③ R을 순회한다.

 

POSTORDER-TREE-WALK( x ) 
      if x ≠ NIL
      then           
            POSTORDER-TREE-WALK( left[x] )     // 왼쪽 자식
            POSTORDER-TREE-WALK( right[x] )   // 오른쪽 자식
            print key[x]                                          // x의 데이터  

postorder 순회하면?

=> x y + a b + c / *

 

연습) 설명해 보세요!

적혀있는 답은 중순위 순회

 Level-Order 순회 

레벨 순으로 방문하고, 동일 레벨에서는 왼->오른 순으로 순회한다.

큐(queue)를 이용하여 구현

1. 루트노드를 큐에 넣는다.

2. 큐에서 꺼내고(방문 했음) 자식 노드를 큐에 넣는다. 1을 반복한다.

 

LEVEL-ORDER-TREE-TRAVERSAL()
     visit the root;
     Q ← root;                  // Q is a queue
     while Q is not empty do
         v ← dequeue(Q);
         visit children of v;
         enqueue children of v into Q;
     end.
end.

방문순서: 3, 1, 5, 0 ,2, 4, 6, 7, 8