Data Structure in C++ - Tree

본 포스팅 시리즈에서는 모든 프로그래머들이 반드시 알아야 할 가장 기본적인 자료구조를 다룰 예정이다.

앞으로 다룰 내용은 프로그래머에게 기본 소양이며, 본인 스스로 직접 구현할 수 있어야 한다. 

 

| 다섯 번째 순서는 트리이다. 

트리는 계층적으로 구성되어 있고 서로 연결되어있는 데이터에 적합한 계층적 자료구조이다. 이 구조는 링크드 리스트 와는 다른 자료구조이지만, 링크된 요소끼리는 선형 순서로 링크드 리스트라고도 볼 수 있다. 트리는 오래전부터 다양한 형태로 계속 연구되어 발전되어 왔고, 활용되었으며 또 특정 상황 및 애플리케이션에 맞는 제약사항을 가지게 되었다. 트리의 형태로는 대부분이 알고 있는 이진 탐색 트리부터 B 트리, 레드 블랙 트리, AVL 트리 등이 있다.

이진 탐색 트리는 말 그대로 데이터가 계층적으로 구조되어 있는 이진트리이다. 다만 이진트리와 차이점은 이진 탐색 트리는 데이터가 일정 기준으로 정렬되어 저장된다는 것이다. 그 기준은 아래와 같다. 

• 왼쪽 자식의 모든 서브 트리는 항상 부모노드의 값보다 작다
• 오른쪽 자식의 모든 서브 트리는 항상 부모노드의 값보다 크다.

추후 구현할 Heap또한 이 이진트리 기반으로 구현된다. 

다음은 가장 기본적인 TreeNode의 구현 사항이다. 

struct TreeNode{
    int val;
    TreeNode * left;
    TreeNode * right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
}

노드는 노드의 값과 왼쪽 자식, 오른쪽 자식과 연결을 위한 포인터 등으로 구성된다. 
보통 이진 트리를 탐색하는 방법은 총 3가지가 있는데, root를 기준으로 root를 먼저(Pre-Order) 탐색하거나, 
중간(In-Order)에 탐색, 혹은 마지막(Post-Order)으로 탐색하는 방법이 있다. 재귀 함수를 이용해 간단하게 구현할 수 있는 부분이다. 

void PreOrder(TreeNode* root) {
    if(root == nullptr) return;

    cout << root->val << endl;
    PreOrder(root->left);
    PreOrder(root->right);
}

void InOrder(TreeNode* root) {
    if(root == nullptr) return;

    InOrder(root->left);
    cout << root->val << endl;
    InOrder(root->right);
}

void PostOrder(TreeNode* root) {
    if(root == nullptr) return;

    PostOrder(root->left);
    PostOrder(root->right);
    cout << root->val << endl;
}

사실 트리라고 하면 보통 이진트리를 떠올리지만, 앞서 설명한 대로 자식이 2개가 아닌 경우가 많다. 트리의 자식 노드가 2개 이상일 수 있고, 또한 자식에서 부모 노드로의 연결도 표현할 수 있다. 또한, 트리의 자료형 또한 다양하게 나타날 수 있다. 아래 예를 확인하자. 

template <typename T>
class TreeNode{
private:
    T data; 
    TreeNode *parent;
    vector<TreeNode*> children;
public:
    void PrintData(TreeNode* root) {
        cout << root->data << endl;

        for(int i = 0; i< childeren.size(); i++) {
            PrintData(root->childeren[i]);
        }
    }

    int height(TreeNode* root) {
        int h = 0;
        for(int i = 0; i< root->children.size(); i++) {
            h = max(h, 1 + height(root->children[i]));
        }
        return h;
    }

}