[DS] 이진 탐색 트리 - Binary search tree, 순회 - Traversal (구현)

이미지 출처 : Pixabay

이진 탐색 트리의 구현 방법에는 여러 가지가 있습니다.

이 글에서는 리스트를 사용하여 재조정 없이 단순히 삽입만 수행하는 트리를 만들고 각 노드를 탐색하여 출력하고자 합니다.

트리 구조에서 각각의 노드를 정확히 한번씩 체계적인 방법으로 방문하는 것을 트리 순회 Tree traversal 라 하는데, 삽입된 원소들을 순회하는 방법은 크게 두 가지 분류로 나뉘며, 대표적인 다음 네 가지 탐색법이 있습니다.

Reference : https://en.wikipedia.org/wiki/Tree_traversal

Tree traversal - Wikipedia

첫 번째 분류는 깊이 우선 탐색 Depth-first search 이며, 일반적으로 스택으로 구현됩니다.

노드 N에서, 재귀적으로 왼쪽 서브트리를 순회하고 노드 N으로 돌아오는 것을 L, 재귀적으로 오른쪽 서브트리를 순회하고 노드 N으로 돌아오는 것을 R, 그리고 N 자신에 대한 탐색을 수행하는 것을 N이라고 했을 때,

전위 순회 Preorder traversal 는 N-L-R 

중위 순회 Inorder traversal 는 L-N-R

후위 순회 Postorder traversal 는 L-R-N 순서로 탐색이 수행됩니다.

깊이 우선 탐색 Depth-first search (*은 재귀 탐색시 return 수행 부분)

두 번째 분류는 너비 우선 탐색 Breath-first search 이며, 일반적으로 큐로 구현됩니다.

레벨 순서 순회 Level-order traversal : 모든 노드를 낮은 레벨부터 높은 레벨까지 순서대로 방문합니다.

너비 우선 탐색 Breath-first search

이진 탐색 트리를 만들기 위하여 템플릿 트리 노드 클래스를 정의해 줍니다.

template<typename Object>
class TreeNode {
private:
    Object * value_;
    TreeNode * left_;
    TreeNode * right_;

public:
    TreeNode() {
        value_ = nullptr;
        left_ = nullptr;
        right_ = nullptr;
    }
    TreeNode(Object& object) {
        value_ = &object;
        left_ = nullptr;
        right_ = nullptr;
    }
    Object& value() {
        return *value_;
    }
    void set_value(Object& value) {
        value_ = &value;
    }
    TreeNode<Object>* left() {
        return left_;
    }
    void set_left(TreeNode<Object> * node) {
        left_ = node;
    }
    TreeNode<Object>* right() {
        return right_;
    }
    void set_right(TreeNode<Object> * node) {
        right_ = node;
    }
};

그리고 재귀 호출을 통한 원소 삽입을 포함하여 재귀적으로 구현한 너비 우선 탐색법과 큐를 활용한 깊이 우선 탐색법의 구현을 포함하고, 재조정을 포함하지 않은 이진 탐색 트리 클래스는 다음과 같습니다.

레벨 순서 순회를 구현하기 위한 큐는 이전 글에서 작성한 클래스를 활용하였습니다.

[DS] 큐 - Queue (개념 및 배열로 큐 구현하기)

#include "queue.h"

template<typename Object>
class BinarySearchTree {
private:
    TreeNode<Object> * root_;
    int size_;
    TreeNode<Object> * InsertNode(TreeNode<Object> *node, Object &object) {
        if(node == nullptr) {
            return new TreeNode<Object>(object);
        }
        if(node->value() > object) {
            node->set_left(InsertNode(node->left(), object));
        } else if (node-> value() < object) {
            node->set_right(InsertNode(node->right(), object));
        }
        return node;
    }
    void PreorderTraversal(TreeNode<Object> * node) {
        cout << node->value() << ' ';
        if(node->left() != nullptr) {
            PreorderTraversal(node->left());
        }
        if(node->right() != nullptr) {
            PreorderTraversal(node->right());
        }
    }
    void InorderTraversal(TreeNode<Object> * node) {
        if(node->left() != nullptr) {
            InorderTraversal(node->left());
        }
        cout << node->value() << ' ';
        if(node->right() != nullptr) {
            InorderTraversal(node->right());
        }
    }
    void PostorderTraversal(TreeNode<Object> * node) {
        if(node->left() != nullptr) {
            PostorderTraversal(node->left());
        }
        if(node->right() != nullptr) {
            PostorderTraversal(node->right());
        }
        cout << node->value() << ' ';
    }
public:
    BinarySearchTree() {
        size_ = 0;
    }
    void InsertNode(Object &object) {
        root_ = InsertNode(root_, object);
    }
    void PreorderTraversal() {
        PreorderTraversal(root_);
        cout << endl;
    }
    void InorderTraversal() {
        InorderTraversal(root_);
        cout << endl;
    }
    void PostorderTraversal() {
        PostorderTraversal(root_);
        cout << endl;
    }
    void LevelorderTraversal() {
        Queue<TreeNode<Object> > node_queue;
        node_queue.EnQueue(*root_);
        while(node_queue.size() > 0) {
            TreeNode<Object> node = node_queue.DeQueue();
            cout << node.value() << ' ';
            if(node.left() != nullptr) {
                node_queue.EnQueue(*node.left());
            }
            if(node.right() != nullptr) {
                node_queue.EnQueue(*node.right());
            }
        }
        cout << endl;
    }
};

위 클래스에 값을 삽입할 땐 리밸런싱이 전혀 되지 않기 때문에 값을 삽입하는 순서에 유의하여야 합니다.

(삽입 순서 : F, B, A, D, C, E, I, H, G, J - 위 순회 방법 설명에 나타난 것과 같은 모양의 트리 만들기)

실행 결과