|자료구조| 3 | BinSearchTree | 이진 탐색 트리

이진 탐색 트리 구현

이진 탐색트리 구현은 다음 깃허브를 참고했습니다

https://gist.github.com/harish-r/a7df7ce576dda35c9660

Visual Studio 솔루션 구성

---

구현부

노드 - 헤더 : Node.h

#pragma once
class Node
{
	friend class BinSearchTree;
public:
	int data;
	Node* lch;
	Node* rch;
};

이진 탐색 트리 - 헤더 : BinSearchTree.h

#pragma once
#include "Node.h"
class BinSearchTree
{
	friend class Node;
private:
	Node* mRoot;
	Node* mMakeEmpty(Node *_t);
	Node* mInsert(Node* _t, int _x);
	Node* mFindMin(Node *t);
	Node* mFindMax(Node *t);
	Node* mFind(Node *t, int _x);
	Node* mRemove(Node *t,Node *par, int _x);
	void mPreorder(Node* _t);
	void mInorder(Node* _t);
	void mPostorder(Node* _t);

public:
	BinSearchTree();
	~BinSearchTree();
	void insert(int _x);
	void remove(int _x);
	void search(int _x);
	void preorder();
	void inorder();
	void postorder();
};

이진 탐색 트리 - 메소드 : BinSearchTree.cpp

#include <bits/stdc++.h>
#include "BinSearchTree.h"
#include "Node.h"
using namespace std;

Node* BinSearchTree::mMakeEmpty(Node* _t) {
	//인풋은 트리 전체이다
	//재귀적으로 노드를 L R "Del" 하면서 삭제한다
		//삭제는 동적할당, 동적삭제 사용
	if (_t == NULL)
		return NULL;
	else {
		mMakeEmpty(_t->lch);
		mMakeEmpty(_t->rch);
		Node* curNode = _t;
		delete curNode;
		return NULL;
	}
}

Node* BinSearchTree::mInsert(Node* _t, int _x) {
	//인풋은 트리 전체이다.
	if (_t == NULL) {
		// 재귀적으로 왔는데 현재 위치에 Node가 없다면,또는 트리가 없다면
			//노드(트리) 생성
		_t = new Node;
		_t->data = _x;
		_t->lch = _t->rch = NULL;
	}
	// 트리가 존재한다면 
	//현재 노드와 비교하면서 재귀적으로
	//노드 들어간다.
	else if (_x < _t->data) {
		_t->lch = mInsert(_t->lch, _x);
	}
	else if (_t->data < _x) {
		_t->rch = mInsert(_t->rch, _x);
	}
	return _t;
}
Node* BinSearchTree::mFindMin(Node* _t){
	//이진탐색트리는 늘 죄측이 작은 숫자이다.
	if (_t == NULL)
		return NULL;
	else if (_t->lch == NULL)
		return _t;
	return mFindMin(_t->lch);
}
Node* BinSearchTree::mFindMax(Node* _t){
	//이진탐색트리는 늘 우측이 큰 숫자이다.
	if (_t == NULL)
		return NULL;
	else if (_t->rch == NULL)
		return _t;
	return mFindMax(_t->rch);
}
Node* BinSearchTree::mFind(Node* _t, int _x) {
	//현재 노드의 대소비교를 하며 수를 찾아간다.
	if (_t == NULL)
		return NULL;
	else if (_t->data == _x)
		return _t;
	else if (_x < _t->data) {
		return mFind(_t->lch, _x);
	}
	else if (_t->data < _x){
		return mFind(_t->rch, _x);
	}
}
Node* BinSearchTree::mRemove(Node* _t, Node *_par, int _x) {
	Node* temp;
	if (_t == NULL)
		return NULL;
	else if (_x < _t->data)
		_t->lch = mRemove(_t->lch, _par,_x);
	else if (_x > _t->data)
		_t->rch = mRemove(_t->rch, _par,_x);
	else if (_t->lch && _t->rch)
	{
		temp = mFindMin(_t->rch);
		_t->data = temp->data;
		_t->rch = mRemove(_t->rch, _par, _t->data);
	}
	else
	{
		temp = _t;
		if (_t->lch == NULL)
			_t = _t->rch;
		else if (_t->rch == NULL)
			_t = _t->lch;
		delete temp;
	}

	return _t;
}

BinSearchTree::BinSearchTree() {
	mRoot = NULL;
}
BinSearchTree::~BinSearchTree() {
	mRoot = mMakeEmpty(mRoot);
}
void BinSearchTree::insert(int _x) {
	mRoot = mInsert(mRoot, _x);
}
void BinSearchTree::remove(int _x) {
	mRoot = mRemove(mRoot, NULL, _x);
}
void BinSearchTree::search(int _x) {
	mRoot = mFind(mRoot ,_x);
}

void BinSearchTree::mPreorder(Node *_t) {
	if (_t == NULL)
		return;
	cout << _t->data << ' ';
	mPreorder(_t->lch);
	mPreorder(_t->rch);
}
void BinSearchTree::mInorder(Node* _t) {
	if (_t == NULL)
		return;
	mInorder(_t->lch);
	cout << _t->data << ' ';
	mInorder(_t->rch);
}
void BinSearchTree::mPostorder(Node* _t) {
	if (_t == NULL)
		return;
	mPostorder(_t->lch);
	mPostorder(_t->rch);
	cout << _t->data << ' ';
}
void BinSearchTree::preorder() {
	mPreorder(mRoot);
	cout << '\n';
};
void BinSearchTree::inorder() {
	mInorder(mRoot);
	cout << '\n';
}
void BinSearchTree::postorder() {
	mPostorder(mRoot);
	cout << '\n';
}

---

적용부

main.cpp

#include <bits/stdc++.h>
#include "BinSearchTree.h"
using namespace std;
/*
** Binary Search Tree implementation in C++
** Harish R
** Edit By DogGuyMan
*/

int main() {
    BinSearchTree t;
    t.insert(20);
    t.insert(25);
    t.insert(15);
    t.insert(10);
    t.insert(30);
    t.inorder();
    t.preorder();
    t.postorder();
    cout << '\n';
    t.remove(20);
    t.inorder();
    t.preorder();
    t.postorder();
    cout << '\n';
    t.remove(25);
    t.inorder();
    t.preorder();
    t.postorder();
    t.remove(30);
    t.inorder();
    t.preorder();
    t.postorder();
    cout << '\n';
    return 0;
}