[C++] 이진 트리 구현하고 순회하기 (Binary Tree in C++)

이진트리(Binary Tree)란?

모든 노드의 차수를 2 이하루 정하여 전체 트리의 차수가 2 이하가 되도록 만든 것이 이진트리다.

이진트리는 왼쪽 자식노드와 오른쪽 자식노드 2개만을 가질 수 있으며, 공백노드도 이진트리의 노드로 취급한다.

이진트리의 서브트리 모두 이진트리이다.

이진트리의 종류

이진트리는 포화 이진 트리(Full binary tree), 완전 이진트리(Complete binary tree), 편향 이진트리(Skewed binary tree) 3가지가 있다.

포화 이진트리는 모든 레벨에 노드가 꽉찬 이진트리를 말하며, 공백 노드가 없다.

즉 트리의 높이가 h 일때 2^(h+1) - 1 개의 최대 노드수를 갖는 이진트리이다.

완전 이진트리는 노드 개수가 n 개일 때, 노드의 위치가 포화 이진트리의 노드 1번 부터 n번 까지의 위치와 완전히 일치하는 이진트리다.

편향이진트리는 트리중 최소 개수의 노드를 가지면서 왼쪽이나 오른쪽 서브트리만 가지고 있는 트리이다.

이진트리 C++로 구현하기

이진트리를 C++로 구현하기 위해서 구조를 간단하게 살펴보면 아래 그림과 같다.

그림은 C 코드 이지만 이것을 간단히 C++ 스타일로 바꿔주면 된다.

우리가 구현할 트리는 아래 그림처럼 생겼다. (그림판 ㅈㅅ ㅋㅋㅋ)

이 이진트리를 순회 할것인데, 순회 방법은 전위순회(preorder traversal), 중위순회(inorder traversal), 후위순회(postorder traversal) 3가지가 있다. 처음 보면 "으악 이게 뭐야!" 할 텐데, 알고보면 간단하다. 현재 노드를 언제 방문할 것이냐에 따른 문제로,

전위 순회를 예로보면 현재노드 먼저, 다음 왼쪽 서브트리, 다음 오른쪽 서브트리 순으로가는 것에서 알 수 있다.

전위순회 순서 : (1) 현재노드 방문 (2) 현재노드의 왼쪽 서브트리 이동 (3) 현재노드 오른쪽 서브트리 이동

중위순회 순서 : (1) 현재노드의 왼쪽 서브트리 이동 (2) 현재노드 방문 (3) 현재노드 오른쪽 서브트리 이동

후위순회 순서 : (1) 현재노드의 왼쪽 서브트리 이동 (2) 현재노드 오른쪽 서브트리 이동 (3) 현재노드 방문

이들 함수가 재귀적으로 호출된다.

전위순회 알고리즘을 간단히 아래와 같은 의사코드처럼 생겼다 하자.

preorder(T)

if (T != null) then {

visit T.data;

preorder(T.left);

preorder(T.right);

}

end preorder()

이 순회 경로는 'A - B - D - H - E - I - J - C - F - G - K' 처럼된다.

이해가 안간다면 직접 종이에 그려서 위 코드를 따라가보면 된다.

나머지 traversal도 같다.

#include <iostream>
#define null 0
 
using namespace std;
 
template <typename T>
class Tree;
 
template <typename T>
class TreeNode {
    friend class Tree<T>;
private:
    T data;
    TreeNode* left;
    TreeNode* right;
public:
    TreeNode(T data = 0, TreeNode* left = null, TreeNode* right = null) {
        this->data = data;
        this->left = left;
        this->right = right;
    }
};
 
template <typename T>
class Tree {
private:
    TreeNode<T>* root;
public:
    Tree(T data = 0) {
        root = new TreeNode<T>(data);
    }
    // Tree 만들기
    /*
                A
            B        C
          D      E      F   G
         H   I J       K 
    */
    void buildTree() {
        root->left = new TreeNode<T>('B', new TreeNode<T>('D', new TreeNode<T>('H')), new TreeNode<T>('E', new TreeNode<T>('I'), new TreeNode<T>('J')));
        root->right = new TreeNode<T>('C', new TreeNode<T>('F'), new TreeNode<T>('G', null, new TreeNode<T>('K')));
    }
 
    TreeNode<T>* getRoot() {
        return root;
    }
 
    void visit(TreeNode<T>* current) {
        cout << current->data << " ";
    }
 
    // 전위 순회 Current - Left - Right
    void preorder(TreeNode<T>* current) {
        if (current != null) {
            visit(current);
            preorder(current->left);
            preorder(current->right);
        }
    }
 
    // 중위 순회 Left - Current - Right
    void inorder(TreeNode<T>* current) {
        if (current != null) {
            inorder(current->left);
            visit(current);
            inorder(current->right);
        }
    }
 
    // 후위 순회 Left - Right - Current
    void postorder(TreeNode<T>* current) {
        if (current != null) {
            postorder(current->left);
            postorder(current->right);
            visit(current);
        }
    }
};
 
int main() {
    Tree<char> tree('A');
    tree.buildTree();
    cout << "Preorder >> ";
    tree.preorder(tree.getRoot());
    cout << endl;
 
    cout << "Inorder >> ";
    tree.inorder(tree.getRoot());
    cout << endl;
 
    cout << "Postorder >> ";
    tree.postorder(tree.getRoot());
    cout << endl;
}

출력 결과