# Problem Solving using C++

Algorithm Study using C++

## 二叉搜索树操作(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;
}

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

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

•