• <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)----生成

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

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

              比較y和NULL的關(guān)系,若y==NULL,則root=NULL,有root=current;
              設(shè)置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 閱讀(543) 評論(0)  編輯 收藏 引用


            只有注冊用戶登錄后才能發(fā)表評論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            My Links

            Blog Stats

            常用鏈接

            留言簿(1)

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            99久久99这里只有免费费精品| 欧美大战日韩91综合一区婷婷久久青草 | 99久久99久久精品国产片果冻| 久久夜色精品国产亚洲| 久久午夜无码鲁丝片秋霞| 奇米影视7777久久精品| 91精品国产91久久| 久久久久久午夜精品| 久久人人爽人人爽人人片av高请| 2022年国产精品久久久久| 精品免费久久久久国产一区| 免费久久人人爽人人爽av| 伊人色综合久久| 久久久无码人妻精品无码| 久久精品国产亚洲Aⅴ香蕉 | 国产福利电影一区二区三区久久老子无码午夜伦不 | 亚洲精品无码久久不卡| 国产亚洲综合久久系列| 久久久久久久综合日本| 久久精品国产99久久久| 亚洲中文字幕伊人久久无码| 国产午夜免费高清久久影院| 一本久久精品一区二区| 精品国产乱码久久久久久浪潮| 久久一日本道色综合久久| 四虎国产精品成人免费久久| 91秦先生久久久久久久| 777米奇久久最新地址| 伊人久久大香线蕉av不卡| 亚洲国产精品综合久久一线| 国产精品伦理久久久久久| 久久福利青草精品资源站| 久久久久久久亚洲Av无码| 99久久精品国产一区二区 | 久久夜色精品国产亚洲| 亚洲精品无码久久久久AV麻豆| 91精品国产91久久久久久| 久久99国产精一区二区三区| 2021精品国产综合久久| 久久久久久久尹人综合网亚洲| 久久91亚洲人成电影网站|