// BST.h
#include <iostream>
using namespace std;
#define Min_sort 0
#define Max_sort 1
template<typename T>
class BST;
template<typename T>
class node{
private:
T data;
node<T> *left;
node<T> *right;
public:
node() : left(NULL), right(NULL), data(0) { }
friend class BST<T>;
};
template<typename nodetype>
class BST{
private:
node<nodetype> *root;
node<nodetype> *P; // Get Search Parent
public:
node<nodetype> *input(int input_d);
node<nodetype> *Search(int input_d);
node<nodetype> *GetLeftChild(node<nodetype> *Parent);
node<nodetype> *GetRightChild(node<nodetype> *Parent);
nodetype *LtoRPrint(node<nodetype> *Parent);
nodetype *RtoLPrint(node<nodetype> *Parent);
nodetype *Print(int sort_rule);
bool del_node(int input_d);
void input(nodetype input_arr[], int size);
};
template<typename nodetype>
node<nodetype> *BST<nodetype>::input(int input_d){
if (root == NULL){
root = new node<nodetype>;
root->data = input_d;
return root;
}
node<nodetype> *temp = Search(input_d);
if(temp->data > input_d){
temp->left = new node<nodetype>;
temp = GetLeftChild(temp);
}
else if(temp->data < input_d){
temp->right = new node<nodetype>;
temp = GetRightChild(temp);
}
temp->data = input_d;
return temp;
}
// Array Input~
template<typename nodetype>
void BST<nodetype>::input(nodetype input_arr[], int size){
if (root == NULL){
root = new node<nodetype>;
root->data = input_arr[0];
}
int cnt;
for(cnt=0; cnt < size; cnt++){
node<nodetype> *temp = Search(input_arr[cnt]);
if(temp->data > input_arr[cnt]){
temp->left = new node<nodetype>;
temp = GetLeftChild(temp);
}
else if(temp->data < input_arr[cnt]){
temp->right = new node<nodetype>;
temp = GetRightChild(temp);
}
temp->data = input_arr[cnt];
}
}
template<typename nodetype>
bool BST<nodetype>::del_node(int input_d){
node<nodetype> *del = Search(input_d);
// Search 함수는 노드를 탐색하면서 같은값을 찾게 되었을때
// 그 노드를 ret하지만, 없다면 최하위 노드를 ret하게 되므로 값을 비교해줘서
// 분기를 해줘야한다.
if(del->data != input_d)
return false;
// Case 1 : left, right NULL
if(GetLeftChild(del) == NULL && GetRightChild(del) == NULL){
if(P->left != NULL)
if(P->left->data == del->data)
P->left = NULL;
if(P->right != NULL)
if(P->right->data == del->data)
P->right = NULL;
delete del;
if(del == root)
root = NULL;
}
// Case 2 : left and right not NULL
else if(GetLeftChild(del) != NULL && GetRightChild(del) != NULL){
node<nodetype> *temp = del;
node<nodetype> *p_temp = del;
temp = GetRightChild(del);
while(GetLeftChild(temp) != NULL){
p_temp = temp;
temp = GetLeftChild(temp);
}
if(P->left == del){
temp->left = del->left;
P->left = temp;
}
else if(P->right == del){
temp->left = del->left;
P->right = temp;
}
else if(P == del){
//P->data = temp->data;
P->right = temp->right;
}
delete del;
}
// Case 3 : have one Child
else{
if(P->left == del){
if(GetLeftChild(del) != NULL)
P->left = GetLeftChild(del);
else
P->left = GetRightChild(del);
}
else if(P->right == del)
if(GetLeftChild(del) != NULL)
P->right = GetLeftChild(del);
else
P->right = GetRightChild(del);
delete del;
}
return true;
}
template<typename nodetype>
node<nodetype> *BST<nodetype>::Search(int input_d){
node<nodetype> *temp = root;
P = root;
while(temp->left != NULL || temp->right != NULL){
if(temp->data > input_d && GetLeftChild(temp) != NULL){
P = temp;
temp = GetLeftChild(temp);
}
else if(temp->data < input_d && GetRightChild(temp) != NULL){
P = temp;
temp = GetRightChild(temp);
}
else
break;
}
return temp;
}
template<typename nodetype>
node<nodetype> *BST<nodetype>::GetLeftChild(node<nodetype> *Parent){
return Parent->left;
}
template<typename nodetype>
node<nodetype> *BST<nodetype>::GetRightChild(node<nodetype> *Parent){
return Parent->right;
}
template<typename nodetype>
nodetype *BST<nodetype>::Print(int sort_rule){
if(sort_rule == Min_sort)
return LtoRPrint(root);
else if(sort_rule == Max_sort)
return RtoLPrint(root);
}
template<typename nodetype>
nodetype *BST<nodetype>::LtoRPrint(node<nodetype> *Parent){
if(Parent == NULL)
return NULL;
LtoRPrint(Parent->left);
cout << Parent->data << endl;
LtoRPrint(Parent->right);
}
template<typename nodetype>
nodetype *BST<nodetype>::RtoLPrint(node<nodetype> *Parent){
if(Parent == NULL)
return NULL;
RtoLPrint(Parent->right);
cout << Parent->data << endl;
RtoLPrint(Parent->left);
}
//BST.cpp
#include <iostream>
#include <cstdlib>
#include "BST.h"
using namespace std;
int main()
{
BST<int> *bst = new BST<int>;
int arr[1000], i;
srand(time(NULL));
for(i = 0; i < 1000; i++)
arr[i] = rand() % 10000 + 1;
bst->input(arr,1000);
bst->Print(Min_sort);
delete bst;
return 0;
}
'자료' 카테고리의 다른 글
| Heap 기반 free() & malloc() Exploit 작성하기 (0) | 2015.12.26 |
|---|---|
| 비초기화 정적 변수의 오버플로우에 대한 Exploit의 제작기법(1) (0) | 2015.12.26 |
| [Python] Rop Exploit (0) | 2015.12.05 |
| [Python] Blind SQL Injection (0) | 2015.12.05 |
| [자료구조] Stack (0) | 2015.12.05 |
KuroNeko_
KuroNeko
Headers.h
MIPS assemble.pdf