C/C++ 이진 트리(binary tree) 개요 및 구현(1)

개요

트리는 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조이다. 하위 트리가 존재하고, 그 노드에 또 하위 트리가 존재하는 자료구조 이다. 트리의 맨 위에 있는 루트 노드가 존재한다. 우리가 알아볼 트리는 이진 트리이다. 이진 트리는 자식 노드(부모로부터 아래로 이어진 노드)가 2개 이하인 구조를 말한다. 트리의 사용 사례로는 다음과 같다

계층 적 데이터 저장(파일,폴더)
효율적인 검색 속도
힙
데이터 베이스의 인덱싱

트리에 관한 용어

degree - 각 노드가 가진 자식 노드(가지)의 수
root node(루트 노드) - 맨 위의 노드, 부모가 없다
leaf node(단말 노드) - 자식이 없는 노드
internal node(내부 노드) - leaf node가 아닌 노드
edge - 노드를 연결하는 선
depth - 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 edge의 수
level - 같은 깊이를 가진 노드의 집합, 맨 위부터 레벨 1, 2, 3 순으로 간다.
height - 루트 노드에서 가장 깊숙이 있는 노드의 깊이

이진 트리의 종류

정 이진트리(Strict Binary Tree)

오직 0 또는 2의 degree의 노드만 존재한다. 즉 자식이 무조건 두 개 또는 한 개이다.
포화 이진트리(Perfect Binary Tree)

모든 노드가 2개의 자식을 가지고 leaf 노드가 모두 같은 level이다.
완전 이진트리(Complete Binary Tree)

마지막 level을 제외하고 모든 노드가 채워져 있어야 한다. 마지막 레벨의 노드는 다 채워져 있을 수도 있고 아닐 수도 있다. 또한 노드는 왼쪽에서 오른 쪽으로 빈 공간 없이 채워져 있어야 한다.

이진 트리의 특징

height 당 최대/최소 노드
- 최대 - n = 2^(h+1) -1
- 최소 - n = h + 1
strict m-array(최대 dgree가 2인) tree 에서 height 당 최대/최소 노드
- 최대 - (m^(h+1) - 1) / (m - 1)
- 최소 - m*h + 1
- 이진트리는 2-array tree다.

이진 트리의 표현

array

하나의 배열에 노드를 순서대로 입력하는 것이다. 일반적으로 맨 위 level의 노드부터 해서 왼쪽에서 오른쪽 순서대로 입력한다.

각 노드의 인덱스에 대한 규칙은 다음과 같다.

루트 노드	1
노드 i의 부모	i / 2
노드 i의 왼쪽 자식	i * 2
노드 i의 오른쪽 자식	i * 2 + 1

연결 리스트 활용

각 노드를 연결 리스트의 노드로 보는 것이다. 각 노드는 데이터와 왼쪽 노드를 향한 포인터, 오른쪽 노드를 향한 포인터로 이루어져 있다.

훨씬 직관적이기에 연결 리스트 형태의 이진 트리 활용을 선호한다.

이진 트리 순회(traversing) 방식

preorder

A->B->D->H->I->E->J->K->C->F->G

부모 노드, 왼쪽 노드, 오른쪽 노드 순으로 순회함
postorder

H->I->D->J->K->E->B->F->G->C->A

왼쪽 노드, 오른쪽 노드, 부모 노드 순으로 순회함
Inorder

H->D->I->B->J->E->K->A->F->C->G

왼쪽 노드, 부모 노드, 오른쪽 노드 순으로 순회함

TreeCreate함수-트리 생성

트리 생성은 큐와 연결 리스트를 통해 구현한다. 원리는 다음과 같다. 노드를 생성하고, 큐에 넣는다. 큐의 선입선출 방식을 이용해 큐에서 노드를 뽑은 다음, 해당 노드의 왼쪽 자식 노드, 오른쪽 자식 노드를 생성해 큐에 집어 넣는다. 그 후, 다시 큐에서 노드를 뽑아 자식 노드를 만들어 큐에 넣는 방식을 반복한다. 코드를 통해 알아보자.

Node *root = NULL;
void Treecreate()
{
    Node *p, *t;
    Queue q;
    create(&q, 100);

    int x;
    printf("Enter root value");
    scanf("%d", &x);
    root = new Node;
    root->data = x;
    root->lchild = root->rchild = NULL;
    enqueue(&q, root);

    while(!isEmpty(q))
    {
        p = dequeue(&q);
        printf("Enter left child: %d", p->data);
        scanf("%d", &x);
        if (x != -1)
        {
            t = new Node;
            t->data = x;
            t->lchild = t->rchild = NULL;
            p->lchild = t;
            enqueue(&q, t);
        }

        printf("Enter right child: %d", p->data);
        scanf("%d", &x);
        if (x != -1)
        {
            t = new Node;
            t->data = x;
            t->lchild = t->rchild = NULL;
            p->rchild = t;
            enqueue(&q, t);
        }
    }
}

큐에 노드가 존재할 때, 노드를 큐에서 뽑아 자식 노드를 만들고, 자식 노드를 큐에 넣는 방식이다.

preorder함수-preorder 순회를 재귀 함수로

void preorder(Node *p)
{
    if (p)
    {
        printf("%d", p->data);
        preorder(p->lchild);
        preorder(p->rchild);
    }
}

부모 노드의 데이터를 출력하고, 왼쪽 자식 노드로 옮기고, 오른쪽 자식 노드로 옮기는 방식이다. 트리 자체가 하위 노드에 또 하위 노드가 있는 재귀 형태이기 때문에 재귀 함수로의 구현이 쉽다.

postorder함수-postorder 순회를 재귀 함수로

void postorder(Node *p)
{
    if (p)
    {
        postorder(p->lchild);
        postorder(p->rchild);
        printf("%d ", p->data);
    }
}

Inorder함수-Inorder 순회를 재귀 함수로

void inorder(Node *p)
{
    if (p)
    {
        inorder(p->lchild);
        printf("%d ", p->data);
        inorder(p->rchild);
    }
}

마무리

트리의 기초와 트리 생성, 순회 코드를 알아보았다. 비선형 구조인 만큼 직관적인 트리 생성을 이해하기 힘들다. 하지만, 연결 리스트와 재귀를 활용해서 쉽게 구현할 수 있다. 다음 글에서는 위의 순회 코드를 루프를 통해 구현해보자. 루프는 이보다 이해가 어려우니 주의를 기울이자.