[C++] 이진 탐색 트리 구현하기 (Binary Search Tree)

이진 탐색 트리 (Binary Search Tree)

이진 탐색트리는 데이터의 크기에 따라 노드의 위치가 다르다.

정의는 아래와 같다.

(1) 모든 원소는 서로 다른 유일한 키를 갖는다.

(2) 왼쪽 서브 트리에 있는 원소의 키는 그 루트의 키보다 작다.

(3) 오른쪽 서브 트리에 있는 원소의 키는 그 루트의 키보다 크다.

(4) 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리이다.

이진 탐색 트리 C++ 구현

이제 이진 탐색트리를 구현할텐데,

- 탐색(search)

- 삽입(insert)

두 가지 기능을 수행하도록 할 것이다.

구현해볼 이진 탐색트리는 아래와 같이 생겼다. 

주황색 표시된 부분은 새로 추가해볼 노드다.

#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;
    }
    friend ostream& operator<<(ostream& os, const TreeNode<T>& node) {
        os << "[data] " << node.data << endl;
        if (node.left != null) {
            os << "[left] " << node.left->data << endl;
        }
        if (node.right != null) {
            os << "[right] " << node.right->data << endl;
        }
        return os;
    }
};
 
template <typename T>
class Tree {
private:
    TreeNode<T>* root;
public:
    Tree(T data = 0) {
        root = new TreeNode<T>(data);
    }
    // Tree 만들기
    void buildSearchTree() {
        insertNode(new TreeNode<int>(3));
        insertNode(new TreeNode<int>(10));
        insertNode(new TreeNode<int>(14));
        insertNode(new TreeNode<int>(2));
        insertNode(new TreeNode<int>(5));
        insertNode(new TreeNode<int>(11));
        insertNode(new TreeNode<int>(16));
    }
 
    void insertNode(TreeNode<T>* node) {
        // 중복이 없을 때
        if (search(root, node->data) == null) {
            TreeNode<T>* parent = null;
            TreeNode<T>* current = root;
            // 작으면 왼쪽, 크면 오른쪽으로 이동,
            // 새 노드의 부모가 정해짐
            while (current != null) {
                parent = current;
                if (node->data < parent->data) {
                    current = current->left;
                }
                else {
                    current = current->right;
                }
            }
            if (node->data < parent->data) {
                parent->left = node;
            }
            else {
                parent->right = node;
            }
            cout << "Inserted " << node->data << endl;
        }
    }
 
    TreeNode<T>* getRoot() {
        return root;
    }
 
    void preorder(TreeNode<T>* current) {
        if (current != null) {
            visit(current);
            preorder(current->left);
            preorder(current->right);
        }
    }
 
    void visit(TreeNode<T>* current) {
        cout << current->data << " ";
    }
 
    TreeNode<T>* search(TreeNode<T>* current, T data) {
        if (current == null) return null;
        if (data == current->data) {
            return current;
        }
        else if (data < current->data) {
            search(current->left, data);
        }
        else {
            search(current->right, data);
        }
    }
};
 
int main() {
    Tree<int> tree(8);
    tree.buildSearchTree();
    // 만들어진 Tree 출력하기
    // 8 3 2 5 10 14 11 16
    cout << "Preorder >> ";
    tree.preorder(tree.getRoot());
    cout << endl;
 
    // Tree에 4 넣고, 확인
    tree.insertNode(new TreeNode<int>(4));
    cout << "Preorder >> ";
    tree.preorder(tree.getRoot());
    cout << endl;
 
    // Tree에서 노드 찾기
    int number;
    cout << "Input number to search >> ";
    cin >> number;
 
    TreeNode<int>* found = tree.search(tree.getRoot(), number);
 
    if (found != null) {
        cout << "Found node." << endl;
        cout << *found;
    }
    else {
        cout << "Not found node." << endl;
    }
 
}

구현 결과

찾을 노드 데이터로 5를 넣었을 땐 정상적으로 찾아지고, 해당 노드의 정보를 출력해 준다.

5는 오른쪽 자식 노드가 없으므로 오른쪽 노드는 출력되지 않은 모습니다.

찾을 노드 데이터로 239를 넣었더니 못찾았다고 정상 수행된다.