#include <iostream>
#include <cstdlib>
using namespace std;
#ifndef NULL
#define NULL 0
#endif
#ifndef MAXSIZE
#define MAXSIZE 10
#endif
typedef struct BST//Binary Search Tree
{
int key;
//maybe there are some other satellites
struct BST* left;
struct BST* right;
struct BST* parent;
} BST;
BST* root=NULL;
void BST_Insert(int key)//add value key to the Binary Search Tree
{
BST* y=NULL;//y records the parent node
BST* x=root;//x records the current node
BST* node = new BST();
node->key = key;
node->left = NULL;
node->right = NULL;
node->parent = NULL;
while(x!=NULL)
{
y=x;
if(key<x->key)
x=x->left;
else
x=x->right;
}
node->parent=y;
if(y==NULL)
root = node;
else
{
if(key<y->key)
y->left=node;
else
y->right=node;
}
}
void BST_Delete(BST* p)
{
if(p)
{
BST_Delete(p->left);
BST_Delete(p->right);
delete p;
}
}
void BST_Build()
{
int temp;
cout<<"Original Input:"<<endl;
for(int i=0;i<MAXSIZE;i++)
{
temp=rand()%MAXSIZE;
cout<<temp<<" ";
BST_Insert(temp);
}
cout<<endl;
}
void BST_Inorder_Walk(BST* p)
{
if(p)
{
BST_Inorder_Walk(p->left);
cout<<p->key<<" ";
BST_Inorder_Walk(p->right);
}
}
void BST_Preorder_Walk(BST* p)
{
if(p)
{
cout<<p->key<<" ";
BST_Preorder_Walk(p->left);
BST_Preorder_Walk(p->right);
}
}
void BST_Postorder_Walk(BST* p)
{
if(p)
{
BST_Postorder_Walk(p->left);
BST_Postorder_Walk(p->right);
cout<<p->key<<" ";
}
}
BST* BST_Search(int key)
{
BST* x=root;
while(x)
{
if(x->key==key)
return x;
else
if(x->key>key)
x=x->left;
else
x=x->right;
}
return NULL;
}
BST* BST_Min(BST* p=root)
{
//BST* p = root;
while(p->left)
{
p=p->left;
}
return p;
}
BST* BST_Max(BST* p=root)
{
//BST* p = root;
while(p->right)
{
p=p->right;
}
return p;
}
BST* BST_Successor(int key)
{
BST* p = BST_Search(key);
BST* y;
if(p)
{
if(p->right)
{
return BST_Min(p->right);
}
y=p->parent;
while(y&&(y->right==p))
{
p=y;
y=y->parent;
}
return y;
}
return NULL;
}
BST* BST_Predecessor(int key)
{
BST* p = BST_Search(key);
BST* y;
if(p)
{
if(p->left)
return BST_Max(p->left);
y=p->parent;
while(y&&(y->left==p))
{
p=y;
y=y->parent;
}
return y;
}
return p;
}
BST* BST_Delete(int key)
{
BST* p = BST_Search(key);
BST* y,*x;
if(p)
{
if(!p->left||!p->right)
{
y=p;
}
else
y=BST_Successor(key);
if(y->left)
x=y->left;
else
x=y->right;
if(x!=NULL)
x->parent=y->parent;
if(!y->parent)
root=x;
else
{
if(y==y->parent->left)
y->parent->left=x;
else
y->parent->right=x;
}
if(y!=p)
p->key=y->key;
return y;
}
return p;
}
int main(int argc,char* argv[])
{
int input;
BST_Build();
BST_Delete(7);
cout<<"Inorder Walk:"<<endl;
BST_Inorder_Walk(root);
cout<<endl;
cout<<"Preorder Walk:"<<endl;
BST_Preorder_Walk(root);
cout<<endl;
cout<<"Postorder Walk:"<<endl;
BST_Postorder_Walk(root);
cout<<endl;
cout<<"Min: "<<BST_Min()->key<<endl;
cout<<"Max: "<<BST_Max()->key<<endl;
while(1)
{
cin>>input;
if(input==-1)
break;
BST* p;
if(p=BST_Search(input))
{
cout<<"Parent="<<(p->parent)->key<<endl;
if(p->left)
cout<<"Left:"<<p->left->key<<endl;
if(p->right)
cout<<"Right:"<<p->right->key<<endl;
}
else
{
cout<<"Not found!"<<endl;
break;
}
if(p=BST_Predecessor(input))
{
cout<<"Predecessor:"<<p->key<<endl;
}
if(p=BST_Successor(input))
{
cout<<"Successor:"<<p->key<<endl;
}
}
BST_Delete(root);
cout<<endl;
system("pause");
return 0;
}