本單元涉及的內(nèi)容-資料下載頁(yè)
【導(dǎo)讀】樹(shù)形結(jié)構(gòu)是以分支關(guān)系來(lái)定義的層次結(jié)構(gòu)。–D中其余數(shù)據(jù)元素都有且只有一個(gè)前趨；繼（子樹(shù)），或無(wú)后繼（葉結(jié)點(diǎn)）；0）個(gè)互不相交的集合。每個(gè)集合又是一棵。結(jié)點(diǎn)包括一個(gè)數(shù)據(jù)元素及若干個(gè)指向其它子樹(shù)的分。支；例如，A，B，C，D等。結(jié)點(diǎn)度結(jié)點(diǎn)擁有的子樹(shù)數(shù)；例如，A的度為3。父結(jié)點(diǎn)相對(duì)于某結(jié)點(diǎn)子樹(shù)的根，稱該結(jié)點(diǎn)為。兄弟結(jié)點(diǎn)同一父親的孩子之間互為兄弟結(jié)點(diǎn)。路徑結(jié)點(diǎn)的序列n1，n2，…等于父節(jié)點(diǎn)的層數(shù)加1。樹(shù)的深度節(jié)點(diǎn)的最大層數(shù)值。樹(shù)中每個(gè)結(jié)點(diǎn)而言，其子樹(shù)的集合即為森林。有序數(shù)如果將樹(shù)中結(jié)點(diǎn)的各子樹(shù)看成從左。否則，稱為無(wú)序樹(shù)。ROOT求樹(shù)的根，返回樹(shù)根的位置。CHILD求樹(shù)T中結(jié)點(diǎn)x的第i個(gè)孩子。CREATE（x，T1，T2，…,Tk)生成一個(gè)結(jié)點(diǎn)x,中各個(gè)結(jié)點(diǎn)，且使每個(gè)結(jié)點(diǎn)只能被訪問(wèn)一次。–每個(gè)結(jié)點(diǎn)至多只有兩個(gè)子樹(shù);不是普通樹(shù)的特殊情況；右子樹(shù)，而樹(shù)則無(wú)此區(qū)分。–由歸納假設(shè)，第i-1層上至多有2i-2個(gè)結(jié)點(diǎn)。該二叉樹(shù)深度為4,最多有24-1個(gè)結(jié)點(diǎn).找子易,找父難.
【正文】 始化 輸入結(jié)點(diǎn)數(shù)據(jù) ！ ROOT root=create_btee（） create_btree() 結(jié)束 ? N Y 打印該樹(shù) 查找指定結(jié)點(diǎn) Print_btree() Search_btree() 下一頁(yè) 上一頁(yè) 停止放映 第 72 頁(yè) 生成二叉排序樹(shù)程序框圖 Create_btree() 開(kāi)始 r = 0？ Y 申請(qǐng)結(jié)點(diǎn)空間 r = 0？ 顯示“溢出” 結(jié)束 根結(jié)點(diǎn)的處理 N Y N rleft = 0。 rright = 0。 rinfo = info 。 非根結(jié)點(diǎn) inforinfo? Y t=rleft t=rright N 調(diào)用本函數(shù) root? 返回 Y N rleft=0 rright=0 rootleft=r 或 rootright=r 下一頁(yè) 上一頁(yè) 停止放映 第 73 頁(yè) 查詢二叉排序樹(shù)算法框圖 開(kāi)始 Search_btree() !root Y 顯示“空樹(shù)” 返回 N rootinfo!=key循環(huán) keyrootinfo? root=rootleft root=rootright root=0? N Y 查找成功 ,顯示 返回 顯示“失敗” root!=0? 循環(huán)結(jié)束 ? N Y 下一頁(yè) 上一頁(yè) 停止放映 第 74 頁(yè) 打印算法框圖 開(kāi)始 Print_btree() r=0? Y N 調(diào)用自身打印左子 打印當(dāng)前結(jié)點(diǎn)值 調(diào)用自身打印右子 返回 下一頁(yè) 上一頁(yè) 停止放映 第 75 頁(yè) 主程序 include “” struct tree { char info。 struct tree *left,*right。 } main ( ) { char *s,*c,key=??。 struct tree *create_btree(),*search_btree(),*root=0。 do { printf(“Enter a letter:”)。 gets(s)。 if (!root) root=create_btree(root,root,*s)。 else create_btrr(root,root,*s)。 } while (*s) 。 下一頁(yè) 上一頁(yè) 停止放映 第 76 頁(yè) 主程序 (續(xù)） print_btree(root,0)。 key=?1?。 while ( key) { printf(“Enter a key to find:”)。 scanf(“%s”,amp。c)。 key=search_btree(root,c)。 printf(“press to continue\n”)。 } } /* Btree。 C 結(jié)束 */ 下一頁(yè) 上一頁(yè) 停止放映 第 77 頁(yè) 生成二叉排序樹(shù)程序 struct tree create_btree(root,r,info) struct tree *root,*r。 char info。 { if (r = =0 ) { r=malloc(sizeof(struct tree))。 rleft= 0。 rright=0。 rinfo=info。 if (root) { if(inforootinfo) root left=r。 else rootright=r。 } else { rright=0。 rleft = 0。 } return r。 } 下一頁(yè) 上一頁(yè) 停止放映 第 78 頁(yè) 生成二叉排序樹(shù)程序 （續(xù)） if (info rinfo) create_btree(r,rleft,info)。 if(info=rinfo) create_btree(r,rright,info)。 } 下一頁(yè) 上一頁(yè) 停止放映 第 79 頁(yè) struct tree *search_btree(root,key) struct tree *root。 char key。 { if (!root) { printf(“Empty btree\n”)。 return root。 } while(rootinfo!=key) { if(keyrootinfo) root=rootleft。 else root=rootright。 if(root==0) { printf(“Search Failure\n”)。 break 。 } } /* while(rootinfo!=key) */ 查詢二叉排序樹(shù)程序 下一頁(yè) 上一頁(yè) 停止放映 第 80 頁(yè) if (root !=0) printf(“Successful search\n key=%c\n”,rootinfo)。 return root 。 } /* *search_btree(root,key) */ 查詢二叉排序樹(shù)程序（續(xù)） 下一頁(yè) 上一頁(yè) 停止放映 第 81 頁(yè) 打印二叉排序樹(shù)程序 print_btree(r,l) struct tree *r。 int l。 { int i。 if (r = = 0) return 。 print_tree(rleft,l+1)。 for(i=0。il。i++) printf(“ “)。 printf(“%c\n”,rinfo)。 print_btree(rright,l+1)。 } 下一頁(yè) 上一頁(yè) 停止放映 第 82 頁(yè) 程序輸入 輸入： 輸出： h ? b d ? d p ? e r ? h b ? p e ? r ? 下一頁(yè) 上一頁(yè) 停止放映 第 83 頁(yè) 舉例 對(duì)數(shù)列 {10， 18， 3， 4， 9， 13， 25}， 生成二叉排序樹(shù) 。 10 （ 7） 10 18 （ 2） 10 3 18 （ 3） 10 3 18 4 （ 4） 10 3 4 18 9 10 3 4 9 18 13 （ 6） （ 5） 10 3 9 4 18 13 25 （ 1） 下一頁(yè) 上一頁(yè) 停止放映 第 84 頁(yè) 作業(yè)、思考題 本單元 作業(yè)： 11 作業(yè)要求： – 提交數(shù)字化作業(yè)，按要求提交到指定路徑下 – 用 C語(yǔ)言描述 – 作業(yè)命名方式為： 學(xué)號(hào) .章數(shù) _序號(hào) 下一頁(yè) 上一頁(yè) 停止放映 第 85 頁(yè) 結(jié)束語(yǔ) ? 歡迎對(duì)數(shù)字化教學(xué)法提出意見(jiàn)，以利改進(jìn)。 ? 我的 Email地址： ? 數(shù)字化課件的路徑 : jec254\user2\tools\lzq\軟件基礎(chǔ) ? 作業(yè)提交路徑： jec251\user\dataroom\homework\班級(jí)編號(hào) 謝謝，再見(jiàn)！
鄂ICP備17016276號(hào)-1