jynoh00 - 개발 블로그

자료구조 중 하나인 트리에 대하여 정리하고, 이진 트리와 이진 탐색 트리에 대하여 알아본다.

1. 트리

트리(Tree)는 계층적인 구조를 나타내는 자료구조로,
부모 - 자식간의 관계의 노드들로 구성된다. 트리의 간단한 구조는 다음과 같다.

alt text

위 그림에서 루트(Root), 부모가 없는 노드는 A 노드가 되고
단말 노드(Terminal), 자식이 없는 노드는 E, F, G, H, I, J가 존재한다.
비단말 노드로는 A, B, C, D가 있다.

트리에서 다양한 용어가 있는데 그 중 level, height, degree는 각각 다음과 같다.

level: 트리의 각 층 번호
height: 트리의 최대 level
degree: 노드의 자식 노드 수

alt text

2. 이진 트리

이진 트리는 트리의 일종으로, 모든 노드가 2개의 서브 트리를 가지고 있는 트리 구조이다.
( 이때 서브 트리는 공집합일 수 있다 )
alt text

이진 트리를 class를 이용하여 나타내면 다음과 같다.

#include <iostream>
using namespace std;

class TreeNode{
private:
    int data;
    TreeNode* left;
    TreeNode* right;
public:
    TreeNode(int d = 0, TreeNode* l = nullptr, TreeNode* r = nullptr){
        data = d;
        left = l;
        right = r;
    }
    void setData(int d){ data = d; }
    void setLeft(TreeNode* l){ left = l; }
    void setRight(TreeNode* r){ right = r; }
    int getData(){ return data; }
    TreeNode* getLeft(){ return left; }
    TreeNode* getRight(){ return right; }
};

class BinaryTree{
private:
    TreeNode* root;
public:
    BinaryTree(TreeNode* r = nullptr){ root = r; }
    void setRoot(TreeNode* r){ root = r; }
    bool isEmpty(){ return root == nullptr; }
};

int main(){
    TreeNode n1 = {1, nullptr, nullptr};
    TreeNode n2 = {16, nullptr, nullptr};
    TreeNode n3 = {25, nullptr, nullptr};
    TreeNode n4 = {4, &n1, nullptr};
    TreeNode n5 = {20, &n2, &n3};
    TreeNode n6 = {15, &n4, &n5};

    BinaryTree t;
    t.setRoot(&n6);
}

3. 이진 트리의 순회 방법

이진 트리를 순회하는 방법으론 기본적으로 3가지 방법이 있다.

전위순회: preorder traversal // 루트 -> 왼쪽 자식 -> 오른쪽 자식
중위순회: inorder traversal // 왼쪽 자식 -> 루트 -> 오른쪽 자식
후위순회: postorder traversal // 왼쪽 자식 -> 오른쪽 자식 -> 루트

BinaryTree 클래스에서 메소드로 각각의 순회를 구현하면 아래 코드와 같다.

//preorder
void preorder(){
    cout << "preorder: ";
    preorder(root);
    cout << endl;
}
void preorder(TreeNode* r){
    if(r){
        cout << r->getData() << " ";
        preorder(r->getLeft());
        preorder(r->getRight());
    }
}

//inorder
void inorder(){
    cout << "inorder: ";
    inorder(root);
    cout << endl;
}
void inorder(TreeNode* r){
    if(r){
        inorder(r->getLeft());
        cout << r->getData() << " ";
        inorder(r->getRight());
    }
}

//postorder
void postorder(){
    cout << "postorder: ";
    postorder(root);
    cout << endl;
}
void postorder(TreeNode* r){
    if(r){
        postorder(r->getLeft());
        postorder(r->getRight());
        cout << r->getData() << " ";
    }
}

main

t.preorder();
t.postorder();
t.inorder();

output

preorder: 15 4 1 20 16 25 
postorder: 1 4 16 25 20 15 
inorder: 1 4 15 16 20 25 

(pre, in, post)-order를 제외하고도 다양한 순회 방법이 있는데,
그 중에서도 level 순회는 큐(Queue)를 이용하여 구현할 수 있다.

alt text

레벨 순회(lvel order) 알고리즘은 아래와 같다.

initialize queue;

queue.enqueue(root);

while queue.isEmpty() != true do
    x <- queue.dequeue();

    if (x != nullptr) then
        print DATA(x);
        queue.enqueue(LEFT(x));
        queue.enqueue(RIGHT(x));

// 코드가 아닌 알고리즘 방식을 나타낸 문법으로, 코드 구현 시 각 설명에 맞게 작성

앞서 C++ 코드에서 사용했던 Tree 구조에서 Level-order를 진행하면 아래의 순서로 나타난다.

level order: 15 4 20 1 16 25 

정리,
트리는 계층적인 구조를 나타내는 자료구조이다.
inorder, preorder, postorder, levelorder 등 다양한 순회 방법이 존재한다.