Week 7-2 : Tree, Binary Tree

< 180517 >

1) 트리

- 계층구조를 표현하기 위한 비선형 자료구조. ex) 디렉토리

- 노드(형제, 부모, 자식, 루트, 단말)

- 서브트리의 개념 설명. 트리의 자식노드를 루트로 하는 트리.

- 레벨 : 루트노드 기준 노드까지의 거리. 루트의 레벨을 0 으로 두기도 하고, 1로 두기도 한다.

- 높이 : 최대레벨

- 트리의 예시 (그림 출처 : http://wwst.tistory.com/2)

 

- 트리의 종류 : 일반트리, 이진트리

2) 이진트리 (Binary Tree)

- 정의 : 각 노드별 자식노드가 두개 이하로 구성된 트리..(최대 두개의 자식노드)

- 성질 : 노드의 갯수 -1 = 간선의 수

- n 개의 노드로 최대 n 레벨을 만들수 있으며, 최소 ceil(log(n+1))의 레벨을 만들 수 있다. 로그의 밑은 2.

- 이진트리의 종류(일반 이진트리, 완전이진트리, 포화 이진트리)

- 포화이진트리 : 마지막 레벨까지 모든 레벨에 노드가 가득 차 있는 트리.

- 완전이진트리 : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있는 트리.

- 일반이진트리 : 완전도 포화도 아닌 트리 (아래 그림에서 TreeA 는 일반 이진트리)

- 이진트리의 서브트리 (그림출처 : https://kks227.blog.me/221028710658)

>> 서브트리는 부모노드를 기준으로, 한 자식노드를 루트로 하는 트리

< 180529 >

- 이진 트리의 표현

1) 배열을 이용한 표션

>> 주로 힙(Heap)/우선순위 큐에서 사용

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

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

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

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

2) 링크 표현

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

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

- 트리의 순회  (그림출처 : https://kks227.blog.me/221028710658)

전위순회 : 루트 - 왼쪽 서브트리 - 오른쪽 서브트리 순으로 탐색

중위순회 : 왼쪽 서브트리 - 루트 - 오른쪽 서브트리 순으로 탐색

후위순회 : 왼쪽 서브트리 - 오른쪽 서브트리 - 루트 순으로 탐색

레벨순회 : 큐를 이용, 구현은 다음 시간에..!

>> 전위순회의 경우, 왼쪽 서브트리를 순회할때, 재귀적으로 왼쪽 서브트리의 루트를 기준으로 전위순회를 한다.

Preorder : ( 0 ) ( 1 3 6 7 4 ) ( 2 5 8 9 ) >> (루트) (왼쪽 서브트리) (오른쪽 서브트리)

왼쪽 서브트리의 경우 1 3 6 7 4 인데 마찬가지로 (1) (3 6 7) (4) >> (루트) (왼쪽 서브트리) (오른쪽 서브트리) 순으로 순회를 한다.

위에서 왼쪽 서브트리는 3 6 7 인데,  마찬가지로 (3) (6) (7) >>  (루트) (왼쪽 서브트리) (오른쪽 서브트리) 순으로 순회를 한다.

>> 중위순회, 후위순회도 마찬가지..!!

>> 왼쪽 ,오른쪽이 아니다. 왼쪽 서브트리, 오른쪽 서브트리. 개념 확실히 잡고 넘어가자. 

>> 루트 기준 왼쪽 자식 노드는 왼쪽 서브트리의 루트가 되며, 루트 기준 오른쪽 자식노드는 오른쪽 서브트리의 루트가 된다..!!

>> 트리를 삭제할 때에는 후위순회를 사용해야 한다. 

- 구현

#include <stdio.h>
#include <stdlib.h>
 
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);
   }
}
 
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("Tree의 높이 : %d\n", height(root));
   level(root);
}
 

>> 42 라인 : 트리에서 노드의 갯수는 왼쪽 서브트리의 노드의 갯수 + 오른쪽 서브트리의 노드의 갯수 + 1(기준 트리의 루트노드) 이다.

>> preorderPrint() 라는 함수는 한 트리의 루트를 매개변수로 전달 받는다.

    그리고 이 트리는 매개변수로 전달받은 루트를 기준으로 하는 트리에 대해 전위순회를 하는 함수이다.

    전위순호는 루트를 방문하고, 왼쪽 서브트리에 대해 전위순회를 하고, 오른쪽 서브트리에 대해 전위순회를 진행하면 된다.

    왼쪽 서브트리에 대해 전위순회를 진행하려면 preorderPrint() 라는 함수에 해당 왼쪽 서브트리의 루트를 매개변수로 전달하면 된다.

    마찬가지로 오른쪽 서브트리에 대해 전위순회를 진행하려면 preorderPrint() 라는 함수에 해당 오른쪽 서브트리의 루트를 매개변수로 전달하면 된다.

>> 48 라인 : 트리의 높이는 max(왼쪽 서브트리의 높이, 오른쪽 서브트리의 높이)+1 이 된다.

>> 58 라인 : 트리의 삭제, 후위순회 방식으로 진행한다.