[Data Structure] 이진 트리 순회

개요

트리 순회(tree traversal)은 트리의 모든 노드를 한 번씩 방문하는 것이다.

L, V, R이 한 노드에서 각각 왼쪽 이동, 노드 방문, 오른쪽 이동을 나타낸다면 다음과 같다.

• 전위 순회: VLR
• 중위 순회: LVR
• 후위 순회: LRV

트리의 순회는 재귀를 사용하면 쉽게 구현할 수 있다.

트리의 순회 방법은 수식에서의 전위 표기(prefix), 중위 표기(infix), 후위 표기(postfix)가 자연스럽게 대응된다.

이진 트리 구현

#include <iostream>
#include <queue>

template <typename T>
class TreeNode
{
    public:
        TreeNode(T data)
        {
            this->data = data;
        }

    T data;
    TreeNode<T>* left = nullptr;
    TreeNode<T>* right = nullptr;
};

template <typename T>
class BinaryTree
{
public:
    // 빈 이진 트리 생성
    BinaryTree() {}

    // 왼쪽 서브트리, 오른쪽 서브트리, 값을 갖는
    // 이진트리 생성
    BinaryTree(BinaryTree<T>* leftSubTree, T data, BinaryTree<T>* rightSubTree)
    {
        TreeNode<T>* newNode = new TreeNode(data);
        if (leftSubTree)
            newNode->left = leftSubTree->GetRootNode();
        else
            newNode->left = nullptr;

        if (rightSubTree)
            newNode->right = rightSubTree->GetRootNode();
        else
            newNode->right = nullptr;
        root = newNode;
    }

    ~BinaryTree()
    {
        DeleteAllNode(this->root);
    }

    void DeleteAllNode(TreeNode<T>* node)
    {
        if (node)
        {
            DeleteAllNode(node->left);
            DeleteAllNode(node->right);
            delete node;
        }
    }

    // 이진 트리 공백 여부
    bool IsEmpty()
    {
        if (this->root)
            return false;
        else
            return true;
    }
    
    TreeNode<T>* GetRootNode()
    {
        if (IsEmpty())
        {
            std::cout << "Binary tree is empty\n";
            return nullptr;
        }
        else
            return this->root;
    }

    TreeNode<T>* GetLeftSubtree()
    {
        if (IsEmpty())
        {
            std::cout << "Binary tree is empty\n";
            return nullptr;
        }
        else
            return this->root.left;
    }

    TreeNode<T>* GetRightSubtree()
    {
        if (IsEmpty())
        {
            std::cout << "Binary tree is empty\n";
            return nullptr;
        }
        else
            return this->root.right;
    }

    T RootData()
    {
        if (IsEmpty())
        {
            std::cout << "Binary tree is empty\n";
            return NULL;
        }
        else
            return this->root.data;
    }
    
 private:
    TreeNode<T>* root = nullptr; // root node
};

전위 순회 (preorder traversal)

void Preorder(TreeNode<T>* node)
{
    if (node) // 널 포인터가 아니면
    {
        std::cout << node->data << " ";
        Preorder(node->left);
        Preorder(node->right);
    }
}

중위 순회 (inorder traversal)

void Inorder(TreeNode<T>* node)
{
    if (node) // 널 포인터가 아니면
    {
        Inorder(node->left);
        std::cout << node->data << " ";
        Inorder(node->right);
    }
}

후위 순회 (postorder traversal)

void Postorder(TreeNode<T>* node)
{
    if (node) // 널 포인터가 아니면
    {
        Postorder(node->left);
        Postorder(node->right);
        std::cout << node->data << " ";
    }
}

레벨 순서 순회 (level order traversal)

큐를 사용한다.

void LevelOrder()
{
    std::queue<TreeNode<T>*> q; // 큐
    TreeNode<T>* currNode = root;
    while (currNode)
    {
        std::cout << currNode->data << " ";
        if (currNode->left)
            q.push(currNode->left);
        if (currNode->right)
            q.push(currNode->right);
        if (q.empty()) return; // 큐 비었으면 리턴
        currNode = q.front(); // 다음 노드 => 큐 맨 앞
        q.pop();
    }
    std::cout << "\n";
}