• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            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 閱讀(185) 評論(0)  編輯 收藏 引用

            My Links

            Blog Stats

            常用鏈接

            留言簿(1)

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            伊人久久大香线蕉综合影院首页| 亚洲国产欧洲综合997久久| 亚洲国产精品久久久久久| 精品国产综合区久久久久久| www亚洲欲色成人久久精品| 久久一区二区免费播放| 日韩精品久久久久久久电影蜜臀| 国产∨亚洲V天堂无码久久久 | 模特私拍国产精品久久| 亚洲欧美日韩久久精品第一区| 精品综合久久久久久97超人| 日日狠狠久久偷偷色综合96蜜桃| 国内精品久久久久国产盗摄| 国内精品久久久久影院亚洲| 久久99毛片免费观看不卡 | 国产成人综合久久久久久| 麻豆久久久9性大片| 99久久精品国产毛片| 久久久久人妻一区精品色| 日韩十八禁一区二区久久| 91精品国产91久久| 91精品国产高清久久久久久io| 久久精品中文字幕有码| 久久久综合九色合综国产| 亚洲色欲久久久综合网东京热 | 国产精品一久久香蕉国产线看| 模特私拍国产精品久久| 久久国产乱子伦精品免费午夜| 丰满少妇高潮惨叫久久久| 无码国内精品久久人妻| 中文字幕日本人妻久久久免费| 亚洲精品高清国产一久久| 亚洲国产精品嫩草影院久久| 亚洲色欲久久久综合网东京热| 久久久久国产一级毛片高清板| 亚洲AV乱码久久精品蜜桃| 久久久久亚洲AV无码专区首JN| 久久影院亚洲一区| 亚洲国产高清精品线久久 | 久久亚洲国产精品成人AV秋霞| 中文字幕精品久久|