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 阅读(120) 评论(0)  编辑 收藏 引用


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


My Links

Blog Stats

常用链接

留言簿(1)

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜