# Problem Solving using C++

Algorithm Study using C++

## 二叉搜索树操作(2)--其他

#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;
}

posted on 2007-08-24 12:35 Kingoal Lee's Alogrithm Study using cplusplus 阅读(125) 评论(0)  编辑 收藏 引用

### Blog Stats

• 随笔 - 19
• 文章 - 0
• 评论 - 2
• Trackbacks - 0

•