应用队列(queue)和栈(stack)对二叉搜索树进行非递归遍历
应用队列queue的是BFS,栈stack的是DFS
代码为:
#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;
}