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

            二叉搜索樹操作(1)----生成

            二叉搜索樹是專門有利于搜索(時間復雜度為logn)的二叉樹。
            生成一棵二叉搜索樹關鍵是不斷地插入數(shù)據(jù)到該樹中,若當前的root為NULL,則當前插入的節(jié)點為root,否則比較左右樹插入,直到為NULL為之。
            二叉搜索樹的插入代碼為:
            void BST_Insert(int key)
            {
                構(gòu)建當前節(jié)點current,初始化current,設置其value=key,左右父節(jié)點都為NULL;
               //用x,y兩個指針來跟蹤current放置的位置
               y=NULL;
              x=root;

              while(x)//x有下面的節(jié)點時
                {  
                     y=x;
                     x的key和當前參數(shù)里面的key做對比,若大于當前key,則x=left[x],否則x=right[x];
                }

              比較y和NULL的關系,若y==NULL,則root=NULL,有root=current;
              設置parent[current]=y;
              比較current的key和y的key的大小,若大,則left[y]=current,否則right[y]=current;
            //插入完畢
            }
            使用代碼表示為:
            #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;
                
                
            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);
                }
            }

            int main(int argc,char* argv[])
            {
                BST_Build();
                BST_Inorder_Walk(root);
                BST_Delete(root);
                
                cout
            <<endl;
                system(
            "pause");
                
            return 0;
            }


            posted on 2007-08-24 09:19 Kingoal Lee's Alogrithm Study using cplusplus 閱讀(544) 評論(0)  編輯 收藏 引用

            My Links

            Blog Stats

            常用鏈接

            留言簿(1)

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            亚洲精品国产综合久久一线| 久久久精品国产免大香伊| 色狠狠久久AV五月综合| 97久久综合精品久久久综合| 青青热久久综合网伊人| 人妻精品久久久久中文字幕| 亚洲伊人久久精品影院| 久久久久国产精品| 久久久一本精品99久久精品88| 亚洲精品无码专区久久久 | 日本一区精品久久久久影院| 国产一区二区精品久久凹凸 | 久久精品国产欧美日韩99热| 欧美大香线蕉线伊人久久| 国产日韩久久免费影院| 一本久久a久久精品亚洲| 久久免费视频一区| 久久夜色tv网站| 久久99精品国产自在现线小黄鸭| 狠狠精品干练久久久无码中文字幕 | 久久亚洲精品国产精品| 亚洲日本久久久午夜精品| 九九久久99综合一区二区| 久久精品国产色蜜蜜麻豆| 精品久久人人妻人人做精品| 久久精品国产影库免费看| 久久久一本精品99久久精品88| 中文字幕无码久久精品青草| 激情综合色综合久久综合| 国产国产成人精品久久| AV无码久久久久不卡网站下载 | 四虎国产永久免费久久| 99久久免费国产精精品| 国产精品免费福利久久| 99精品国产在热久久无毒不卡| 99久久无色码中文字幕人妻| 国产aⅴ激情无码久久| 99久久国产宗和精品1上映| 久久狠狠爱亚洲综合影院| 无码人妻久久一区二区三区蜜桃| 久久福利资源国产精品999|