TreeTraversal.md

트리의 순회

작성자

이진 트리 노드

struct node
{
    int val; // 데이터
    node* left; // 왼쪽 자식 노드
    node* right; // 오른쪽 자식 노드
};

전위 순회(preorder)

• V -> L -> R

1. 노드를 방문한다.
2. 왼쪽 서브 트리를 순회한다.
3. 오른쪽 서브 트리를 순회한다.

void preorder(node* n)
{
    // 1. 노드를 방문한다.
    cout<<n->val<<endl;
    // 2. 왼쪽 서브 트리를 순회한다.
    if(n->left != NULL)
    {
        preorder(n->left);
    } 
    // 3. 오른쪽 서브 트리를 순회한다.
    if(n->right != NULL)
    {
        preorder(n->right);
    }   
}

중위 순회(Inorder)

• L -> V -> R
• 트리의 값이 순차적으로 정렬된다.

1. 왼쪽 서브 트리를 순회한다.
2. 노드를 방문한다.
3. 오른쪽 서브트리를 순회한다.

void Inorder(node* n)
{
    // 1. 왼쪽 서브 트리를 순회한다.
    if(n->left != NULL)
    {
        Inorder(n->left);
    } 
    // 2. 노드를 방문한다.
    cout<<n->val<<endl;
    // 3. 오른쪽 서브 트리를 순회한다.
    if(n->right != NULL)
    {
        Inorder(n->right);
    }   
}

후위 순회(postorder)

• L -> R -> V

1. 왼쪽 서브 트리를 순회한다.
2. 오른쪽 서브트리를 순회한다.
3. 노드를 방문한다.

void postorder(node* n)
{
    // 1. 왼쪽 서브 트리를 순회한다.
    if(n->left != NULL)
    {
        postorder(n->left);
    } 
    // 2. 오른쪽 서브 트리를 순회한다.
    if(n->right != NULL)
    {
        postorder(n->right);
    }   
    // 3. 노드를 방문한다.
    cout<<n->val<<endl;
}

레벨 순회

• 레벨별로 순회하며 각 노드를 방문한다.
• level1 -> level2 -> ... -> levelN

void levelorder(node* root)
{
    queue<node*> q;
    q.push(root);
    while (!q.empty())
    {
        node* front = q.front();
        visit[front->data] = 1;
        if (front->left != NULL)
        {
            q.push(front->left);
        }
        if (front->right != NULL)
        {
            q.push(front->right);
        }
    }
}

예제

전위 순회

• F, B, A, D, C, E, G, I, H

중위 순회

• A, B, C, D, E, F, G, H, I

후위 순회

• A, C, E, D, B, H, I, G, F

레벨 순회

• F, B, G, A, D, I, C, E, H

참조

• Wiki