[Data Structures] Tree (트리)

Tree

트리는 사이클 없이 간선으로 연결되어있는 노드들의 집합이다.

 

Siblings

한 노드의 자식 노드들은 서로 Sibling이라고 한다.

 

Ordered Tree

각 레벨에 있는 자식 노드들 사이의 순서에 의미가 부여되어 있는 트리

 

Degree

노드의 Degree는 해당 노드가 갖고 있는 자식 노드의 수이고, 트리의 Degree는 트리의 노드들의 Degree중 최댓값을 의미한다. leaf 노드는 Degree가 0이다.

 

Path, Length of path

한 노드에서 다른 노드까지의 경로 상에 존재하는 노드들의 순서를 path 라고하고, 그 노드들을 연결하는 간선의 개수를 length of a path라고 한다.

 

Depth(level) of a node

트리의 루트 노드부터 특정 노드까지의 length of the unique path를 뜻한다.

 

Height of tree

height of a tree는 height of the root와 같다. height는 다음과 같은 수식으로 표현할 수 있다.

height(i) = max(height(child_of_i)) + 1, (단, leaf 노드의 Height는 0.)

 

Counting #edge

트리의 간선을 세는 식은 다음과 같다.

edge(i) = sum(edge(child_of_i)) + size(child_of_i)

 

Binary tree (이진 트리)

이진트리는 노드의 집합이 공집합 이거나, 루트 노드와 그 노드의 왼쪽 이진 서브트리, 오른쪽 이진 서브트리로 구성된 노드의 집합이다.

 

- i 레벨에 존재할 수 있는 노드의 최대 개수는 2^i개이다.

 

- degree가 2인 노드의 개수 + 1 = degree가 0인 노드의 개수이다.

  노드의 개수 = degree가 0인 노드의 개수 + degree가 1인 노드의 개수 + degree가 2인 노드의 개수

  노드의 개수 = 간선의 수 + 1 = degree가 1인 노드의 개수 + 2 * degree가 2인 노드의 개수 + 1

  degree가 1인 노드의 개수 + 2 * degree가 2인 노드의 개수 + 1 = degree가 0인 노드의 개수 + degree가 1인 노드의 개수 + degree가 2인 노드의 개수

  따라서 degree가 2인 노드의 개수 + 1 = degree가 0인 노드의 개수

 

- Full binary tree

  모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리

 

- Complete binary tree

  마지막 레벨을 제외한 모든 레벨에 최대 노드의 개수가 존재하는 트리. 마지막 레벨에는 노드들이 왼쪽으로 치우쳐 있다.

 

- Perfect binary tree

  내부 노드가 모두 2개의 자식을 가지며, 리프 노드가 모두 같은 레벨에 존재하는 트리, Perfect binary tree는 Full binary tree이며 Complete binary tree이다. 트리의 height가 h일 때, 공비가 2이고, 항의 개수가 h + 1인 등비수열의 합이 노드의 개수(2^(h+1)-1)이다. 

Preorder, Inorder, Postorder tree traversal

재귀적으로 트리를 순회하는 방법.

- Preorder Traversal (전위 순회) : 루트 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리

- Inorder Traversal (중위 순회) : 왼쪽 서브트리 -> 루트 노드 -> 오른쪽 서브트리

- Postorder Traversal (후위 순회) : 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트 노드

 

Binary tree Implementation

다음은 Binary tree의 ADT이다.

typedef int BTData;

typedef struct _biTreeNode
{
    BTData data;
    struct _biTreeNode *left;
    struct _biTreeNode *right;
} BiTreeNode;

BiTreeNode *MakeBTreeNode(void);
BTData GetData(BiTreeNode *bt);
void SetData(BiTreeNode *bt, BTData data);

BiTreeNode *GetLeftSubTree(BiTreeNode *bt);
BiTreeNode *GetRightSubTree(BiTreeNode *bt);

void MakeLeftSubTree(BiTreeNode *main, BiTreeNode *sub);
void MakeRightSubTree(BiTreeNode *main, BiTreeNode *sub);

typedef void (*VisitFuncPtr)(BTData data);

void PreorderTraverse(BiTreeNode *bt, VisitFuncPtr action);
void InorderTraverse(BiTreeNode *bt, VisitFuncPtr action);
void PostorderTraverse(BiTreeNode *bt, VisitFuncPtr action);

 

다음은 Binary tree의 구현체이다.

#include <stdio.h>
#include <stdlib.h>
#include "BinaryTree.h"

BiTreeNode *MakeBiTreeNode(void)
{
    BiTreeNode *nd = (BiTreeNode *)malloc(sizeof(BiTreeNode));
    nd->left = NULL;
    nd->right = NULL;
    return nd;
}

BTData GetData(BiTreeNode *bt)
{
    return bt->data;
}

void SetData(BiTreeNode *bt, BTData data)
{
    bt->data = data;
}

BiTreeNode *GetLeftSubTree(BiTreeNode *bt)
{
    return bt->left;
}

BiTreeNode *GetRightSubTree(BiTreeNode *bt)
{
    return bt->right;
}

void MakeLeftSubTree(BiTreeNode *main, BiTreeNode *sub)
{
    if (main->left != NULL)
        free(main->left);

    main->left = sub;
}

void MakeRightSubTree(BiTreeNode *main, BiTreeNode *sub)
{
    if (main->right != NULL)
        free(main->right);

    main->right = sub;
}

void PreorderTraverse(BiTreeNode *bt, VisitFuncPtr action)
{
    if (bt == NULL)
        return;

    action(bt->data);
    PreorderTraverse(bt->left, action);
    PreorderTraverse(bt->right, action);
}

void InorderTraverse(BiTreeNode *bt, VisitFuncPtr action)
{
    if (bt == NULL)
        return;

    InorderTraverse(bt->left, action);
    action(bt->data);
    InorderTraverse(bt->right, action);
}

void PostorderTraverse(BiTreeNode *bt, VisitFuncPtr action)
{
    if (bt == NULL)
        return;

    PostorderTraverse(bt->left, action);
    PostorderTraverse(bt->right, action);
    action(bt->data);
}