數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-二叉排序樹的實現(xiàn)

1、課程設(shè)計課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題目名稱二叉排序樹的實現(xiàn)學生學院應(yīng)用數(shù)學學院專業(yè)班級信息計算1班學 號學生姓名陳輝騰指導(dǎo)教師劉志煌2016年6月27日二叉排序樹的實現(xiàn)應(yīng)數(shù)14信計1班3114008104陳輝騰課程設(shè)計要求：二叉排序樹的實現(xiàn)二叉排序補充概念（也可以參考書上第九章第二節(jié)）左子樹的數(shù)據(jù)總是小于根和右子樹的數(shù)據(jù)，這種就叫做二叉排序樹，簡單一點，二叉排序樹左邊的數(shù)據(jù)小于右邊.1）編程實現(xiàn)二叉排序樹，包括生成、插入，刪除；2）對二叉排序樹進行先根、中根、和后根非遞歸遍歷；3）每次對樹的修改操作和遍歷操作的顯示結(jié)果都需要在屏幕上用樹的形狀表示出來。4）分別用二叉排序樹和數(shù)組去存儲一個班（50

2、人以上）的成員信息（至少包括學號、姓名、成績3項），對比查找效率，并說明在什么情況下二叉排序樹效率高，為什么？5）格式就要按照我們作業(yè)的要求，對數(shù)據(jù)測試，分析，總結(jié)和改進的工作要做的詳細一點。1、編程實現(xiàn)二叉排序樹，包括生成、插入、刪除;1.1數(shù)據(jù)類型定義E- typedef st ruct BiTIIode rEleniType data; /學號char名字int scorestruct EiTNode tlchildj *rchild;/左右孩子指針 E- IBiTNodej *BiTree:1.2生成一顆二叉排序樹方法一：手工輸入，遞歸生成。E Status CreateBinSart

3、 Treel (BiTree 覽T) /7先序 int id：/看做學號data, scanf &id): if (id 二二-1)T=ITOLL： else T = (BirMade nialloc (sizeof CBiTNode); i(!T)exit(OVERFLOW);T-data = id;CreateBinSortTreel(T-lchild): Great已EinScirtTr已已L:return OK:生成一顆二叉排序樹如下：這樣生成一棵二叉排序樹，就是要自己判斷每個結(jié)點應(yīng)該放在什么地方，因為二叉排 序樹規(guī)定了二叉排序樹左邊的數(shù)據(jù)小于右邊。顯然，這樣每次構(gòu)建一棵二叉排序樹都需

4、要事先 規(guī)定好一個數(shù)據(jù)元素序列，然后依次輸入。這樣的弊端就是你不細心一點就有可能構(gòu)建出一棵 錯誤的二叉排序樹一一非二叉排序樹。優(yōu)點就是可以構(gòu)建自己想要的二叉排序樹。方法二：隨機生成。 St atus CreateEinSart Tree2(BiTree &L BiTNode BiTNode , BiTree &p) T 二 tBiTree)malloc (siEeof (BiTNode) : T-data = 30: T-nanie = ,vjnev :T-score = 100：/根節(jié)點 T-lchild 二 T-rchild 二 NULL：:fuSnt i=0：lS：i+) 機數(shù)不重復(fù)，將

5、產(chǎn)生9個結(jié)點的二叉排序樹= in.t r = rarLdfMAX：/生口-舸的隨機數(shù)吊Inser-tBST tT; BiTNode r. data, p) ;/，播入一個結(jié)點。return OK :這里用到了 C+里面的rand ()函數(shù)，用于生成大于等于0的偽隨機數(shù)(每次運行產(chǎn)生的隨 機數(shù)都是固定的)。用這個函數(shù)需要使用名字空間using namespace std;同時引進 #includeo思路是：按依次插入結(jié)點來生成一棵二叉排序樹，在插入函數(shù)里進行判斷：即編寫生 成二叉排序樹的規(guī)則。另外，事先要有一堆結(jié)點(用于生成二叉排序樹)，我是事先保存在一 個數(shù)組里。然后每次產(chǎn)生一個偽隨機數(shù)(范圍

6、是0到數(shù)組長度)作為數(shù)組下標，并把對應(yīng)的該下 標的數(shù)組元素插入到要生成的二叉排序樹里。其中for循環(huán)次數(shù)就是生成二叉排序樹結(jié)點個數(shù)的最大值減1。最大是因為產(chǎn)生的偽隨 機數(shù)可能會重復(fù)，而重復(fù)的結(jié)點不再插入樹中。減1是因為根結(jié)點我事先就定義了，它的data默 認為30，默認為30的目的是因為我可以產(chǎn)生064的偽隨機數(shù)，學號范圍也是暫時定在064這 個范圍。這樣規(guī)定可以照顧生成的左右子樹盡量均衡，即靠近完全二叉排序樹。要靠近完全二 叉樹是因為到時打印一顆樹的時候，打印的層數(shù)(樹的深度)盡量少，因為到時候打印一棵樹， 深度越大就越難控制。(當然也可以把上述函數(shù)的2,3,4行注釋起來，這樣就要保證T一開

7、始是 空樹。)其中InsertBST()函數(shù)為：當樹T中不存在關(guān)建宇等于日的數(shù)據(jù)元素時，插AecEl Status InsertBST (BiTree Elenlype Sj Eilree &p) rCiSearchESKL % NULL, p) 查找不成功BiTree s = (EiTree) iTLalloc (sizeof (EiLTirude) J :s-data = e ; s-Mchild = 3-r child = NULL;if (!p)T = s插入結(jié)點*R為新的糧結(jié)點。else if LT (e3p-data) p-lch.ild = 禎插結(jié)由*目為左技子 else p-r

8、child = s;/插結(jié)點幡為右枝子 return TRUE :else return FALSE;/樹中已有關(guān)健字相同結(jié)點，不再插入在插入一個結(jié)點的函數(shù)里，首先要找一下原樹里有沒有與即將被插入的結(jié)點元素相同 的結(jié)點元素。有的話就放棄插入，沒有就進行與根結(jié)點判斷大小，小就插到它的左邊作為左孩 子，大的就到右邊。其中查找函數(shù)SearchBST()為：1-療在樹T上查找關(guān)疆字等于上毀的數(shù)據(jù)元素，若萱找成功，讓指針p 療指向該元素結(jié)點，并返回TRUE。否貝如指向萱找路徑上訪問的最 后一個結(jié)點，返回FAL血，指針f指向T的雙親，:f初始值為NULLE St at ns SearchBST(BiTre

9、e T,KeyType key, Bi Tree f,EiTree &p) if(!T) p = f; return F虹SE：查找不成功 else if EQ (ke/j T-data) (P = T ; re-turn TRITE;/查找成功 else if LT (key T-data) re-turn SearchBST (T-lctiildj key Tj p);else return SearchBST (T-rchild, keyj T,p) ;/在右子樹繼續(xù)查憑查找函數(shù)是遞歸定義，同時也用到了比較函數(shù)LT(a,b)。LT(a,b)比較函數(shù)定義如下:#defin.e EQ (aj

10、 b) ( ! strcmp (a)3 (b)#defin.e LT (aj b) (strcmp (a)j (b) 0)#def in.e LQ (a3 b) (strcmp (b) = 0)所以我用比較數(shù)值型的比較函數(shù)就夠了(學號暫時用兩位數(shù)，因為打印樹的時 還有就是用整形int可以存得下)。于是自己寫了比較函數(shù)。在比較函數(shù)里又用到了字符串比較函數(shù)strcmp(a,b)。這個函數(shù)c+里面有，只要 #include就行了。但是它比較的是字符串。由于對于我來說我的關(guān)鍵字是學號，比 較的就是學號 候占用位置少 即：E St at usstrcmp (int田iht b) (/自己是義，用于數(shù)值型

11、 return a - b;函數(shù)名字忘記改了，不能見名知義，不過沒關(guān)系了。運行結(jié)果：S3 C:W i nm 3 2c md. exe啊造一顆二只排序樹：樹形狀如下：30/21 / 、526/25/404754X58經(jīng)過驗證，是成功的生成了一棵二叉排序樹。for循環(huán)了 8次，此時生成了 9個結(jié)點， 說明產(chǎn)生的偽隨機數(shù)沒有重復(fù)，而且隨機構(gòu)造的樹也基本左右均衡。1.3對生成的二叉排序樹插入一個節(jié)點生成了一棵二叉排序樹，接下來對它插入一個結(jié)點。(其實生成樹時一直在插入，不 過還是做一下驗證一下。由于產(chǎn)生的是偽隨機數(shù)，所以運行結(jié)果和上次一樣)raw C:Wi n d-ow5systern22cmd.ex

12、e曲造T貝二叉排序樹=樹形狀如下：部/21/ 、52&/254Q475458；青輸入一個要插入的結(jié)點，2?青輸入一個要插入的結(jié)點；”*入學號27后，樹形狀如下.巾序遍歷結(jié)果為：5 21 25 26 27 30 40 47 54 5830 TOC o 1-5 h z /X2147/ / 5264054/ S、252758插入關(guān)鍵字(學號)為27的結(jié)點后，它已成功接到關(guān)鍵字為26的結(jié)點右邊作為其右孩子。并 以樹的形狀打印出來。所以，插入結(jié)點是成功的。1.4對生成的二叉排序樹刪除一個結(jié)點對二叉排序樹進行刪除操作，刪除函數(shù)代碼為：對二叉排序樹T中存在關(guān)健字等于k阿的數(shù)據(jù)元素時，則刪除之。E St at

13、 us Delet eBST (BiTree &L KeyTyp 已 key) (if (!T)return FALSE不存在關(guān)健宇等于kep的數(shù)據(jù)元素else if (EQ (Icey, T dal a) return Delete (T)到關(guān)鍵寶等于k 打的數(shù)據(jù)無素已 已 if (LT Qc 巳偵a) r 已 turn。已1 已 teBST (T-LchildJ k 已)；else return DeleteBST(T-rchildJkey):此函數(shù)也是遞歸調(diào)用。其中EQ()函數(shù)和LT()函數(shù)上面有說明。這里關(guān)鍵是Delete()函數(shù)， 定義如下：/7從二只排摩樹中余結(jié)點p，井重搔它的左右

14、子樹。E Status Delete (BiTree &p) ErTr ee s :if (!p-rchild) LV右子樹為空則重擦它的左子樹q = p ; p = p- 1 clii 1 d ; f r e e q);1獎/?左子樹為空只需重接它的右子樹q = p ; p = p- r clii 1 d ; f r e e q);1突/左右子樹都不空Q = p; s =while(s-rchild) /7向右走到盡頭q = s ； s = s-rchild;/s指向被刪結(jié)點的“前驅(qū)”p-data = s-dat a.;if (q != p) (/重接的右子樹q-rchild = s-lch

15、ild;else/重接*q的左田樹q-lchild = s-lchild;delete s;return TRUE;在原來樹插入結(jié)點27后，刪除結(jié)點54的運行結(jié)果為:請輸入一個要刪除的結(jié)點：54帆除學號X后，樹形狀如下，中序遍歷結(jié)果為=5 21 25 26 27 3B 40 47 5830 TOC o 1-5 h z 2147/ ， 、5264058/ 、2527所以，由遍歷結(jié)果和打印結(jié)果知，刪除是成功的。2、對二叉排序樹進行先根、中根、和后根非遞歸遍歷;非遞歸遍歷要用到棧，自己有寫棧的各種操作。另外，我發(fā)現(xiàn)可以用C+庫里面人家寫 好的，include進來就可以直接調(diào)用，以下代碼有些是用自己寫

16、的棧，有些是用C+庫里面的 (感覺別人寫的很好用，比如調(diào)試的時候查看棧內(nèi)元素就比自己寫的簡單明了)。思路都寫在 代碼的注釋里面面，個人覺得這樣好看些，截圖放入word文檔就省去排版了，更方便理解。2.1棧相關(guān)數(shù)據(jù)類型及函數(shù)定義E type def st ruct BiTNode tbasB, *top :桂底和桂頂指針，在棧構(gòu)造之前和銷成之后，ha睥的值為NULL int st acisize;/小，當前巳分噪的存儲空間，已元耄為單位。|日 Sq.St ack: St at us visit(ElemType elem) pxintf (Kd , el瓢):return OK:初始化棧Init

17、Stack()函數(shù)為：malloc是存儲空間分配函數(shù)，返回分配空間的首地址，所以一開始S.base和S.top保 存的是首地址，即棧頂指針和棧底指針指向同一個地方。其實棧是一個數(shù)組。E Status InitStack(SqStack /構(gòu)造一個空棧H S.base = (BiTNode malloc(STACK_INII_SIZE * aizeof(EiTNode):LfC! S.base) esit (OVERFLOW) 分嶇敗S. t op = S. base :S.stacksize = STACK_INIT_SIZE;teturn OE;判斷棧是否為空的StackEmpty()函數(shù)：

18、El St at us St a.c kEmpt y (S q.St ack S) if (S. base = S. t op return. TRUE:return FJiLSE;訪問元素的visit ()函數(shù)：IS Status visit (ElemTyp已 elem printf , elem): return OK:入棧Push()函數(shù)：入棧后棧頂指針上移，指向一個待存數(shù)據(jù)的位置。? Status Push(SqStack SjEiTNode +p) ff 插入元素p為新的棧頂元素if (S. top - S.base = STACK_INIT_SIZEi 追加空間hS. base=

19、(BiTNode*)realloc(S. bas6j (S. stacksizb+STACE_INCREMENI)*sizeof(BiTWode) if US.tase)eKi-t (OVERFLOW ;/7分噪,破S. t op = S. base + S. st acltsize:S.stacisize 4 STACK,INCREMENT:S. t op = *p ;S. -top=S. t op+1:return OK:出棧Pop()函數(shù)：出棧后棧頂指針下移，指向下一個數(shù)據(jù)的位置。若棧不空，則刪院5的柱頂元素，用P退回其值，并返回口虬杏則返回ERKQR.IE Status Fop (Sq

20、StackBiTNode 福口)if (S.base = S.top)returri ERROR：S. t op=S. top-1 : p = S. t op ： ret urn OK:2.2先、中、后序非遞歸遍歷算法/7先序遍歷”非遞歸E St at us PreOrder (BiTree T, Status(ELemTyje elem.) 采用C+庫里面的棧，Sinelude,using namespace std;stack S:-/JET保存下來(蛾給p)，因為一次遍歷后T就不一定指向根節(jié)點了，而下次1/7其他遍歷就不能對同一顆構(gòu)苣的材誑行遍仿，即為了T的復(fù)用、BiTree p = T

21、：if (T) 不是空樹就進行遍而S.pushfp);/先讓根節(jié)點柱whi le ( !S. empty ()/棧不空時進行循環(huán)P = S.top()取得犢頂元素臆給指針燮重pS.popO : /退棧，一出棧便要訪問之if (! visit (p-dat a) return. ERROR; /7訪問已出棧的無素，/若有右巷子，則先讓右攝子壓棧，因為訪問左巷子要在右枝子之前，根據(jù)棧是先進后/出和以上先出棧先訪問(一出棧便訪問)的規(guī)定，所瑚右枝子要被壓在左接子下面。if (p-rchild) S. push (p-rchild):if (p-Lchild)S. push(p-Lchild) ;/7

22、左子后進棧return OK中序遍歷一豐遞歸-St at us InOrder (Bilree Tj St at us (tvisil) (EleinType elem.) /7采用自己寫的棧的各神操作根據(jù)書本的偽臺，持化成可運行的匚語言代碼對T進行中序遍歷SqStack 5 :InitStack (3)：/始化一個棧5EiTree t = T：while(b | | !StacliEnipty(S)訝(EJLV若b不空，根指升進棧，左子樹進棧PushCSj b):b = b-lchlld；已1 m日3Popb)；/根指針退犢，訪問糧節(jié)點，遍歷右子樹Z7訪問節(jié)點b是在節(jié)點b的左子例為空或者石子

23、樹為空時訪問，即云【b)不成立時，在這種情況Z7下，要不就是左子樹為空，要不就是左子樹被訪問完了，此時應(yīng)訪問根節(jié)點并轉(zhuǎn)向右子樹。if (! vis it (b-dat a) return ERROR:L - b-rchild：return OKI后序遍歷一 非遞歸E- Status Pos-tOtd&r (BiTree T3 Status (*visit) (ElemType elemj) 即棧法思路是:先將節(jié)點入犢L，愁后出棧1放到桂2去，其實這和先厚遍仿婦的“逆序”很類似，先序的“逆序是右-左-根，而后序是左f右-根，榔是左右段子巨換一下寰是先序遍歷的“逆底由于要實現(xiàn)“逆婦自然又可以用另外

24、一個棧，所以當出棧1時不訪問，壓到棧7去形成“吏序再訪問婦由于最后訪問根節(jié)點，所以.根節(jié)點要壓在左右蒞子下面，st a.ck S1, S2 ： EiTree p = T ：SI. push (T);while ( ! SI. empty () ) / 柱空時結(jié)束p = SI. t op :S1. pop C);驅(qū)-pgh(p) ; /，第一次循環(huán)把根節(jié)點壓在棧2最下面。if (p-Lcliild) 左蒞子先入柱1，出棧則左套子后出柱1。SI. push (p-lchild) : /7由于柱1出來又要壓到柱9去，if (p-rcliild) 所以左枝子登壓在右苞子上面，這樣出SI. push (

25、pfr child，棧7時就會讓左孩子先出來，訪問while ( !S2. empty () 依次出棧八訪問P = S2. top ();if ( ! visit (p-dat a) return ERROR;S2.pop():retirn OK :思路都寫在注釋里面了。遍歷結(jié)果為:請輸入一個要刪除的結(jié)點；54屈除學號54后，樹形狀如下，中序遍歷結(jié)果為；5 21 25 26 27 30 40 47 5S4047582?25274740582730404758214058473030 21 5 265 21 25 265 25 27 26驗證遍歷結(jié)果知，遍歷成功。2.3遍歷算法總結(jié)其實，對于二叉

26、排序樹來說，中序遍歷是一個從小到大的序列。二叉樹的本質(zhì)是遞歸定義的二叉鏈表，對樹的操作往往離不開遞歸，遞歸形式上看起 來簡單明了，調(diào)用起來卻是層層嵌套，而且遞歸調(diào)用要保存很多信息，這些信息也應(yīng)該是用棧 來保存的，另外，遞歸調(diào)用會占用較多的CPU資源，效率不高。于是，我們考慮使用非遞歸的形式來對樹進行操作，而非遞歸的算法卻不太好理解， 可能對于我來說不確定的因素太多了吧，要自己想還真想不出來。一開始，算法也看不太懂， 特別是后序非遞歸比較難，本身對c語言，對指針就不是特別理解，于是只能跟著程序來調(diào)試， 并參考別人寫的，慢慢的才理解。個人覺得后序非遞歸算法用雙棧法比較高大上，因為不僅充 分運用數(shù)據(jù)

27、結(jié)構(gòu)的棧，還能和先序非遞歸進行對比，簡直是經(jīng)典算法。另外，做這幾個算法的時候也遇到了許多困難，感覺對指針怕怕的，還好后來經(jīng)過同 學間的討論，以及豐富的網(wǎng)上資源把困難擺平了。3、每次對樹的修改操作和遍歷操作的顯示結(jié)果都需要在屏 幕上用樹的形狀表示出來。3.1打印二叉排序樹二叉排序樹要用樹的形狀打印出來。打印二叉排序樹的函數(shù)思路如下：由于printf（）;函數(shù)會獨占一行，就是打印換行后，就開啟了新的一行，回不去原來那 一行去了。所以，要豎向打印一棵樹，必須用層次遍歷法，一層一層的打印，打印一層換一行。層次遍歷法主要用到了隊列，就是先讓根節(jié)點入隊列，然后讓根節(jié)點出隊列，若根節(jié) 點有左、或右孩子，則讓

28、左、右孩子依次入隊列。在基于層次遍歷法的基礎(chǔ)上，最主要的就是要控制好兩點：（1）遍歷到該元素時，該空多少個空格位再打印它。（2）什么時候打印換行。對于（1）:由于第一個打印的根節(jié)點我們可以先確定它的位置，比如放在第一行，空 了32個空格位的位置。那如果它有左右孩子，它的左右孩子該空多少格呢？我的答案是空 32/2=16個和32*3/2=48個。因為要打印的樹事先是不確定的，我們必須要照顧到會發(fā)生的所 有情況。當二叉排序樹趨于滿二叉排序樹而且樹的深度達到一定值時，比如5,空16和48個 空格位就會讓葉子結(jié)點不會擠在一個位置產(chǎn)生沖突。所以，我們有結(jié)論：當根節(jié)點空了n個空 格位再打印時，它的左右孩子

29、應(yīng)分別空n/2和n*3/2個空格位。對于(2):由于我們不知道要打印的樹具體是怎么樣的，所以不知道每一層有多少個 結(jié)點，自然就不知道什么時候該換行了。但是，我們知道滿二叉樹是長什么樣子的，所以我們 可以對每一棵二叉樹當做滿二叉樹來打印，當發(fā)現(xiàn)結(jié)點為空時，打印相應(yīng)的空格位就行了。又 因為層次遍歷法沒有讓空孩子入隊列，我們可以對它進行改進，就是讓空孩子也入隊列。這樣 做當發(fā)現(xiàn)隊列元素為空時，就知道節(jié)點不存在，即只管打印相應(yīng)空格。關(guān)鍵代碼如下：-Status FrintTree (BiTree T) /打印一棵樹，層次遍歷法。int n=32；1nt 0; int t=0;/n:控制打印空格數(shù)目。m

30、;控制打印換行。七控制每一行打印次數(shù) BiTree目毗t巳叩毗(:隊列用于層次遍仿令讓噸口:臨時數(shù)組，控制打印樹枝數(shù)目 int front二0 ;int rear二Cl;/7用于表示隊頭和隊尾指針bool flag = true;/用來判斷是否要維續(xù)循壞的標志if(T) /若非空，首先打印根節(jié)點Print Space (n) ;/7根節(jié)點定在窗口第一行凡乎中間的位置printf tSSdXnXrL, T-data):打印根結(jié)點元素h = 每次換行，h減半qLrear = T;/7糧節(jié)點入隊列七已呻住=同時保存到數(shù)組U n! = l) (/本身是隊列不空時循環(huán)，但這樣會死循環(huán)，由于特殊情況，fl

31、ag = false; NULL入隊列太嚴重，導(dǎo)致隊列如永遠追,不上比皿 irrt q = U ;Trent = (-frant+1 )100;T =;/取得隊頭元素 I I I . _ . . . -1_l_ I I - . |,-H-jtl ; / / 1 2 f J -if 5 5 G f 7 .* (T) ifCT-lchild) /左子存在，打印左模子Print Space (n 舊匚 intf (“禺 d。T- 1 child-da-t : Print Spce (n-1):resx = Crear+DLOO :qtrear = T-lchild：/打印后入隊列temp +-H =

32、 T-lchild：/保存到數(shù)組el3e /否則數(shù)組戚空并打印相應(yīng)空格，rear = Crear+DLOO ：qtrear = NULL:X PA 列t emp +1 - NULL:PrintSpace(2n)：/2*n+l?if CT-rchild)Print Space M :printfT- r child-da1: : Print Space (n-1):rear 二 Crear+DLOO : q rear = T-rchild.： t emp -H-t = T-rchild ：else rear = Crear+DlOO :q rear = NULL : /A 隊列t emp +-H

33、 = HULL :Print Space (舛 n);1睥本身是空樹，左右孩子自然不存在- r r I- I -r I-1 i i Lifor (int i=0 ; i2 ; zl-H-) /打印兩遍PrintSpace(2n):t ennp +t = HULL :rear = Crear+DLOa；q.rear = NULL :/A 隊列訝(m=l | | m=3| |in= 7 | |m=15| | m=31 | | m= = 63)滿足換行條件pELntfCW);n = n/2 ;/Lf(n=l)n = 2;f cr (int i=_fxant; i=rear; 1+) if Cq.if

34、 1 ag=true: / /FA列還有非空元素if (f lag：=f alse) /de 1ete q;delete temp:return OK:其中PrintSpace()函數(shù)為： Status Print Space (int mn.) /打印 個空格 for (int i=0 : ilchiLdj&-tempi-rchild.) /7并且左右孩子存在?打印指向左右技子的樹枝 Print Sp ac 已(n捋性):printf: Print Space (n);Mntf (W) : Print Space (n*3/2-1):if (i= 0)print;根節(jié)點處，多換一行是得更美觀

35、else if(temp i-1child)Print Sp ace (n3/2 :printf CV) : Print Space (n) ; Print Space t3*n/2-l):else if(temp i-rchild)Print Space(n3/2 :Print Space tn):printf:PrintSpace(3*n/2-l):else/-左右蒞子均不存在，打印相應(yīng)空格Pririt Space (rL5tt3/2 :Print Space tn) :PriritSpace (3*ri/2+1):elSe/左右強子均不存在，打印相應(yīng)空格Print Sp ace (n3/

36、2 : Print Space tn) : Print Space (3+：n/ 2+1);/,邁什=昂/記下L的位置?irintfCVn :運行結(jié)果為：ii、= m構(gòu)造一顆二叉排序樹： 也形狀如下:307214?/ /5邪4054/ /0254458于是，成功把樹枝加上去。3.3寫打印樹函數(shù)遇到的困難和總結(jié)這個函數(shù)不是萬能的，while循環(huán)里有一個條件n= 1時會跳出循環(huán)，就是由32變到1 一共換了 5行，而完全二叉樹第5行是有16個元素，這時我還可以打印第6行的32個元素， 所以以上打印樹的函數(shù)最多只能打印63個元素。因為樹的深度大于5后，命令行窗口寬度固定 了，空格位就很難把握了。寫這個

37、函數(shù)是一點一點優(yōu)化來的，歷時長，不過挺鍛煉人的，寫完挺有成就感。不過 當我知道有一種橫向打印樹的遞歸算法后，10行就搞定了，而且適用性很強。我就4、分別用二叉排序樹和數(shù)組去存儲一個班(50人以上)的成 員信息(至少包括學號、姓名、成績3項)，對比查找效率， 并說明在什么情況下二叉排序樹效率高,為什么？4.1初始化數(shù)組和二叉排序樹首先用一個數(shù)組存50人以上(65個)的成員信息：必要的初始化工作：Status Init (BiTNode bitArr L) ini:; int z=-l;char st r IIAK 1 000 ; char *c = ,r. chen ;皿產(chǎn)生隨機數(shù)。根據(jù)時間設(shè)置

38、隨機種子fox (int/始化BiTree q = (BiTNade *)jnllac(sizeaf (BiTHode):ifC!q)eKit (OVERFLOW存儲空間分酉哄敗，退出q-data = Cl;/7學號初始化為Clq-l child = q-rchild = NULL：/ 左右技子初始化q-n.amie -七/名字初始化為空q-score = 口;/7分數(shù)初始化為0bitArrti=咱;/7地址嗑給每一個數(shù)組元表(irrt)(對田詛()/7職皿_胸十1);產(chǎn)生。一nT的隨機數(shù)，RAND二花鬲T ;/7而公式rand.0% (n-m+1)十產(chǎn)生mfn的偽睫機數(shù)打設(shè)定分數(shù)，隨機紿定一

39、個aa-ioo分bitArr i. score = Cint) (lOLraiid()/):打設(shè)定學號，隨機給定一個10-99的學號idL+z = (int (90*rand(V(WED-MAX+D + 10):bit Ar r i. dat a = idz:for (mt j=0： j/A| / .return OK;4.2寫這個函數(shù)遇到的問題：一開始初始化姓名的函數(shù)是這樣的，打印輸出也在這個函數(shù)里面。能打印輸出正確的 結(jié)果。char *c = 17. cheri : cliar str 20:If or (mt l=0 ; idata = e. data; -n.ajne = e. naj

40、ne : E-score = s-lchild = s-rchild - NULL:if ( !d) T =舀刀祝播入結(jié)點*m為新的糧菇點創(chuàng)建二叉排序樹函數(shù)修改為：E Status CreateBinSortTreeZ (EiTree BiTKode BiTWode j BiTree 匝m iirt n) ( int r MAK:int t=-l:毗皿亂(項1:)頊函口)；/7產(chǎn)生隨機數(shù)。根據(jù)時間設(shè)置隨機種子for (mt i=a；in;i+) /若隨機數(shù)不重復(fù)，將產(chǎn)生irf結(jié)點的二叉排序樹，r +t = (:Lnt) QU跆rand()/(EAND_臉(十 1);產(chǎn)生。一的隨機數(shù)#for (

41、int j=O;jt;j+)有堇復(fù)，重新來討，保證數(shù)組元表全部插到樹里ifCrt=Ej) -一t :一一i:break:InsertBSTl (L BiTNoder Lt 3 p) ;/7插入.一個結(jié)點。return OK:對其進行中序遍歷結(jié)果如下:中序非誦歸遍歷：18 13 14 15 16 18 20 21 22 24 26 27 28 29 31 32 33 34 38 39 40 4 E 43 44 45 46 48 49 50 51 52 53 55 56 57 58 60 61 62 63 64 碼 66 67 68 69 70 71 72 73 74 75 7t 79 80 81

42、 83 84 89 91 92 94 9t 97 99、+ 3- X產(chǎn)、和 U X UE+ I-數(shù)了一下，發(fā)現(xiàn)剛好有65個結(jié)點。由于信息太多，用層次遍歷法打印樹的形狀(縱向 打印)不能漂亮的打印出來，因為樹的深度到了 5之后，命令行窗口寬度固定了，很難把握空 格位的細微之差。但是依然可以用遞歸的方法橫向打印出一棵樹，但還是數(shù)據(jù)太多，這樣打印 出來的樹也很難看，我試了，一個窗口屏幕也顯示不完。所以打印結(jié)果就不放上來了。根據(jù)以上輸出結(jié)果和遍歷結(jié)果，說明二叉排序樹保存的學生信息和數(shù)組保存的學生信 息是一樣的。在這個前題下，接下來就可以做效率分析了。4.3效率分析書本上說，在隨機情況下，二叉排序樹的平

43、均查找長度和logn是等數(shù)量級的。就是二叉排序樹的查找可以獲得類似折半查找的性能。當二叉排序樹趨于滿二叉排序樹時，查 找性能是最好的。而數(shù)組的平均查找長度應(yīng)該為n/2。那數(shù)組和二叉排序樹的查找效率哪個比較高呢？ 看起來好像二叉排序樹性能會好點。但是數(shù)組是具有連續(xù)存儲地址的一種比較特別的數(shù)據(jù)結(jié)構(gòu)。 對數(shù)組查找僅需做一次判斷，不需要調(diào)用查找函數(shù)。而且，二叉排序樹的查找需要調(diào)用查找函 數(shù)，查找函數(shù)是遞歸。結(jié)點之間以指針相連這些都還不知道要不要花費時間。二叉排序樹和數(shù)組的性能比較：思路是對已經(jīng)初始化的二叉排序樹和數(shù)組(兩者具有相同的數(shù)據(jù)元素，數(shù)據(jù)元素個數(shù) 和值都是一樣)進行查找某一個動態(tài)(隨機)確定的

44、數(shù)據(jù)元素n(n足夠大)次，每次查找都是 隨機給定一個要查找的目標元素。(查找的是關(guān)鍵字學號，學號范圍是10到99) 函數(shù)如下：-St atus Compare (BiTree I, BiTWode bitArr EiTr&e p) 數(shù)組和二叉排摩樹巳經(jīng)初始化，每麥萱找都是萱找一個隨機值毗而頊ED)】：，,產(chǎn)生臆機數(shù)*根據(jù)時間設(shè)置隨機神子int Yi = 1000000 ：/總共萱找次教double st art = clock。； 查戒二以排摩料開始時間forCrnt != : lh ; 2+) 每一次給室一個。到頁的隨機數(shù)int r = (mt) (HAR*rand (RAIED_MAK+1

45、):if (SearchBST (T： bit Ar r r . dat a, NULL, p) ) c out mue ;double finish = clock ()刀查找二叉排厚樹結(jié)束時間double time 二 f lnzLsh-st art ;printf (i(在二叉排序櫥里隨機查找任意一個關(guān)鍵字囁d次所需時間為二,烏七項已);| statt =己口匚虹)；/查拔數(shù)組開始肘間far(int i=0;ix二1; /7對每個元素做唯一標識 qzear-y = 1：/7對每個換行元素做行數(shù)標識 while(rear != front)+in： front = (front + 0%1

46、00： I = q.frot: iCr-lchzLld) rear = (rear+l)iaO: qrear = T-lchil(l; qrear/-k = m+1 ;if (r-rchild) rear = (rear+DlOO : q.rear = T-rchild.： q.rear-s = m+1:if Cm=1|m=31|m=71|血二二15|n=31) -H-qrear-y 行標志。return OK后來發(fā)現(xiàn)是不行的，因為這樣就要用到引用，這次遍歷完成后，屬性雖然可以設(shè)置成 功，T已經(jīng)不知道指向什么地方了，就是原來生成的樹T已經(jīng)變了，下次對T的操作就會得到 錯誤結(jié)果。另外，寫初始化函

47、數(shù)Init()也遇到很多問題，上面已經(jīng)分析了一些。主要是對字符 指針和對字符串操作不熟的原因。不過我最后使用隨機數(shù)來初始化數(shù)組，然后把數(shù)組元素生成 二叉排序樹，簡化了很多繁瑣的賦值代碼量。還有問題就是怎么保證全部數(shù)組元素都插到二叉 排序樹里面去了？像初始化學號那樣，遇到重復(fù)學號就重新來一次。由于數(shù)組元素關(guān)鍵字都是 不同的，所以也可以按照數(shù)組順序來插。初始換操作也可以不用循環(huán)來賦值，這樣代碼量就比 較大了。做完這個程序，就要寫論文了，難點是怎么想辦法把自己的思路清晰的表達出來。其 實在寫程序時，我們應(yīng)該把一些思路過程保存下來了(修改程序時，把原先程序注釋起來，同 時也盡量寫多點代碼注釋)。所以，

48、總的來說，經(jīng)過這些對自己的鍛煉，特別是嚴謹性，全局觀的邏輯性，對代碼 的敏感性都會得到大大的提高。以前遇到問題會很惱怒不知道錯誤出在哪里，經(jīng)過一些訓(xùn)練后 你就會很淡定的面對BUG。你會有較高的直覺發(fā)覺哪里有問題，就算沒有還可以調(diào)試分析，這 樣再配合自己對代碼的邏輯分析，豐富的學習資源，大家的幫助，我想，什么BUG也應(yīng)該不在 話下了吧。六、附錄(代碼)頭文件：#include#include#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1/#define OV

49、ERFLOW -2#define MAX 65#define STACK_INIT_SIZE 100#define STACK_INCREMENT 10typedef int Status;typedef int ElemType;typedef int KeyType;#define EQ(a,b) (!strcmp(a),(b)#define LT(a,b) (strcmp(a),(b) 0)#define LQ(a,b) (strcmp(a),(b) = STACK_INIT_SIZE)/棧滿，追加空間S.base=(BiTNode*)realloc(S.base,(S.stacksiz

50、e+STACK_INCREMENT)*sizeof(BiTNode);if(!S.base)exit(OVERFLOW);/分 配失敗S.top = S.base + S.stacksize;S.stacksize += STACK_INCREMENT;*S.top = *p;S.top=S.top+1;return OK;/若棧不空，則刪除S的棧頂元素用p返回其值，并返回OK,否則返回ERROR.Status Pop(SqStack &S,BiTNode *&p)if(S.base = S.top)return ERROR;S.top=S.top-1;p = S.top;return OK;

51、Status GetTop(SqStack S,BiTNode *p)if(S.base = S.top)return ERROR;*p = *(S.top-1);return OK;Status StackEmpty(SqStack S)if(S.base = S.top)return TRUE; return FALSE;Status strcmp(int a,int b)/自己定義，用于數(shù)值型 return a - b;Status Delete(BiTree &p) BiTree q,s;if(!p-rchild)/右子樹為空則重接它的左子樹q = p;p = p-lchild;fre

52、e(q);else if(!p-lchild)/左子樹為空只需重接它的右子樹q = p;p = p-rchild;free(q);)else/左右子樹都不空q = p;s = p-lchild;/轉(zhuǎn)左while(s-rchild)/向右走到盡頭q = s;s = s-rchild;/s指向被刪結(jié)點的“前驅(qū)”p-data = s-data;if(q != p)/重接*4的右子樹q-rchild = s-lchild;else/重接*4的左子樹q-lchild = s-lchild;delete s;return TRUE;/對二叉排序樹T中存在關(guān)鍵字等于key的數(shù)據(jù)元素時，則刪除之。Status

53、 DeleteBST(BiTree &T,KeyType key)if(!T)return FALSE;/不存在關(guān)鍵字等于key的數(shù)據(jù)元素elseif(EQ(key,T-data) return Delete(T);/找到關(guān)鍵字等于 key 的數(shù)據(jù)元素 else if(LT(key,T-data) return DeleteBST(T-lchild,key);else return DeleteBST(T-rchild,key);/在樹T上查找關(guān)鍵字等于key的數(shù)據(jù)元素，若查找成功，讓指針？/指向該元素結(jié)點，并返回TRUE。否則？指向查找路徑上訪問的最/后一個結(jié)點，返回FALSE,指針f指向T

54、的雙親，f初始值為NULL。/從二叉排序樹中刪除結(jié)點P，并重接它的左右子樹。Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p)if(!T)p = f;return FALSE;/查找不成功else if EQ(key,T-data)p = T;return TRUE;/查找成功else if LT(key,T-data) return SearchBST(T-lchild,key,T,p);else return SearchBST(T-rchild,key,T,p);/在 右子樹繼續(xù)查找/當樹T中不存在關(guān)鍵字等于e的數(shù)據(jù)元素時，

55、插入。Status InsertBST(BiTree &T,ElemType e,BiTree &p)if(!SearchBST(T,e,NULL,p)/查找不成功BiTree s = (BiTree)malloc(sizeof(BiTNode);s-data = e;s-lchild = s-rchild = NULL;if(!p)T = s;/被插入結(jié)點*、為新的根結(jié)點。else if LT(e,p-data) p-lchild = s;/被插結(jié)點*s 為左孩子else p-rchild=s;/被插結(jié)點*、為右孩子 return TRUE;else return FALSE;/樹中已有關(guān)鍵

56、字相同結(jié)點，不再插入/當樹T中不存在關(guān)鍵字等于e的數(shù)據(jù)元素時，插入。Status InsertBST1(BiTree &T,BiTNode e,BiTree &p)if(!SearchBST(T,e.data,NULL,p)/查找不成功BiTree s = (BiTree)malloc(sizeof(BiTNode);s-data = e.data;s-name = ;s-score = e.score;s-lchild = s-rchild = NULL;if(!p)T = s;/被插入結(jié)點*、為新的根結(jié)點。else if LT(e.data,p-data) p-lchild =

57、 s;/被插結(jié)點*s 為左孩子 else p-rchild = s;/被插結(jié)點*s為右孩子 return TRUE;else return FALSE;/樹中已有關(guān)鍵字相同結(jié)點，不再插入Status CreateBinSortTree2(BiTree &T,BiTNode BiTNode,BiTree &p,int n)(int rMAX;int t=-1;srand(int)time(0);/產(chǎn)生隨機數(shù)。根據(jù)時間設(shè)置隨機種子for(int i=0;in;i+)(/若隨機數(shù)不重復(fù)，將產(chǎn)生n個結(jié)點的二叉排序樹。r+t = (int)(MAX*rand()/(RAND_MAX+1);/產(chǎn)生 0-6

58、4 的隨機數(shù)。for(int j=0;jdata = id;CreateBinSortTree1(T-lchild);CreateBinSortTree1(T-rchild);return OK;Status Init(BiTNode bitArr)/初始化/char s20;strcpy (s,小”)；int idMAX;int z=-1;char strMAX1000;char *c = .chen”;srand(int)time(0);/產(chǎn)生隨機數(shù)。根據(jù)時間設(shè)置隨機種子for(int i=0;idata = 0;/學號初始化為0q-lchild = q-rchild = NULL;/左右

59、孩子初始化q-name = ;/名字初始化為空q-score = 0;/分數(shù)初始化為0bitArri = *q;/地址賦給每一個數(shù)組元素/(int)(n*rand()/(RAND_MAX+1);產(chǎn)生 0-n-1 的隨機數(shù),RAND_MAX=32767;/而公式rand()%(n-m+1) + m。產(chǎn)生m-n的偽隨機數(shù)設(shè)定分數(shù)，隨機給定一個分數(shù)0-100分bitArri.score = (int)(101*rand()/(RAND_MAX+1);設(shè)定學號，隨機給定一個10-99的學號id+z = (int)(90*rand()/(RAND_MAX+1)+10);bitArri.data = id

60、z;for(int j=0;jz;j+)/由于學號不能重復(fù)if(idz=idj)/當發(fā)現(xiàn)有重復(fù)，重新賦值學號-z;-i;break;/設(shè)定名字itoa(i,stri,10);/類型轉(zhuǎn)換函數(shù)：整形轉(zhuǎn)字符串i:int,to,a將整數(shù)i轉(zhuǎn)換/成字符串存入stri指向的內(nèi)存空間,保存到stri里.10代表10進制的整數(shù)strcat(stri,c);/字符串拼接，c拼接到stri去，從stri的最后一個n開始/但是str是同一個引用 bitA = stri;/設(shè)定名字return OK;Status PrintSpace(int mn)/打印 mn 個空格for(int i=0;irch