자료구조 - 트리 (Tree)

1. 트리란?

트리(Tree)란 자료들 사이의 계층적 관계를 나타내는데 사용하는 자료구조로 부모-자식 관계로 표현된다.

트리는 1개 이상의 노드를 갖는 집합으로 루트 노드가 존재하고 트리의 부분트리(SUb Tree) 또한 트리 구조를 따른다. 노드가 N개인 트리는 항상 N-1개의 간선을 가진다. 루트에서 어떤 노드로 가는 경로는 유일하다. 또한 두 개의 정점 사이에 반드시 1개의 경로만을 가진다. 한 개의 루트 노드만이 존재하며 모든 자식 노드는 한 개의 부모 노드만을 가진다.

 

2. 트리와 관련된 용어

• 루트 노드(root node) : 트리의 최상위 노드로 유일하다.
• 깊이 (Depth) : 루트 노드에서 해당 노드까지 도달하는데 사용하는 간선의 개수로 루트 노드는 자기 자신까지 도달하는 간선의 개수가 0이므로 루트 노드의 깊이는 0이다.
• 레벨 (Level) : 노드의 깊이 + 1
• 부모 노드 (Parent Node) : 부모 자식 관계에서 상위 계층에 있는 노드로 상위 계층에 있을수록 노드의 깊이와 레벨이 낮다.
• 자식 노드 (Child Node) : 부모 자식 관계에서 하위 계층에 있는 노드
• 형제 노드 (Sibling Node) : 부모가 동일한 노드
• 조상 노드 : 해당 노드의 부모노드부터 루트노드까지 가는 경로에 존재하는 노드들을 그 노드의 조상 노드라고 한다.
• 후손 노드 : 해당 노드를 루트로 하는 서브트리에 있는 모든 노드를 그 노드의 후손 노드라고 한다.
• 노드의 분지 수 (노드의 차수, Degree) : 노드의 자식 수
• 트리의 분지 수 (트리의 차수) : 해당 트리 내 모든 노드의 분지 수 중 최댓값
• 내부 노드 (internal/nonterminal Node) : 자식이 있는 노드
• 외부 노드 (단말 노드, 잎새 노드, leaf/external/terminal Node) : 자식이 없는 노드
• 높이 (Height) : 루트 노드에서 해당 노드까지 도달하는데 지나간 정점의 개수로 노드 중 가장 높이가 높은 노드의 높이를 트리의 높이라고 한다.

3. 트리의 응용

1) 트라이(Trie)

 

[예시문제]

주어진 입력 값으로 트리를 구성하고, 구성된 트리를 전위순회하고 방문한 노드의 번호를 출력하시오. 첫 줄에는 전체 테스트 케이스의 수(T), 두 번째 줄에는 노드의 총 수(nodeNum), 간선의 총 수(edgeNum)가 주어진다. 그 다음 줄에는 간선이 나열 된다. 간선은 그것을 이루는 두 정점으로 표기된다. 간선은 항상 “부모 자식” 순서로 표기 된다. 예를 들어 “1 2”는 정점 1과 2를 잇는 간선을 의미하며 1이 부모 2가 자식을 의미한다. 부모는 최대 2개의 자식 노드를 갖으며, 최대 노드의 개수는 10000개이다.

 

[Reference Code]

#include <stdio.h>
 
#define MAX_NODE_NUM 10000
#define MAX_CHILD_NUM 2
 
typedef struct
{
    int parent;
    int child[MAX_CHILD_NUM];
} TreeNode;
TreeNode tree[MAX_NODE_NUM];
int nodeNum;
int edgeNum;
int root;
 
void initTree(void) 
{
    int i;
    int j;
    for (i = 0; i <= nodeNum; i++)
    {
        tree[i].parent = -1;
        for (j = 0; j < MAX_CHILD_NUM; j++)
        {
            tree[i].child[j] = -1;
        }
    }
}
 
void addChild(int parent, int child) 
{
    int i;
    for (i = 0; i < MAX_CHILD_NUM; i++)
    {
        if (tree[parent].child[i] == -1)
        {
            break;
        }
    }
    tree[parent].child[i] = child;
    tree[child].parent = parent;
}
 
int getRoot(void) 
{
    int i;
    int j;
    for (i = 1; i <= nodeNum; i++) 
    {
        if (tree[i].parent == -1) 
        {
            return i;
        }
    }
    return -1;
}
 
void preOrder(int root) 
{
    int i;
    int child;
    printf("%d ", root);
 
    for (i = 0; i < MAX_CHILD_NUM; i++) 
    {
        child = tree[root].child[i];
        if (child != -1)
        {
            preOrder(child);
        }
    }
}
 
int main(void)
{
    int test_case;
    int T;
    int i;
    int parent;
    int child;
 
    scanf("%d", &T);
 
    for (test_case = 1; test_case <= T; ++test_case) 
    {
        scanf("%d %d", &nodeNum, &edgeNum);
 
        initTree();
 
        for (i = 0; i < edgeNum; i++)
        {
            scanf("%d %d", &parent, &child);
            addChild(parent, child);
        }
 
        root = getRoot();
 
        printf("#%d ", test_case);
        preOrder(root);
        printf("\n");
    }
 
    return 0;
}