구현 - 이진 탐색 트리

순회 : 재귀

탐색 : 반복

삭제 : 반복

삽입 : 반복

삭제시의 처리는 조금 생각해봐야한다.

1. 단말 노드일 때 -> 그냥 삭제, 부모의 링크 nullptr 초기화 필요

2. 자식 노드가 하나일 때 -> 삭제하고 부모의 링크를 자식에 연결

3. 자식 노드가 둘일 때 ->

오른쪽 자식의 맨 왼쪽 노드의 값을 기존 삭제할 노드에 덮어씌우고 삭제.

오른쪽 자식에게 왼쪽 노드가 없다면 오른쪽 자식 삭제.

삭제하기전 오른쪽 자식이 있는지 체크하고 연결

마지막에 간단하게 레벨별로 출력해보고 싶어서 레벨필드를 추가해봤음

main.cpp

#include "BST.h"

void main()

{

BSearchTree bst;

bst.insert(8, "팔");

bst.insert(3, "삼");

bst.insert(10, "십");

bst.insert(1, "일");

bst.insert(6, "육");

bst.insert(14, "십사");

bst.insert(9, "구");

bst.insert(13, "십삼");

bst.display();

 

cout << endl;

cout << "삭제 : 1" << endl << endl;

bst.erase(1);

bst.display();

cout << endl;

cout << "삭제 : 10" << endl << endl;

bst.erase(10);

bst.display();

cout << endl;

cout << "삭제 : 8" << endl << endl;

bst.erase(8);

bst.display();

cout << endl;

cout << "삭제 : 3" << endl << endl;

bst.erase(3);

bst.display();

cout << endl;

cout << "삭제 : 13" << endl << endl;

bst.erase(13);

bst.display();

cout << endl;

cout << "삭제 : 9" << endl << endl;

bst.erase(9);

bst.display();

cout << "\n모두 삭제\n\n";

bst.clear();

bst.display();

_CrtDumpMemoryLeaks();

}

BST.h

#pragma once

#include "BSubTree.h"

using namespace std;

class BSearchTree

{

BSubTree* _root{};

public:

bool isEmpty() { return _root == nullptr; }

void insert(int key, string data);

void erase(int key);

void display();

void clear();

};

BST.cpp

#include "BST.h"

void BSearchTree::insert(int key, string data)

{

if (isEmpty())

{

_root = new BSubTree(key, data);

_root->setLevel(0);

}

else

_root->insert(key, data);

}

void BSearchTree::erase(int key)

{

if (isEmpty()) return;

BSubTree* target = _root;

BSubTree* parent = nullptr;

while (target)

{

if (key == target->key())

{

if (target->left() && target->right()) //타겟의 자식이 둘일 때는

{

//타겟의 오른쪽 서브트리에서 제일 왼쪽에 있는 값을 찾아 그 값으로 타겟을 대체해야한다.

//t는 우측 노드로 초기화되어 왼쪽 트리 끝 값을 찾는다.

//tpre는 만약 우측 노드의 좌측 노드가 여러 레벨이 있을 때 부모를 추적하기 위해 사용된다.

BSubTree* t = target->right(); 

BSubTree* tpre = nullptr;

while (t->left())

{

tpre = t;

t = t->left();

}

target->copyField(t); //현재 target에 t의 값을 복사한다.

if (tpre)

{

//왼쪽 노드가 있었다면 tpre, 지울 왼쪽 노드의 상위 노드의 left를 바꿔줘야한다.

BSubTree* tempRight = tpre->left()->right();

delete tpre->left();

tpre->setLeft(tempRight);

}

else

{

//t의 왼쪽 노드가 없었다면 타겟의 오른쪽인 t를 지울 시간이다.

BSubTree* tempRight = t->right();

delete t;

target->setRight(tempRight);

}

}

//자식이 하나일 때는 해당 자식으로 타겟을 대체한다.

else if (target->left() || target->right())

{

BSubTree* t = target->left() ? target->left() : target->right();

t->decreLevel();

if (target == _root)

_root = t;

else

parent->left() == target ? parent->setLeft(t) : parent->setRight(t);

delete target;

target = nullptr;

}

else // 자식이 없다면 이전 노드의 링크를 초기화 해주고 삭제하면 된다.

{

parent->left() == target ? parent->setLeft(nullptr) : parent->setRight(nullptr);

delete target;

target = nullptr;

}

}

else if (key < target->key()) //찾는 원소가 없을 때의 순회

{

parent = target;

target = target->left();

}

else if (key > target->key())

{

parent = target;

target = target->right();

}

}

}

void BSearchTree::display()

{

if (isEmpty()) cout << "데이터가 없습니다.\n";

else _root->print_by_level();

}

void BSearchTree::clear()

{

if (isEmpty()) return;

_root->clear();

_root = nullptr;

}

BSubTree.h

#pragma once

#include <iostream>

#include <string>

#include <queue>

using namespace std;

class BSubTree

{

int _key{};

string _value{};

BSubTree* _left{};

BSubTree* _right{};

int _level{};

public:

BSubTree() {};

BSubTree(int key, string data) : _key(key), _value(data) {};

int level() { return _level; }

int key() { return _key; }

string data() { return _value; }

BSubTree* left() { return _left; }

BSubTree* right() { return _right; }

void setLevel(int lv) { _level = lv; }

void decreLevel() { --_level; }

void setLeft(BSubTree* left) { _left = left; }

void setRight(BSubTree* right) { _right = right; }

void setKeyData(int key, string data) { _key = key; _value = data; }

void copyField(BSubTree* node) { _key = node->key(); _value = node->data(); }

void push_left(BSubTree* node);

void push_right(BSubTree* node);

void print() { cout << _key << " "; }

void print_preorder();

void print_inorder();

void print_postorder();

void print_levelorder();

void print_by_level();

size_t number_of_elem() { return number_of_elem(this);}

size_t get_height() { return get_height(this); }

size_t number_of_leaf() { return number_of_leaf(this);}

BSubTree* find(int key);

void insert(int key, string data);

bool isLeaf() { return _left == nullptr && _right == nullptr; }

void clear() { clear(this);}

private:

void clear(BSubTree* curr);

size_t number_of_elem(BSubTree* curr);

size_t get_height(BSubTree* curr);

size_t number_of_leaf(BSubTree* curr);

void print_by_level(int n);

};

BSubTree.cpp

#include "BSubTree.h"

void BSubTree::push_left(BSubTree * node)

{

_left = node;

}

void BSubTree::push_right(BSubTree * node)

{

_right = node;

}

void BSubTree::print_preorder() //VLR

{

print();

if (_left) _left->print_preorder();

if (_right) _right->print_preorder();

}

void BSubTree::print_inorder() //LVR

{

if (_left) _left->print_inorder();

print();

if (_right) _right->print_inorder();

}

void BSubTree::print_postorder() //LRV

{

if (_left) _left->print_postorder();

if (_right) _right->print_postorder();

print();

}

void BSubTree::print_levelorder()  //LRV

{

queue<BSubTree*> que;

que.push(this);

while (!que.empty())

{

BSubTree* front = que.front();

front->print();

if (front->_left) que.push(front->_left);

if (front->_right) que.push(front->_right);

que.pop();

}

}

void BSubTree::print_by_level(int n)

{

if (level() > n) return;

if (level() == n) print();

if (_left) _left->print_by_level(n);

if (_right) _right->print_by_level(n);

}

void BSubTree::print_by_level()

{

for (size_t i = 0; i < get_height(); ++i)

{

print_by_level(i);

cout << endl;

}

}

BSubTree * BSubTree::find(int key)

{

BSubTree* target = this;

while (target)

{

if (key == target->_key)

break;

else if (key < target->_key)

target = target->_left;

else

target = target->_right;

}

return target;

}

void BSubTree::insert(int key, string data)

{

BSubTree* target = this;

int level = 0;

while (target)

{

if (key == target->_key)

return;

++level;

if (key < target->_key)

{

if (target->_left)

target = target->_left;

else

{

target->_left = new BSubTree(key, data);

target->_left->setLevel(level);

}

}

else

{

if (target->_right)

target = target->_right;

else

{

target->_right = new BSubTree(key, data);

target->_right->setLevel(level);

}

}

}

}

void BSubTree::clear(BSubTree * curr)

{

if (curr->left()) clear(curr->left());

if (curr->right()) clear(curr->right());

delete curr;

}

size_t BSubTree::number_of_elem(BSubTree * curr)

{

if (!curr) return 0;

return 1 + number_of_elem(curr->_left) + number_of_elem(curr->_right);

}

size_t BSubTree::get_height(BSubTree * curr)

{

if (!curr) return 0;

size_t leftH = get_height(curr->_left);

size_t rightH = get_height(curr->_right);

size_t currH = leftH < rightH ? rightH + 1 : leftH + 1;

return currH;

}

size_t BSubTree::number_of_leaf(BSubTree * curr)

{

if (!curr) return 0;

if (!curr->_left && !curr->_right)

{

cout << curr->_key << ", ";

return 1;

}

return number_of_leaf(curr->_left) + number_of_leaf(curr->_right);

}