180301 튜터링 - 트리(Tree)

< 180301 >

- 트리 : 계층 구조를 표현하는 비선형 자료구조

- 용어 : 노드(부모, 자식, 형제), 공집합 노드, 단말노드(리프, 터미널), 루트, 서브트리, 레벨, 높이

- 트리의 종류 : 일반트리, 이진트리(Binary Tree)

- 이진트리의 정의 : 모든 노드가 2개의 서브트리를 가지고 있는 트리. (서브트리는 공집합일 수 있다.)

- 이진트리의 성질

>> 노드 수 = 간선 수 + 1

>> 레벨에 따른 최소, 최대 노드를 구할 수 있다.

>> 노드가 n개 일때, 최대 레벨은 n, 최소 레벨은 ceil(log(n+1))

- 이진트리의 종류 : 완전, 포화

>> 완전 이진트리 : 레벨에 따라 왼쪽에서 오른쪽으로 순차적으로 노드가 삽입된 트리

>> 포화 이진트리 : 각 레벨에 노드가 가득 차 있는 이진 트리.

- 이진 트리의 표현

1) 배열을 이용한 구현

>> 주로 힙(Heap)에서 사용

>> 구현의 편의상 0번째 인덱스를 사용하지 않는 경우가 많은 것 같다.

>> 현재노드 기준, 부모노드의 인덱스는 현재노드의 인덱스 / 2

>> 현재노드 기준, 왼쪽 자식의 인덱스는 현재노드의 인덱스 * 2

>> 현재노드 기준, 오른쪽 자식의 인덱스는 현재노드의 인덱스 * 2 + 1

2) 링크 표현

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

>> 노드는 이런식으로 디자인을 한다.

- 트리의 구현 (coded by ㄱㄱㄷ ㅋㄱ ㄱㅇㄹ)

// Tree
#include <stdio.h>
#include <stdlib.h>
 
#define MAX 100
 
typedef struct TreeNode {
   int data;
   struct TreeNode * left;
   struct TreeNode * right;
} TreeNode;
 
TreeNode* makeTreeNode(int data, TreeNode * left, TreeNode * right) {
   TreeNode * tmp = (TreeNode*)malloc(sizeof(TreeNode));
   tmp->data = data;
   tmp->left = left;
   tmp->right = right;
   return tmp;
}
 
void preorderPrint(TreeNode * root) {
   if (root) {
      printf("%d ", root->data);
      preorderPrint(root->left);
      preorderPrint(root->right);
   }
}
 
void inorderPrint(TreeNode * root) {
   if(root){
      inorderPrint(root->left);
      printf("%d ", root->data);
      inorderPrint(root->right);
   }
}
 
void postorderPrint(TreeNode * root) {
   if(root) {
      postorderPrint(root->left);
      postorderPrint(root->right);
      printf("%d ", root->data);
   }
}
 
int nodeCount(TreeNode * root) {
   int count = 0;
   if (root) count = nodeCount(root->left) + nodeCount(root->right) + 1;
   return count;
}
 
int height(TreeNode * root) {
   int count=0;
 
   if (root) {
       int L = height(root->left);
       int R = height(root->right);
       count = (L > R ? L : R) + 1;
   }
   return count;
}
 
void clear(TreeNode * root) {
   if (root) {
      clear(root->left);
      clear(root->right);
      free(root);
   }
}
 
 
// QUEUE
typedef struct queue {
   TreeNode * data[MAX];
   int front;
   int rear;
} Queue;
 
void init(Queue * q) {
   q->front = 0;
   q->rear = 0;
}
 
int isEmpty(Queue * q) {
   return (q->front == q->rear);
}
 
int isFull(Queue * q) {
   return (q->rear + 1) % MAX == q->front;
}
 
void enqueue(Queue * q, TreeNode * data) {
   if (isFull(q)) printf("큐가 포화상태입니다. 더이상 삽입할 수 없습니다.\n");
   else {
      q->rear = (q->rear + 1) % MAX;
      q->data[q->rear] = data;
   }
}
 
TreeNode* peek(Queue * q) {
   if (isEmpty(q)) {
      printf("(peek)큐가 비어있습니다. : ");
      return NULL;
   }
   return q->data[(q->front + 1) % MAX];
}
 
void dequeue(Queue * q) {
   if (isEmpty(q)) printf("(deqeue)큐가 비어있습니다.\n");
   else {
      q->front = (q->front + 1) % MAX;
   }
}
 
 
 
void level(TreeNode * root) {
   Queue q;
   init(&q);
 
   if (root) {
      enqueue(&q, root);
   }
 
   while (!isEmpty(&q)) {
      TreeNode * tmp = peek(&q); dequeue(&q);
      printf("%d ", tmp->data);
      if (tmp->left) enqueue(&q, tmp->left);
      if (tmp->right) enqueue(&q, tmp->right);
   }
}
 
 
int main()
{
   TreeNode * t8 = makeTreeNode(8, NULL, NULL);
   TreeNode * t4 = makeTreeNode(4, t8, NULL);
   TreeNode * t5 = makeTreeNode(5, NULL, NULL);
   TreeNode * t6 = makeTreeNode(6, NULL, NULL);
   TreeNode * t7 = makeTreeNode(7, NULL, NULL);
   TreeNode * t2 = makeTreeNode(2, t4, t5);
   TreeNode * t3 = makeTreeNode(3, t6, t7);
   TreeNode * t1 = makeTreeNode(1, t2, t3);
 
   TreeNode * root = t1;
 
   preorderPrint(root);
   printf("\n");
   
   inorderPrint(root);
   printf("\n");
   
   postorderPrint(root);
   printf("\n");
 
   printf("노드 갯수 : %d개\n", nodeCount(root));
   printf("depth : %d\n", height(root));
 
   level(root);
 

}
 

>> makeTreeNode() : 첫번째 인자로는 데이터를, 

     두번째 인자는 왼쪽 서브트리의 루트가 될 노드(의 주소)를, 

     세번째 인자로는 오른쪽 서브트리의 루트가 될 노드(의 주소)를 전달한다.

>> 21-27 : 전위순회 코드이다. 전위순회는 루트 - 왼쪽 서브트리 - 오른쪽 서브트리의 순서로 탐색을 한다.

>> 29-35 : 중위순회 코드이다. 중위순회는 왼쪽 서브트리 - 루트 - 오른쪽 서브트리의 순서로 탐색을 한다. 

>> 37-43 : 후외순회 코드이다. 후위순회는 왼쪽 서브트리 - 오른쪽 서브트리 - 루트의 순서로 탐색을 한다.

>> 45-49 : 노드의 갯수를 구하는 함수로 

                  왼쪽 서브트리의 노드의 갯수 + 오른쪽 서브트리의 노드의 갯수 + 자기 자신의 갯수를 포함한 것이 트리의 노드의 갯수가 된다

>> 51-60 : 트리의 높이를 구하는 함수로

                  왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 중 큰 값에 자기 자신이 높이(1)를 더한 것의 트리의 높이가 된다.

>> 62-68 : 트리의 모든 노드를 삭제하는 함수. 후위순회로 진행하면 된다. 다른 순회로 하면 왜 안되는지도 생각해보자.

>> 116-130 : 트리의 레벨 순회.

                    큐가 필요하다. 또한 TreeNode의 포인터를 담아야 하므로,  73 라인에서 보는 것 처럼 큐의 데이터 타입을 TreeNode* 로 변경하였다.

                    알고리즘은 다음과 같다.

1) 우선 루트를 큐에 담는다.

2) 큐가 비어 있지 않을때까지 루프를 돈다.

3) 큐에 있는 노드 하나를 꺼내 해당 데이터를 출력한다.

4) 꺼낸 노드의 왼쪽 자식노드와 오른쪽 자식노드를 큐에 담는다.

>> 135-142 : 트리를 생성하는 과정이다.

### BST 는 아마 언젠가 업데이트를 할거 같아. 시간은 걸리겠지만, 하게되면 알려줄게. 여기까지 따라오느라 다들 수고 많았어!!