이진탐색트리 구현하기(C++)

이진탐색트리에 노드를 삽입/삭제/중위순회로 출력하는 코드입니다!

중요하게 봐야 할 곳은,
1. 아직 트리가 만들어지지 않았을 때 노드를 삽입하는 경우
2. 트리 삭제 시
노드를 찾았는데,
1.자식이 0개라면 node를 지운 후 해당 node를 nullpointer로 바꿔준다.
2.왼쪽 자식만 있다면 왼쪽 자식을 해당 노드로 바꿔준 후 찾았던 걸 삭제한다.
3.오른쪽 자식만 있다면 오른쪽 자식을 해당 노드로 바꿔준 후 찾았던 걸 삭제한다.
4.왼쪽 오른쪽 자식 둘 다 있다면 왼쪽 노드 중에서 가장 큰 값을 찾아서 그 노드로 바꿔준다.
3. 노드의 왼쪽 자식/오른쪽 자식으로 이동할 때 pointer 값!! (null pointer도 잘 생각해주자)

main.cpp 파일

#include "binarysearchtree.h"


int main() {
    BinarySearchTree<int>* BST = new BinarySearchTree<int>();
    int a = 0;
    int key;
    char value;
    while (a != 5) { //5라고 쓰이지 않을 때까지 시행한다.
        cin >> a; 
        if (a == 1) {
            cin >> key >> value; //value와 key를 입력받아 BST에 넣는다.
            BST->AddNode(key, value);
        }
        else if (a == 2) {
            cin >> key; //key를 입력받아 BST에서 그 value를 찾는다.
            BST->SearchValue(key);
        }
        else if (a == 3) {
            cin >> key; //value를 입력받아 BST에서 해당 노드를 지운다.
            BST->RemoveNode(key);
        }
        else if (a == 4) { //BST에 있는 값들을 보여준다.
            BST->Display(); cout << endl;
        }
    }
    if (a == 5) {
        cout << "종료되었습니다.";
    }
    return 0;
}

binarysearchtree.h 파일

#include <iostream>
using namespace std;

template <typename T>
struct Node //이진트리이므로 자식은 왼쪽/오른쪽 두 개이다. 노드 한 개는 value와 key를 갖는다.
{
    Node* left;  
    Node* right;
    T key;
    char value;
};

template <typename T>
class BinarySearchTree
{
public:
    BinarySearchTree() :root(nullptr) {};//루트는 포인터를 Null로 설정한다.
    ~BinarySearchTree() {};

    void AddNode(T _key, T _value); //value와 key를 이용해서 노드를 추가하는 함수
    bool SearchValue(T _value); //value를 이용해서 노드를 탐색하는 함수 -> bool형이므로 True/False의 반환값을 갖는다.
    void RemoveNode(T _value); //Node를 제거하는 함수 
    void Display(); //Node들을 보여주는 함수


private: //트리에는 root노드가 있다.
    Node<T>* root; //root 노드


    void Inorder(Node<T>* current) //중위순회를 이용해서 node를 보여주는 함수
    {
        if (current != nullptr) //만약 current가 nullpointer가 아니라면
        {
            Inorder(current->left); //left먼저 방문
            cout << current->value << " "; //이후 중간 값 출력
            Inorder(current->right); //이후 right 방문
        }
    }
    Node<T>* SearchMaxNode(Node<T>* node) //최대 노드값을 찾는 함수
    {
        if (node == NULL) //트리가 아예 만들어지지 않았을 시
            return NULL;

        while (node->right != NULL)
        {
            node = node->right;
        }
        return node;
    }

    Node<T>* RemoveSeqence(Node<T>* node, T _vaule); //삭제하는 과정의 함수

};


template <typename T>
Node<T>* BinarySearchTree<T>::RemoveSeqence(Node<T>* node, T _key)
{
    if (node == nullptr) return node; //node 포인터가 NULL이면 return한다. (트리가 아직 안 만들어졌거나 트리를 아예 벗어났을 경우)
    else if (node->key > _key)
        node->left = RemoveSeqence(node->left, _key); //종착지보다 찾으려는 value값이 작으면 left로 내려간다.
    else if (node->key < _key)
        node->right = RemoveSeqence(node->right, _key); //종착지보다 찾으려는 value값이 크면 right로 내려간다.
    else
    {
        Node<T>* ptr = node; //해당 노드를 pointer로 가져온다.
        //(자식 0개) 왼쪽 노드도 없고 오른쪽 노드도 없을 때
        if (node->right == nullptr && node->left == nullptr)
        {
            delete node;
            node = nullptr;
        }
        //(자식 1개) 왼쪽 노드만 있을 때
        else if (node->right == nullptr)
        {
            node = node->left;
            delete ptr;
        }
        //(자식 1개) 오른쪽 노드만 있을 때
        else if (node->left == nullptr)
        {
            node = node->right;
            delete ptr;
        }
        //(자식 2개) 왼쪽 노드중 가장 큰 값 찾아 부모노드로 바꾸기
        else
        {
            ptr = SearchMaxNode(node->left);
            node->key = ptr->key;
            node->left = RemoveSeqence(node->left, ptr->key);
        }
    }
    return node;
}

template <typename T>
void BinarySearchTree<T>::RemoveNode(T _key)
{
    Node<T>* ptr = root; //루트 포인터를 가져와서 함수에 넣어준다.
    RemoveSeqence(ptr, _key);
}

template<typename T>
void BinarySearchTree<T>::Display() //노드를 차례대로 보여주는 함수는 중위순회로 구현한다.
{
    Inorder(root);
}

template <typename T>
bool BinarySearchTree<T>::SearchValue(T _key)
{
    Node<T>* ptr = root; //root포인터를 저장한다.
    Node<T>* tmpRoot = nullptr; //tmpRoot를 nullpointer값으로 해서 하나 만들어 둔다.


    while (ptr != nullptr) //pointer가 null pointer가 아닐 때까지, 즉 leaf노드를 넘기지 않을 때까지
    {
        if (ptr->key == _key) //찾으려는 값이 정확히 해당 값일 때
        {
            cout << ptr-> value << endl;
            return true;
        }
        else if (ptr->key > _key) //찾으려는 값이 해당 값보다 작을 때 
            ptr = ptr->left;
        else //찾으려는 값이 해당 값보다 클 때 
            ptr = ptr->right;
    } 
    //위에 해당하는 값들을 모두 넘겨버린다면 false 반환
    cout << _key << " 값을 찾지 못했습니다." << endl;
    return false;
}

template <typename T>
void BinarySearchTree<T>::AddNode(T _key, T _value) //해당 value,key값의 노드를 추가하는 함수
{
    Node<T>* node = new Node<T>(); //새로운 node 생성
    Node<T>* tmpRoot = nullptr; //tmpRoot를 nullpointer값으로 해서 하나 만들어 둔다.

    node->key = _key; //node의 key,value를 입력된 값으로 할당해준다.
    node->value = _value;

    if (root == nullptr) //만약 root가 nullpointer라면, 즉 트리가 생성되기 전이라면 해당 node를 root로 할당해준다.
        root = node;
    else
    {
        Node<T>* ptr = root;

        while (ptr != nullptr) //트리를 벗어나기 전까지
        {
            tmpRoot = ptr; //해당 node의 pointer를 tmpRoot로 놓는다.
            if (node->key < ptr->key) //만약 넣으려는 값이 해당 ptr보다 작을 때
            {
                ptr = ptr->left; //왼쪽 노드로 간다.
            }
            else //만약 넣으려는 값이 해당 ptr보다 클 때
            {
                ptr = ptr->right; //오른쪽 노드로 간다.
            }
        }
        //넣을 위치에 대입
        if (node->key < tmpRoot->key)
            tmpRoot->left = node;
        else
            tmpRoot->right = node;
    }
}