이진 트리

이진 트리는 배열과 리스트로 구현이 가능하다. 이진 트리에서 이해하기 쉬운 리스트로 구현할 예정이다. 배열 기반 트리는 나중에 나올 '힙'이라는 자료 구조에서 알아보도록 하자. 이 포스트에서는 리스트를 이용하여 이진 트리를 구현해볼 것이다.

노드의 형태

먼저 아래의 그림을 보면 노드의 형태가 나온다. 이진 트리의 정의를 보면 "노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합 노드가 존재하는 것으로 간주한다." 라고 정의되어 있다. 그러므로 아래의 그림은 두 가지 형태는 같은 노드로 표현이 된다.

이진 트리의 노드

이진 트리의 연결

아래의 그림을 보면 B노드를 생성한 후 A 노드의 왼쪽 자식으로 연결해준 모습을 보여준다. 연결의 경우 간단하기 때문에 다른 언급은 하지 않겠다.

A 노드에 B 노드를 자식으로 연결시킨 모습

이진 트리의 순회

트리의 순회 방법은 총 3가지가 있다.
1) 전위 순회라고 하며 루트 노드를 먼저 순회하는 방법이다.
2) 중위 순회라고 하며 루트 노드를 중간에 순회하는 방법이다.
3) 후위 순회라고 하며 루트 노드를 마지막에 순회하는 방법이다.

위의 정의에서 알아보듯이 루트 노드를 기준으로 순회가 이루어진다. 
아래의 그림에서 보듯이 레벨 1의 순회는 그다지 어렵지 않다. 그런데 높이가 2 이상이 될 경우에는 조금 당황스러울 수도있지만 트리는 재귀적인 구조이다. 그렇기 때문에 재귀적으로 해결을 하면된다. 아래의 코드에서 확인해보자.

트리의 순회

#include <iostream>
 
using namespace std;
 
// 큐 구조체
typedef struct binaryTree
{
    // 생성자
    binaryTree() : left(nullptr), right(nullptr), data(0) {}
 
    binaryTree* left;
    binaryTree* right;
    int data;
}BINARYTREE;
 
// 객체 삭제 함수
template<typename T>
void SafeDelete(T& instance)
{
    if (instance == nullptr)
        return;
 
    delete instance;
    instance = nullptr;
}
 
// 왼쪽 서브 트리 연결
void MakeLeftSubTree(BINARYTREE* rootNode, BINARYTREE* childNode)
{
    if (rootNode->left != nullptr)
        SafeDelete(rootNode->left);
 
    rootNode->left = childNode;
}
 
// 오른쪽 서브 트리 연결
void MakeRightSubTree(BINARYTREE* rootNode, BINARYTREE* childNode)
{
    if (rootNode->right != nullptr)
        SafeDelete(rootNode->right);
 
    rootNode->right = childNode;
}
 
// 데이터를 반환
int GetData(BINARYTREE* binaryTree)
{
    return binaryTree->data;
}
 
// 데이터 삽입
void SetData(BINARYTREE* binaryTree, int data)
{
    binaryTree->data = data;
}
 
// 전위 순회
void PreorderTraversal(BINARYTREE* binaryTree)
{
    if (binaryTree == nullptr)
        return;
 
    cout << binaryTree->data << endl;
    PreorderTraversal(binaryTree->left);
    PreorderTraversal(binaryTree->right);
}
 
// 중위 순회
void InorderTraversal(BINARYTREE* binaryTree)
{
    if (binaryTree == nullptr)
        return;
 
    InorderTraversal(binaryTree->left);
    cout << binaryTree->data << endl;
    InorderTraversal(binaryTree->right);
}
 
// 후위 순회
void PostorderTraversal(BINARYTREE* binaryTree)
{
    if (binaryTree == nullptr)
        return;
 
    PostorderTraversal(binaryTree->left);
    PostorderTraversal(binaryTree->right);
    cout << binaryTree->data << endl;
}
 
int main()
{
    // 이진 트리 생성
    BINARYTREE* newBinaryTreeA = new BINARYTREE;
    BINARYTREE* newBinaryTreeB = new BINARYTREE;
    BINARYTREE* newBinaryTreeC = new BINARYTREE;
    BINARYTREE* newBinaryTreeD = new BINARYTREE;
 
    // 이진 트리 데이터 설정
    SetData(newBinaryTreeA, 1);
    SetData(newBinaryTreeB, 2);
    SetData(newBinaryTreeC, 3);
    SetData(newBinaryTreeD, 4);
 
    // 이진 트리 자식 연결
    MakeLeftSubTree(newBinaryTreeA, newBinaryTreeB);
    MakeRightSubTree(newBinaryTreeA, newBinaryTreeC);
    MakeLeftSubTree(newBinaryTreeB, newBinaryTreeD);
 
    // 전위 순회로 노드 출력
    PreorderTraversal(newBinaryTreeA);
 
    // 이진 트리 삭제
    SafeDelete(newBinaryTreeA);
    SafeDelete(newBinaryTreeB);
    SafeDelete(newBinaryTreeC);
    SafeDelete(newBinaryTreeD);
}