배열을 이용한 이진 트리(Binary Tree)

아래 문제를 통해 배열 이진 트리를 이해 해보자.

이 문제는 2번 예시 때문에 포인터를 이용한 트리를 제작하기가 까다롭다.

왜냐하면 루트 노드를 알 수 없고 최종적으로 input을 다 받았을 때 알아 낼 수 있기 때문이다.

배열을 이용한 이진 트리의 제작의 핵심은 다음과 같다.

1 2 3 4 5 6 7 8 9 10 11 12 13

#define nodeNum 100002   typedef struct _tree {     int left;     int right;     int chk;     int parent; }Tree;   Tree tree[nodeNum];   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus

 

구조체를 보면 

int left, int right, int chk, int parent가 존재한다.

각각 용도는 다음과 같다.

left :: 왼쪽 자식 노드의 배열 번호를 가지고 있는다.

right :: 오른쪽 자식 노드의 배열 번호를 가지고 있는다.

chk :: 이 노드가 생성된 노드인지 확인한다.(-1이면 없는 노드, 1이면 있는 노드)

parent :: 이 노드의 부모 노드가 무엇인지 확인한다.(-1이면 루트 노드, 그외 숫자가 들어가 있다면 부모 노드가 존재)

이 구조체를 노드의 개수(혹은 + 1)만큼 선언해준다.

즉, 노드 번호가 1~12번까지 있었다면 nodeNum은 13이면 된다.

노드 번호가 1번 부터이니 배열 번호의 0번 배열은 이용할 수 없게 되니 13개를 선언해야한다. 

    for (int i = 0; i < nodeNum-1; i++)
    {
        tree[i].chk = -1;
        tree[i].right = -1;
        tree[i].left = -1;
        tree[i].parent = -1;
    }
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

초기화를 통해 -1의 의미가 어떤 동작을 하는지 이해한다.

chk가 -1이면 없는 노드

left가 -1이면 왼쪽 자식이 없는 부모 노드

right가 -1이면 오른쪽 자식이 없는 부모 노드

parent가 -1이면 루트 노드가 될 수 있음을 암시

    for (int i = 0; i < n-1; i++)
    {
        scanf("%d %d %d", &parent, &child, &pos);
 
        if (pos == 0)
        {
            tree[parent].left = child; // 부모 배열번호에 left값에 자식 배열번호 값을 넣는다.
            tree[parent].chk = 1; // 부모 및 자식노드는 존재함을 선언
            tree[child].chk = 1;
            tree[child].parent = parent; // 자식의 부모를 알게해준다.
        }
 
        else
        {
            tree[parent].right = child; // 부모 배열번호에 right값에 자식 배열번호 값을 넣는다.
            tree[parent].chk = 1; // 부모 및 자식노드는 존재함을 선언
            tree[child].chk = 1;
            tree[child].parent = parent; // 자식의 부모를 알게해준다.
        }
    }
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

tree[parent].left = child :: 부모 노드 번호의 왼쪽에 자식 번호를 넣어준다.

tree[parent].chk = 1 :: 부모 노드는 활성화 되어있다.

tree[child].chk = 1 :: 자식 노드는 활성화 되어있다.

tree[child].parent = parent :: 자식 노드가 부모 노드가 무엇인지 알게해준다.

위의 문제에 대한 소스 코드이자, 배열을 이용한 이진 트리의 내용이다.

이 코드를 이용, 응용하여 이진 트리를 다르게 꾸밀 수 도있다.

// 배열을 이용한 이진 트리
 
#include <stdio.h>
#define nodeNum 100002
 
typedef struct _tree {
    int left;
    int right;
    int chk;
    int parent;
}Tree;
 
 
// 노드 개수만큼 배열 선언
Tree tree[nodeNum];
 
int k; // k번째 노드 찾기
 
int flag = 0; // flag = 1이되면 순회를 마친다는 의미입니다.
 
void PreorderTraverse(int now)
{
    if (now == -1 || tree[now].chk == -1 || flag == 1)
        return;
 
//    printf("현재 노드 :: %d\n", now);
    k--;
    if (k == 0)
    {
        printf("%d", now);
        flag = 1;
    }
 
    PreorderTraverse(tree[now].left);
    PreorderTraverse(tree[now].right);
 
}
 
 
void InorderTraverse(int now)
{
    if (now == -1 || tree[now].chk == -1 || flag == 1)
        return;
 
    InorderTraverse(tree[now].left);
 
//    printf("현재 노드 :: %d\n", now);
    k--;
    if (k == 0)
    {
        printf("%d", now);
        flag = 1;
    }
 
    InorderTraverse(tree[now].right);
 
}
 
 
void PostorderTraverse(int now)
{
    if (now == -1 || tree[now].chk == -1 || flag == 1)
        return;
 
 
    PostorderTraverse(tree[now].left);
    PostorderTraverse(tree[now].right);
 
//    printf("현재 노드 :: %d\n", now);
    k--;
    if (k == 0)
    {
        printf("%d", now);
        flag = 1;
    }
}
 
int main()
{
    // 초기화 (1부터 시작일수도있으니 100001개를 초기화합니다.)
    for (int i = 0; i < nodeNum - 1; i++)
    {
        tree[i].chk = -1;
        tree[i].right = -1;
        tree[i].left = -1;
        tree[i].parent = -1;
    }
 
    int n;
    int parent, child, pos; // pos = 0 :: left, pos = 1 :: right
 
    scanf("%d", &n);
 
    for (int i = 0; i < n-1; i++)
    {
        scanf("%d %d %d", &parent, &child, &pos);
 
        if (pos == 0)
        {
            tree[parent].left = child; // 부모 배열번호에 left값에 자식 배열번호 값을 넣는다.
            tree[parent].chk = 1; // 부모 및 자식노드는 존재함을 선언
            tree[child].chk = 1;
            tree[child].parent = parent; // 자식의 부모를 알게해준다.
        }
 
        else
        {
            tree[parent].right = child; // 부모 배열번호에 right값에 자식 배열번호 값을 넣는다.
            tree[parent].chk = 1; // 부모 및 자식노드는 존재함을 선언
            tree[child].chk = 1;
            tree[child].parent = parent; // 자식의 부모를 알게해준다.
        }
    }
 
    int h; // h = 1 :: 전위 , h = 2 :: 중위 , h = 3 :: 후위 
    int now;
    scanf("%d %d", &h, &k);
 
    // 루트노드 찾기(현재 루트노드가 뭔지 모르니 찾아내야 합니다.)
    for (int i = 1; i < n ; i++)
    {
        // 아래 printf로 검증해보세요.
        //printf("node :: %d parent :: %d lchild :: %d rchild :: %d\n", i, tree[i].parent, tree[i].left, tree[i].right);
        if (tree[i].parent == -1)
            now = i;
    }
 
    // printf("루트 노드 :: %d\n", now); // 루트 노드 확인
 
    if (h == 1)
        PreorderTraverse(now);
    
    else if (h == 2)
        InorderTraverse(now);
 
    else if (h == 3)
        PostorderTraverse(now);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>