[알고리즘] 트리 순회(Tree traversal)

깊이와 높이

node를 트리 T의 노드라 하자. node의 깊이(depth)는 node의 조상의 수이다. 만약 node가 루트이면, node의 깊이는 0이 된다. 그렇지 않으면, node의 깊이는 node의 부모의 깊이에 1을 더한 것과 같다.

template <typename T>
int depth(Node<T>* node)
{
    if (node->is_root()) return 0;
    return 1+depth(node->parent());
}

 

트리 T에서 node의 높이(height)도 재귀적으로 정의된다. 만약 p가 외부 노드이면 p의 높이는 0이다. 그렇지 않으면 node의 높이는 node의 자식의 높이 중 가장 높은 값에 1을 더하면 된다.

template <typename T>
int height(Node<T>* node)
{
    if (node->is_external()) return 0;
    int h = 0;
    for (auto it = node->children.begin(); it != node->children.end(); ++it)
        h = (h > height(*it) ? h : height(*it));
    return 1 + h;
}

전위 순회(Preorder Traversal)

트리 T의 순회(traversal)는 T의 모든 노드를 방문하기 위한 체계적인 방법이다. 전위(preorder) 순회는 T의 루트가 첫 번째로 방문된 후, 자신의 자식 노드를 루트로 하는 서브 트리들을 재귀적으로 방문한다.

template <typename T>
void preorder(Node<T>* node)
{
    cout<<node->GetValue()<<" ";
    for (auto it = node->children.begin(); it != node->children.end(); ++it)
        preorder(*it);
}

후위 순회(Postorder Traversal)

후위(postorder) 순회는 루트의 자식 노드를 루트로 하는 서브 트리를 먼저 재귀적으로 순회한 후에 루트를 방문한다.

template <typename T>
void preorder(Node<T>* node)
{
    cout<<node->GetValue()<<" ";
    for (auto it = node->children.begin(); it != node->children.end(); ++it)
        preorder(*it);
}

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

너비 우선 순회는 깊이 d+1의 노드를 방문하기 전에 깊이 d인 모든 노드를 방문하는 방법이다. 너비 우선 순회는 큐(queue)를 이용하여 구현할 수 있다.

#include <queue>
using namespace std;

template <typename T> 
void bfs(Node<T>* node)
{
    queue<Node<T>*> q;
    q.push(node);
    while (!q.empty())
    {
        cout<<q.front()->GetValue()<<" ";
        for (auto it = q.front()->children.begin(); it != q.front()->children.end(); ++it)
            q.push(*it);
        q.pop();
    }
}