[Recursion/C++] 이진트리(Binary Tree)의 순회 / PreOrder(전위순회), InOrder(중위순회), postOrder(후위순회)

이진트리의 정의 (recursively)

• (Base case) 공집합이거나
• (recursive step) 루트 노드와 왼쪽 및 오른쪽 하위 트리로 구성되며, 서브 트리들은 모두 이진트리이다.

 

struct node
{
    char data;
    struct node *leftSubtree;
    struct node *rightSubtree;
};

 

트리 순회

• 트리 구조에서 각각의 노드를 정확히 한 번만, 체계적인 방법으로 방문하는 과정을 말한다.
• 트리 순회의 종류
  • PreOrder(전위순회) : root → leftSubTree → rightSubTree
  • InOrder(중위순회) : leftSubtree → root → rightSubTree
  • PostOrder(후위순회) : leftSubTree → rightSubTree → root

 

PreOrder(전위순회)

void preorder(node *root)
{
    if (root == NULL)
        return;

    else
    {
        printf("%c ", root-> data);
        preorder(root -> leftSubtree);
        preorder(root->rightSubtree);
    }

}

 

InOrder(중위순회)

void inorder(node *root)
{
    if (root == NULL)
        return;

    else
    {
        inorder(root -> leftSubtree);
        printf("%c ", root-> data);
        inorder(root->rightSubtree);
    }
}

 

PostOrder(후위순회)

void postorder(node *root)
{
    if (root == NULL)
        return;

    else
    {
        postorder(root -> leftSubtree);
        postorder(root->rightSubtree);
        printf("%c ", root-> data);
    }

}