[알고리즘] 이진 트리 순회(Binary Tree Traversal)

전위 순회(Preorder Traversal)

이진 트리는 트리의 일종으로 일반적인 트리에 대한 전위 순회 알고리즘이 똑같이 적용될 수 있다.

template <typename T>
void preorder(Node<T>* node)
{
    if (node == nullptr) return;
    cout<<node->GetValue()<<" ";
    preorder(node->GetLeft());
    preorder(node->GetRight());
}

후위 순회(Postorder Traversal)

마찬가지로 후위 순회 알고리즘도 똑같이 적용된다.

template <typename T>
void postorder(Node<T>* node)
{
    if (node == nullptr) return;
    postorder(node->GetLeft());
    postorder(node->GetRight());
    cout <<node->GetValue()<<" ";
}

중위 순회(Inorder Traversal)

일반적인 트리와 다르게 이진 트리는 최대 2개의 자식 노드를 갖는다. 따라서 왼쪽 자식 노드를 방문하고 부모 노드를 방문하고 오른쪽 자식 노드를 방문하는 알고리즘이 구현 가능하다.

template <typename T> 
void inorder(Node<T>* node)
{
    if (node == nullptr) return;
    inorder(node->GetLeft());
    cout<<node->GetValue()<<" ";
    inorder(node->GetRight());
}

너비 우선 순회(Breadth-First Traversal)

마찬가지로 너비 우선 순회도 구현 가능하다.

template <typename T> 
void bfs(Node<T>* node)
{
    queue<Node<T>*> q;
    q.push(node);
    while (!q.empty())
    {
        cout<<q.front()->GetValue()<<" ";
        if (q.front()->GetLeft() != nullptr) q.push(q.front()->GetLeft());
        if (q.front()->GetRight() != nullptr) q.push(q.front()->GetRight());
        q.pop();
    }
}

 

오일러 투어 순회(Euler Tour Traversal)

오일러 투어 순회는 전위 순회, 중위 순회, 후위 순회를 모두 합친 형태이다.

template <typename T>
void eulertour(Node<T>* node)
{
    if (node == nullptr) return;
    cout <<node->GetValue()<<" ";
    eulertour(node->GetLeft());
    cout <<node->GetValue()<<" ";
    eulertour(node->GetRight());
    cout <<node->GetValue()<<" ";
}