[C] 이진트리의 순회

연결리스트로 이진트리를 구현해보자.

트리도 마찬가지로 배열 혹은 연결리스트로 구현할 수 있다. 배열로는 안해봤다. 기억공간의 낭비가 심해진다고 한다(? 무슨소리냐...). 그래서 연결리스트로 구현했다.

하나의 링크에는 총 3개의 필드가 있다. 가운데에 데이터필드, 왼쪽과 오른쪽에 각각의 자식노드를 가리키는 2개의 포인터필드이다. 그림을 보면 더 쉽게 이해할 수 있음.

 

출처: http://www.btechsmartclass.com/data_structures/binary-tree-representations.html

 

typedef struct TreeNode {
    int data;
    struct TreeNode* left, * right;
}Node;
 

 

이렇게 데이터필드와 왼쪽, 오른쪽의 포인터필드를 만들어주면 된다.

 

 

(1) 이진트리의 순회 개념정리

이전에 배웠던 선형 자료구조에서, 연산을 하기 위해서는 어떤 기능이 가장 먼저 필요했는지 떠올려보자. 바로 '순회'이다. 구조 안에 데이터를 넣든 빼든 출력하든 모두 노드를 방문해서, 노드가 가지고 있는 데이터를 목적에 맞게 처리해야 했다. 트리에서도 마찬가지로 순차적으로 순회하는 것이 중요한데, 문제는 선형이 아니다보니까 순회하는 방법을 우리가 정해줘야 한다. 표준적인 방법으로는 전위, 중위, 후위의 3가지 방법이 있다.

 

• 전위순회(preorder traversal): 루트노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리
• 중위순회(inorder traversal): 왼쪽 서브트리 -> 루트노드 -> 오른쪽 서브트리
• 후위순회(postorder traversal): 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트노드

루트노드의 위치를 기준으로 생각하면 외우기 쉽다.

각각의 서브트리를 방문할 때도 같은 알고리즘을 쓰면 된다. 가령 전위순회를 할때, 루트노드를 방문하고 왼쪽 서브트리를 방문한다고 하자. 그럼 왼쪽 서브트리의 어떤 노드를 방문하면 되는 것일까? '루트노드가 가장 먼저 방문된다'는 전제를 떠올리면 이 서브트리에서도 루트노드부터 방문해야 한다는 것을 알 수 있다.

어떻게든 그림을 그려보면 쉽다. 그림판으로 그릴 수는 없기 때문에 노트에 연습한 것을 올려본다.

 

 

 

대충 이런 식이다. 표준적인 순회 방법은 아니지만 레벨 순회도 있다. 각 노드를 레벨 순으로 검사하는 순회 방법이다. 레벨이 1인 루트노드부터 왼-오 순으로 레벨을 내려가면서 방문하는데, 큐를 사용한다. 자식노드들을 rear에서 enqueue하고 front에서 dequeue한다. 이것도 그림으로 그려보면 쉬움(올리기 귀찮으니까 생략한다)

 

 

 

(2) 이진트리의 순회 소스코드

전위, 중위, 후위 순회 함수들을 각각 구현해보았다. 

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
 
typedef struct TreeNode {
    int data;
    struct TreeNode* left, * right;
}Node;
/*
내가 만들 트리의 구조는 이렇게 생겼다.
        15
     4      20
  1     16      25 
*/
 
Node n1 = { 1, NULL, NULL };
Node n2 = { 4, &n1, NULL };
Node n3 = { 16, NULL, NULL };
Node n4 = { 25, NULL, NULL };
Node n5 = { 20, &n3, &n4 };
Node n6 = { 15, &n2, &n5 };
Node* root = &n6;
 
int is_empty(Node* root) {
    if (root == NULL) return 0;
    else return 1;
}
void preorder(Node* root) { //전위순회 root -> 왼쪽 -> 오른쪽
    if (is_empty(root) == 1) {
        printf("[%2d] ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}
void inorder(Node* root) { //중위순회 왼쪽 -> root -> 오른쪽
    if (is_empty(root) == 1) {
        inorder(root->left);
        printf("[%2d] ", root->data);
        inorder(root->right);
    }
}
void postorder(Node* root) { //후위순회 왼쪽 -> 오른쪽 ->root
    if (is_empty(root) == 1) {
        postorder(root->left);
        postorder(root->right);
        printf("[%2d] ", root->data);
    }
}
 
int main(void) {
    printf("전위순회 Preorder = ");
    preorder(root);
    printf("\n");
 
    printf("중위순회 Inorder = ");
    inorder(root);
    printf("\n");
 
    printf("후위순회 Postorder = ");
    postorder(root);
    printf("\n");
}

 

 

<결과 창>

 

 

순서만 헷갈리지 않으면 된다.