Problem Solving using C++

Algorithm Study using C++

二叉搜索树操作(3)----非递归遍历

应用队列(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;
}


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


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


My Links

Blog Stats

常用链接

留言簿(1)

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜