• <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++

            二叉搜索樹操作(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 閱讀(314) 評論(0)  編輯 收藏 引用

            My Links

            Blog Stats

            常用鏈接

            留言簿(1)

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            精品国产乱码久久久久久人妻| 亚洲午夜久久久| 久久久久久久波多野结衣高潮| 怡红院日本一道日本久久| 久久综合久久久| 一个色综合久久| 久久综合狠狠综合久久激情 | 开心久久婷婷综合中文字幕| 精品久久久无码21p发布| 精品99久久aaa一级毛片| 久久精品中文字幕一区| 久久精品国产亚洲沈樵| 四虎国产精品成人免费久久| 狠狠色丁香婷综合久久| 中文字幕久久久久人妻| 久久99精品久久久久久野外| 久久精品a亚洲国产v高清不卡| 色婷婷狠狠久久综合五月| 狠狠干狠狠久久| 99精品久久精品| 日产精品久久久一区二区| 欧美一区二区久久精品| 国产精品xxxx国产喷水亚洲国产精品无码久久一区 | 国产精品久久国产精麻豆99网站| 欧美一级久久久久久久大| 久久精品国产精品青草| 精品久久无码中文字幕| 久久夜色精品国产噜噜噜亚洲AV | 中文字幕久久精品无码| 久久精品国产WWW456C0M| 日本久久久久久中文字幕| 久久久精品人妻一区二区三区蜜桃 | 精品久久久久久无码国产| 久久精品国产亚洲AV无码麻豆| 中文字幕无码av激情不卡久久 | 亚洲精品无码久久千人斩| 亚洲国产成人精品久久久国产成人一区二区三区综 | 久久精品国产福利国产秒| 久久精品男人影院| 91精品免费久久久久久久久| 精品亚洲综合久久中文字幕|