자료구조 트리(TREE)

트리(TREE)

계층적인 구조를 나타내는 자료구조

부모-자식 관계의 노드들로 이루어짐

* 리스트, 스택, 큐 등은 선형 자료 구조

응용분야

계층적인 조직 표현

컴퓨터 디스크의 디렉토리 구조

• 회사의 조직

• 파일 디렉토리 구조

• 결정트리

트리의 용어

노드(node): 트리의 구성요소 

루트(root): 부모가 없는 노드(A)

서브트리(subtree): 하나의 노드와 그 노드들의 자손들로 이루어진 트리

단말노드(terminal node): 자식이 없는 노드(E,F,G,H,I,J)

비단말노드: 적어도 하나의 자식을 가지는 노드(A,B,C,D)

자식, 부모, 형제, 조상, 자손 노드: 인간과 동일 

레벨(level): 트리의 각층의 번호

높이(height): 트리의 최대 레벨(3)

차수(degree): 노드가 가지고 있는 자식 노드의 개수 

트리의 예제

A는 루트 노드이다

B는 D와 E의 부모노드이다

C는 B의 형제 노드이다

D와 E는 B의 자식노드이다

B의 차수는 2이다

위의 트리의 높이는 4이다

이진 트리(binary tree)

---

모든 노드가 2개의 서브 트리를 가지고 있는 트리

서브트리는 공집합일수 있음

이진트리의 노드에는 최대 2개까지의 자식 노드가 존재

모든 노드의 차수가 2 이하가 된다-> 구현하기가 편리함

이진 트리에는 서브 트리간의 순서가 존재

이진 트리 검증

• 이진 트리는 공집합이거나 
• 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의됨
• 이진트리의 서브 트리들은 모두 이진트리여야 함

이진 트리 성질

• 노드의 개수가 n개이면 간선의 개수는 n-1
  
  
• 
• 높이가 h인 이진트리의 경우, 최소 h개의 노드를 가지며 최대 2^h-1개의 노드를 가짐

이진 트리의 분류

• 

포화 이진 트리(full binary tree)

• 높이가 5인 포화 이진트리의 노드의 수는?  31개

완전 이진 트리(complete binary tree) 

• 레벨 1부터 k-1까지는 노드가 모두 채워져 있고
  마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리

• 포화 이진 트리와 노드 번호가 일치

이진 트리의 표현

1. 배열을 이용하는 방법

• 모든 이진트리를 포화이진트리라고 가정하고 각 노드에 번호를 붙여서 
  그 번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장하는 방법
  ex)
• 노드 i의 부모 노드 인덱스 = i/2
• 노드 i의 왼쪽 자식 노드 인덱스 = 2i
• 노드 i의 오른쪽 자식 노드 인덱스 = 2i+1
• 포인터를 이용하는 방법

2. 링크 표현법 (포인터를 이용하는 방법)

노드는 구조체로 표현

typedef struct TreeNode { int data; struct TreeNode *left, *right; } TreeNode;

링크는 포인터로 표현

이진 트리의 순회

순회(traversal): 트리의 노드들을 체계적으로 방문하는 것

3가지의 기본적인 순회방법

1. 전위순회(preorder traversal)    : VLR , 자손노드보다 루트노드를 먼저 방문한다.
    루트가 제일 앞에

2. 중위순회(inorder traversal)  : LVR , 왼쪽 자손, 루트, 오른쪽 자손 순으로 방문한다.

루트가 중간

3. 후위순회(postorder traversal) : LRV, 루트노드보다 자손을 먼저 방문한다.

루트가 제일 뒤

* Left, Right의 순서는 그대로이지만 루트가 제일 앞, 중간, 제일 뒤의 순서가 바뀜

순환호출을 이용한 전위 순회

preorder(x) if x≠NULL then print DATA(x); preorder(LEFT(x)); preorder(RIGHT(x));

명시되어 있지는 않지만 NULL 값일 경우 return 한다고 봄

중위 순회 알고리즘

inorder(x) if x≠NULL then inorder(LEFT(x)); print DATA(x); inorder(RIGHT(x));

후위 순회 알고리즘

postorder(x) if x≠NULL then postorder(LEFT(x)); postorder(RIGHT(x)); print DATA(x);

레벨 순회(level order)

각 노드를 레벨 순으로 검사하는 순회 방법

지금까지의 순회법이 스택을 사용했던 것에 비해 레벨 순회는 큐를 사용하는 순회법이다.

level_order(root) initialize queue; enqueue(queue, root); while is_empty(queue)≠TRUE do  x← dequeue(queue); if( x≠NULL) then  print DATA(x); enqueue(queue, LEFT(x)); enqueue(queue, RIGHT(x));

수식트리 : 산술식을 트리형태로 표현한 것

* 컴퓨터는 계산을 위해 중위표현식을 후위표기식으로 바꾸고 스택을 사용하여 계산

수식트리 계산

• 후위순회를 사용
• 서브트리의 값을 순환호출로 계산
• 비단말노드를 방문할때 양쪽서브트리의 값을 노드에 저장된 연산자를 이용하여 계산한다
  
  

수식트리 알고리즘

evaluate(exp) if exp = NULL   then return 0;   else x←evaluate(exp->left);        y←evaluate(exp->right);        op←exp->data;        return (x op y);

이진트리연산 : 노드 개수

탐색 트리안의 노드의 개수를 계산

각각의 서브트리에 대하여 순환 호출한 다음, 반환되는 값에 1을 더하여 반환

int get_node_count(TreeNode *node) {   int count=0;   if( node != NULL )     count = 1 + get_node_count(node->left)+  get_node_count(node->right);   return count; }

이진트리연산 : 높이

서브트리에 대하여 순환호출하고 서브 트리들의 반환값 중에서 최대값을 구하여 반환

int get_height(TreeNode *node) {   int height=0;   if( node != NULL )      height = 1 + max(get_height(node->left),  get_height(node->right));   return height; }