[C] 이진 트리 구현 코드

1. 이진 트리 노드 구현

 

이진 트리는 부모가 왼쪽 자식, 오른쪽 자식을 가지고 있다는 점에서 포인터를 이용해서 구현하면 효과적인 데이터 관리가 가능하다.

 

노드 구조체는 다음과 같다. 

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

typedef struct Node {
    int data;
    struct Node *leftChild;
    struct Node *rightChild;
} Node;

하나의 노드는 내부적으로 하나의 data를 가지고 있다. 여기 예시 코드에서는 정수형 데이터 하나만 들어가는 걸로 설정했지만, 실제로는 다양한 데이터가 data에 들어갈 수 있다. 

 

특정 노드를 초기화하는 함수는 다음과 같다.

Node* initNode(int data, Node* leftChild, Node* rightChild) {
    Node* node = (Node*) malloc(sizeof(Node));
    node -> data = data;
    node -> leftChild = leftChild;
    node -> rightChild = rightChild;
    return node;
}

이진트리 같은 경우에는 함수의 반환형에서 특정 노드의 포인터가 들어가는 경우가 많다. data, leftNode, rightNode 모두 초기화시켜준 다음, 그 노드의 포인터를 반환해 준다.

 

2. 이진 트리의 순회 알고리즘

 

이진 트리는 자료구조이기 때문에 컴퓨터의 메모리상에 올라가 있어 사람이 이진트리에 담긴 데이터를 시각화하기란 어렵다. 따라서 이진트리에 담긴 데이터를 조회해서 출력하는 방법으로는 주로 순회 기법을 사용한다. 크게 세 가지 순회 방법이 있다.

 

(1) 전위 순회

 

- 자기 자신을 출력한다 -> 왼쪽 자식을 방문한다. -> 오른쪽 자식을 방문한다.

 

전위 순회 같은 경우에는 먼저 루트에서 시작하면 자기 자신을 출력하고, 그 다음에 왼쪽 자식노드로 들어가서 데이터를 출력하고, 다시 그 노드의 왼쪽 자식노드로 들어가서 데이터를 출력한다. 마지막에 다다르면 부모 노드로 거슬러 올라갔다가, 부모 노드의 오른쪽 자식 노드로 가서 데이터를 출력한다. 

 

전위 순위법

 

void preorder(Node* root) {
    if (root) {
        printf("%d ", root -> data);
        preorder(root -> leftChild);
        preorder(root -> rightChild);
    }   
}

특정한 노드가 주어졌을 때, 그 노드가 null값이 아니라면 재귀적으로 다음 노드를 탐색한다. 먼저 자기 자신을 출력한 후에 왼쪽으로 들어가고, 마지막에 왼쪽 노드가 null이면 이제 오른쪽 노드로 들어가는 것이다.

 

(2) 중위 순회

 

- 왼쪽 자식 출력 -> 그 다음 자기 자신 출력 -> 오른쪽 자식 출력

 

맨 위 노드에서 계속 왼쪽 자식 노드로 내려간 다음, 1을 출력한다. 그 다음 2, 3을 출력한다. 돌아와서 4를 출력하고 같은 과정을 반복한다. 항상 왼쪽으로 쭉 내려갔다가 자신으로 돌아온 후 오른쪽으로 간다. 결과적으로 왼쪽에서부터 오른쪽으로 차례로 출력된다. 

 

 

 

중위 순위법

 

void inorder(Node* root) {
    if (root) {
        inorder(root -> leftChild);
        printf("%d ", root -> data);
        inorder(root -> rightChild);
    }
}

전위순위랑 비슷하고 코드의 순서만 바꿔주면 된다. 왼쪽 노드를 먼저 방문 후, 자기 자신을 출력하고 오른쪽을 방문한다.

 

(3) 후위 순위

 

- 왼쪽 자식 방문 -> 오른쪽 자식 방문 -> 자기 자신 출력

 

먼저 왼쪽 최하단 노드 1을 방문한 다음, 그 형제 노드 2를 방문한 후 부모 노드 3을 출력한다. 그리고 루트의 오른쪽 4, 5, 6 노드들에 대해서도 같은 연산을 반복한 다음 루트로 돌아와서 출력한다. 이 알고리즘은 루트가 가장 마지막에 출력된다는 특징이 있다. 

 

후위 순위법

 

void postorder(Node* root) {
    if (root) {
        postorder(root -> leftChild);
        postorder(root -> rightChild);
        printf("%d ", root -> data);
    }
}

마찬가지로 코드의 순서만 바꿔주면 된다. 왼쪽 노드를 먼저 방문 후, 오른쪽을 방문한 다음 자기 자신을 출력한다.

 

3. 순회 알고리즘 코드로 표현해보기

 

int main(void) {
    Node* n7 = initNode(50, NULL, NULL);
    Node* n6 = initNode(37, NULL, NULL);
    Node* n5 = initNode(23, NULL, NULL);
    Node* n4 = initNode(5, NULL, NULL);
    Node* n3 = initNode(48, n6, n7);
    Node* n2 = initNode(17, n4, n5);
    Node* n1 = initNode(30, n2, n3);
    preorder(n1);
    printf("\n");
    inorder(n1);
    printf("\n");
    postorder(n1);
    printf("\n");
}

 

루트 노드를 n1이라고 하고 그 자식을 각각 n2, n3라 한다. 또 각 자식도 자식노드를 가진다. 이 하위 자식노드는 더 이상 자식 노드를 갖지 않기 때문에 왼쪽 노드, 오른쪽 노드 부분에 NULL을 넣어 준다. 차례대로 전위, 중위, 후위순회를 실행해 보면 다음과 같이 출력된다.

 

30 17 5 23 48 37 50 
5 17 23 30 37 48 50 
5 23 17 37 50 48 30