이진트리의 순회 (전위,중위,후위) 구현하기

이진트리의 순회방법에는 전위순회, 중위순회, 후위순회의 3가지 방법이 있습니다.

이는 루트와 왼쪽 서브트리, 오른쪽 서브 트리 중에서 루트를 언제 방문 하느냐에 따라 구분할 수 있습니다.

기본적으로 트리의 순회는 순환구조를 이용합니다. 즉, 문제의 구조는 같고 크기만 작아지는 경우 순환을 적용할 수 있습니다.

루트:V, 왼쪽 서브 트리:L, 오른쪽 서브트리:R 이라고 할 때 순회과정은 아래와 같습니다.

V->L->R : 전위순회(preorder traversal)

L->V->R : 중위순회(inorder traversal)

L->R->V : 후위순회(postoreder traversal)

트리를 보고 각 순회방법에 따라 순회방법을 나열할 경우 아래처럼 순회방법을 적어놓고 생각하면 편합니다.

1. 전위 순회

 1) 루트 노드를 방문한다.

 2) 왼쪽 서브 트리를 방문한다.

 3) 오른쪽 서브 트리를 방문한다.

2. 중위 순회

 1) 왼쪽 서브 트리를 방문한다.

 2) 루트 노드를 방문한다.

 3) 오른쪽 서브 트리를 방문한다.

3. 후위 순회

 1) 왼쪽 서브 트리를 방문한다.

 2) 루트 노드를 방문한다.

 3) 오른쪽 서브 트리를 방문한다.

트리의 순회과정을 코드를 보고 분석 할 때는 직접 작은 단위(예를들어 높이2의 노드가3인 간단한 트리구조)부터 직접 손으로 그려가며

이해하는게 편합니다. (노드갯수가 조금만 많아져도 복잡해짐) 

이제 아래와 같은 트리를 이용해 각 순회방법을 적용해 보겠습니다.

코드

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
 
typedef struct treeNode
{
    int data;
    struct treeNode* left;
    struct treeNode* right;
}treeNode;
 
treeNode n1 = { 1,NULL,NULL };
treeNode n2 = { 4,&n1,NULL };
treeNode n3 = { 16,NULL,NULL };
treeNode n4 = { 25,NULL,NULL };
treeNode n5 = { 20,&n3,&n4 };
treeNode n6 = { 15,&n2,&n5 };
treeNode* root = &n6;
void preorder(treeNode* root)
{
    //루트가 존재할 때
    if (root)
    {
        printf("%d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}
void inorder(treeNode* root)
{
    if (root)
    {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}
void postorder(treeNode* root)
{
    if (root)
    {
        postorder(root->left);
        postorder(root->right);
        printf("%d ", root->data);
    }
}
int main()
{
    printf("전위순회: ");
    preorder(root); puts(" ");
    printf("중위순회: ");
    inorder(root); puts(" ");
    printf("후위순회: ");
    postorder(root); puts(" ");
 
}

결과