关于二叉搜索树搜索的递归算法

3

#include <iostream>
#include <cstdlib>
#include <queue>
#include <stack>
#include <algorithm>

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

void BST_Layer_Walk()
{
queue<BST*> queue;
BST* p;
queue.push(root);

while(!queue.empty())
{
p=queue.front();

queue.pop();
if(p->left)
queue.push(p->left);
if(p->right)
queue.push(p->right);

cout<<p->key<<" ";
}

cout<<endl;
}

void Inorder_Walk(BST* node=root)
{
stack<BST*> stk;

while(!stk.empty()||node)
{
if(node)
{
stk.push(node);
node=node->left;
}
else
{
node=stk.top();
cout<<node->key<<" ";
stk.pop();
node=node->right;
}
}
}

void Preorder_Walk(BST* node=root)
{
stack<BST*> stk;

while(!stk.empty()||node)
{
if(node)
{
cout<<node->key<<" ";
stk.push(node);
node=node->left;
}
else
{
node=stk.top();
stk.pop();
node=node->right;
}
}
}

void Postorder_Walk(BST* node=root)
{
stack<BST*> stk;
BST* p;
int flag = 0;//0 stands for left, 1 stands for right

do
{
while(node)
{
stk.push(node);
node=node->left;
}

p=NULL;
flag=0;

while(!stk.empty()&&(flag==0))
{
node=stk.top();
if(node->right==p)
{
stk.pop();
p=node;
cout<<node->key<<" ";
}
else
{
node= node->right;
flag=1;
}
}
}while(!stk.empty());
}

int main(int argc,char* argv[])
{
int input;

BST_Build();

cout<<"Inorder Walk:"<<endl;
//BST_Inorder_Walk(root);
Inorder_Walk();
cout<<endl;

cout<<"Preorder Walk:"<<endl;
BST_Preorder_Walk(root);
cout<<endl;

cout<<"Stack Preorder Walk:"<<endl;
Preorder_Walk(root);
cout<<endl;

cout<<"Postorder Walk:"<<endl;
BST_Postorder_Walk(root);
cout<<endl;

cout<<"Stack Postorder Walk:"<<endl;
Postorder_Walk(root);
cout<<endl;

cout<<"Layer Walk:"<<endl;
BST_Layer_Walk();

BST_Delete(root);

cout<<endl;
system("pause");
return 0;
}