• <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é)點(diǎn)為root,否則比較左右樹插入,直到為NULL為之。
            二叉搜索樹的插入代碼為:
            void BST_Insert(int key)
            {
                構(gòu)建當(dāng)前節(jié)點(diǎn)current,初始化current,設(shè)置其value=key,左右父節(jié)點(diǎn)都為NULL;
               //用x,y兩個指針來跟蹤current放置的位置
               y=NULL;
              x=root;

              while(x)//x有下面的節(jié)點(diǎn)時
                {  
                     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)

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            国产精品久久久久久久app| 久久久久中文字幕| 亚洲AV无码久久精品色欲| 亚洲国产精品无码久久久蜜芽 | 久久久久久久97| 久久这里只精品国产99热| 久久久综合香蕉尹人综合网| 国产美女亚洲精品久久久综合| 久久久精品国产sm调教网站| 欧美精品一区二区精品久久| 久久人人爽人人爽人人片av麻烦| av国内精品久久久久影院| 亚洲另类欧美综合久久图片区| 久久狠狠高潮亚洲精品 | 性欧美丰满熟妇XXXX性久久久 | 伊人久久综在合线亚洲2019| 国产精品久久久久久久人人看| 97久久超碰国产精品旧版| 亚洲人成无码www久久久| 情人伊人久久综合亚洲| 亚洲AV无码久久精品成人| 一本色道久久综合| 久久久久久一区国产精品| 99久久免费只有精品国产| 精品久久久久久无码专区| 亚洲AV日韩AV永久无码久久| 久久久久久国产精品美女| 伊人久久大香线蕉AV一区二区| 精品人妻伦九区久久AAA片69| 国产精品久久久久久一区二区三区| 亚洲中文字幕无码久久综合网| 欧美亚洲国产精品久久| 性做久久久久久久久老女人 | 久久精品aⅴ无码中文字字幕不卡| 思思久久精品在热线热| 亚洲欧美精品一区久久中文字幕| 精品久久久久国产免费| 国内精品欧美久久精品| 久久婷婷人人澡人人| 亚洲欧美日韩精品久久亚洲区| 欧洲国产伦久久久久久久|