[Data Structure] 이진 트리의 순회

 이진 트리의 순회(traversal)에는 전위(preorder), 중위(inorder), 후위(postorder) 세 가지 방법이 있다. 이 세가지 방법의 차이는 말 그대로 순서(order)의 차이다. 무슨 말을 하는 것인지 그림으로 보도록 하자.

 이진트리의 노드타입에는 위와 같이 부모, 왼쪽 자식, 오른쪽 자식 이렇게 셋으로 나눠진다. 여기서 순서라는 것은 어떤 노드를 먼저 참조할 것인가에 대한 문제다.

1. preorder (전위 순회)

 순서는 먼저 parent -> left -> right의 순으로 참조한다. pre- 라는 접두사는 먼저의 라는 의미를 가지는데 이러한 이름에 걸맞게 parent가 먼저 참조된다는 특징이 있다.

2. inorder (중위 순회)

 순서는 left -> parent -> right 로 이어진다. 마찬가지로 in-은 중간의 라는 의미이므로 parent 노드가 2번째로 참조된다.

3. postorder

 이쯤되면 감이 온다. left -> right -> parent 로 이어진다. post-는 나중의 라는 의미를 가지므로 parent 노드가 가장 나중에 참조된다.

 아래의 코드는 위의 트리를 표현하고 있다.

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

typedef int element;
typedef struct {
    element data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 전위 순회
void preorder(TreeNode *root){
    if (root == NULL)
        return;
    printf("%d ",root->data);
    preorder((TreeNode*)root->left);
    preorder((TreeNode*)root->right);
}

// 중위 순회
void inorder(TreeNode *root){
    if (root == NULL)
        return;
    inorder((TreeNode*)root->left);
    printf("%d ",root->data);
    inorder((TreeNode*)root->right);
}

// 후위 순회
void postorder(TreeNode *root){
    if (root == NULL)
        return;
    postorder((TreeNode*)root->left);
    postorder((TreeNode*)root->right);
    printf("%d ",root->data);
}

TreeNode n1 = {1, NULL, NULL};
TreeNode n2 = {4, (struct TreeNode*)&n1, NULL};
TreeNode n3 = {16, NULL, NULL};
TreeNode n4 = {25, NULL, NULL};
TreeNode n5 = {20, (struct TreeNode*)&n3, (struct TreeNode*)&n4};
TreeNode n6 = {15, (struct TreeNode*)&n2, (struct TreeNode*)&n5};
TreeNode *root = &n6;

int main(){
    printf("inorder : ");
    inorder(root);
    printf("\npreorder : ");
    preorder(root);
    printf("\npostorder : ");
    postorder(root);
    printf("\n");
    return 0;
}

 recursive 한 코드이므로 이해하기가 아주 쉽다. 더 이상의 설명은 생략한다 ㄱ-