Data Structure 13 - Tree(1)

트리는 부모와 자식관계로 이루어진 계층적인 자료구조이다. 흔히 볼 수 있는 트리의 구조로는 회사의 조직 구성도를 예로 들 수 있다. 각 데이터를 저장하는 곳을 node라 하며 그 자손들로 이루어진 트리를 subtree라 한다. 각각의 subtree는 또다시 subtree를 가질 수 있다.

가장 위의 첫 노드(회사의 조직 구성도 중 가장 높은 ceo)는 root node라고 하며 더 이상 자식을 가지지 않는 트리의 맨 아래 노드는 leaf node(혹은 terminal node)라 한다. 

각 노드를 있는 선을 간선이라 하며 이 간선의 수로 트리의 높이, 차수, 깊이를 결정한다.

먼저 트리의 차수(degree)는 해당 트리의 노드들이 가지는 자식의 수를 의미한다. 

트리의 깊이(depth)는 루트 노드에서 해당 노드까지 가는데 거치는 간선의 수다. 즉, 루트 노드의 depth는 0이다.

반대로, 트리의 높이(height)는 특정 노드에서 가장 맨 아래 leaf node까지 가는데 거치는 간선 수이다. 즉, leaf node의 높이는 0이고 tree 전체의 높이는 루트의 높이와 같다.

level은 계층으로 트리의 각 층의 동일한 노드를 가리킨다. level은 depth와 동일하다.

주로 많이 사용되는 것은 이진트리(binary tree)이다. 이는 모든 노드의 degree(차수)가 2인 트리이다. 이런 트리의 노드들을 순회하는 여러 순서가 있는데, 이를 traversal이라 한다. 이진 트리의 순회는 preorder, inorder, postorder가 있다. 

preorder는 root->left->right의 순회 순서를 가진다. 주로 구조화된 문서 출력에 사용한다.

inorder는 left->root->right의 순서를 가진다.

postorder는 left->right->root의 순서를 가진다. 주로 디렉토리 용량 계산에 사용된다.

이런 이진트리의 순회를 c코드로 나타내면 아래와 같다.

#include<stdio.h>
#include<stdlib.h>
#define max(a,b) ((a>b)?(a):(b))

typedef struct Node { // 연결리스트로 트리 구현.
    int data;
    struct Node* left;
    struct Node* right;
}Node;

Node* createNode(int data) { //노드 생성
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

void preorederTraversal(Node* root) { // root->left->right의 순서로 탐색하는 preorder 알고리즘
    if (root != NULL) {
        printf("%d", root->data); //root 자기자신의 데이터를 반환하고,
        preorderTraversal(root->left); // 왼쪽 서브트리 순회하고 재귀호출. 따라서 왼쪽sub도 자신의 data를 반환하고 왼쪽 혹은 오른쪽으로 내려감.
        preorderTraversal(root->right); // 오른쪽 서브트리 순회. 이 때 데이터가 없는 리프(혹은 단말)노드라면 if 문에서 탈출. 또한 재귀함수로 이 과정을 구현.
    }
}

void postorderTraversal(Node* root) { // 마찬가지로 왼쪽 서브트리->오른쪽 서브트리->root 순으로 탐색하는 postorder
    if (root != NULL) {
        postorderTraversal(root->left); // 왼쪽 서브트리
        postorderTraversal(root->right); // 오른쪽 서브트리
        printf("%d", root->data); // root 자기자신 데이터 반환. & 재귀함수로 다시 반복
    }
}

void inorderTraversal(Node* root) { // 왼쪽->자기자신->오른쪽 순
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d", root->data);
        inorderTraversal(root->right);
    }
}

int count(Node* rt) { // 해당 트리에 노드가 몇개 있는지 확인하는 함수. 각 서브트리를 계속 재귀호출하며 +1을 하여 계산.
    int countnum = 0;
    if (rt == NULL) return 0;
    countnum = 1 + count(rt->left) + count(rt->right);
    return countnum;
}

int get_leaf_count(Node* rt) { // 이번에는 해당 트리의 단말노드(자식이 없는)노드의 개수 계산. 마찬가지로 자식이 없는 경우에만 +1을 하고, 재귀로 계속 불러와 계산.
    int countnum = 0;
    if (rt == NULL) return 0;
    if (rt->left == NULL && rt->right == NULL) return 1;
    countnum = get_leaf_count(rt->left) + get_leaf_count(rt->right);
    return countnum;
}

int get_height(Node* rt) { // 해당트리의 높이 계산
    int height = 0;
    if (rt == NULL) return 0;
    height = 1 + max(get_height(rt->left), get_height(rt->right));//각 층 중에 가장 높은 서브트리를 선택하여 셈한 값을 반환하여 높이 계산
    return height;
}