[자료구조] Binary-Tree 이진 트리 C언어로 구현하기

이진트리?

---

자식 노드의 수가 2개 이하인 트리 (left child, right child)

 

이진트리 종류

• Full binary tree: 모든 노드의 자식 노드 수가 0개 혹은 2개
• Complete tree: 마지막 레벨을 제외한 트리의 모든 레벨에서 노드가 가득 채워져 있고, 마지막 레벨의 노드는 왼쪽부터 채움
• Balanced binary tree: 트리의 왼쪽 서브트리와 오른쪽 서브트리 사이의 레벨 차이가 1 이하인 트리
• perfect binary tree: 트리의 모든 노드가 2개의 자손을 지님, 트리의 모든 leaf는 같은 레벨에 있음

 

이진 트리 C언어로 구현하기

---

트리의 노드 구조체

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

typedef struct tNode {
    int data;
    struct tNode* left;
    struct tNode* right;
} tNode;

더블 링크드 리스트의 형태와 유사하다.

하나는 왼쪽 자식 노드를, 나머지 하나는 오른쪽 자식 노드를 가리킨다.

 

complete binary tree의 경우 다음과 같이 배열로 표현할 수 있다.

 

트리 순회 Traversal 함수 구현하기

 

1. 데이터를 담은 새로운 노드

// data를 담는 새로운 노드 선언
tNode* newNode(int data) {
    tNode* node = (tNode*)malloc(sizeof(tNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    
    return node;
}

 

 

2-1. In-order 순회 함수 구현

// in-order로 순회하는 함수 구현
void printInorder(tNode* node) {
	
    if (node == NULL)
        return;

    // 왼쪽 서브트리 재귀적 순회
    printInorder(node->left);

    // 서브트리의 root를 출력
    printf("%d ", node->data);

    // 오른쪽 서브트리 재귀적 순회
    printInorder(node->right);
}

 

2-2. pre-order 순회 함수 구현

// pre-order로 순회하는 함수 구현
void printPreorder(tNode* node) {
	
    if (node == NULL)
        return;

    // 트리의 root를 출력
    printf("%d ", node->data);

    // 왼쪽 서브트리 재귀적 순회
    printPreorder(node->left);

    // 오른쪽 서브트리 재귀적 순회
    printPreorder(node->right);
}

 

2-3. post-order 순회 함수 구현

// post-order로 순회하는 함수 구현
void printPostorder(tNode* node) {
	
    if (node == NULL)
        return;
    
    // 왼쪽 서브트리 재귀적 순회
    printPostorder(node->left);

    // 오른쪽 서브트리 재귀적 순회
    printPostorder(node->right);

    // (서브)트리의 root를 출력
    printf("%d ", node->data);
}

 

3. 트리 만들고(1번의 newNode 함수를 이용) 순회하기(2번의 함수들 이용)

int main() {
	
    tNode* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);

    printf("In-order 순회\n");
    printInorder(root);
    printf("\n");

    printf("Pre-order 순회\n");
    printPreorder(root);
    printf("\n");

    printf("Post-order 순회\n");
    printPostorder(root);
    printf("\n");

    getchar();
    return 0;
}

결과