二叉排序樹與平衡二叉樹的實現(xiàn)

1、攀枝花學院學生課程設計（論文）題 目： 二叉排序樹與平衡二叉樹的實現(xiàn) 學生姓名： 學 號： 所在院(系)： 計算機學院 專 業(yè)： 班 級： 指 導 教 師： 職稱： 年 月 日攀枝花學院教務處制攀枝花學院本科學生課程設計任務書題目二叉排序樹與平衡二叉樹的實現(xiàn)1、課程設計的目的1) 使學生進一步理解和掌握課堂上所學各種基本抽象數(shù)據(jù)類型的邏輯結構、存儲結構和操作實現(xiàn)算法，以及它們在程序中的使用方法。2) 使學生掌握軟件設計的基本內容和設計方法，并培養(yǎng)學生進行規(guī)范化軟件設計的能力。3） 使學生掌握使用各種計算機資料和有關參考資料，提高學生進行程序設計的基本能力。2、課程設計的內容和要求（包括原始數(shù)據(jù)

2、、技術要求、工作要求等）(1) (1)以回車(n)為輸入結束標志,輸入數(shù)列L，生成一棵二叉排序樹T；(2)對二叉排序樹T作中序遍歷，輸出結果；(3)計算二叉排序樹T查找成功的平均查找長度,輸出結果；(4)輸入元素x,查找二叉排序樹T,若存在含x的結點,則刪該結點,并作中序遍歷(執(zhí)行操作2)；否則輸出信息“無x”；(5)用數(shù)列L，生成平衡的二叉排序樹BT:當插入新元素之后，發(fā)現(xiàn)當前的二叉排序樹BT不是平衡的二叉排序樹，則立即將它轉換成新的平衡的二叉排序樹BT； (6)計算平衡的二叉排序樹BT的平均查找長度，輸出結果。3、主要參考文獻1劉大有等，數(shù)據(jù)結構（C語言版），高等教育出版社2嚴蔚敏等，數(shù)據(jù)

3、結構（C語言版），清華大學出版社3William Ford，William Topp，Data Structure with C+清華大學出版社4蘇仕華等，數(shù)據(jù)結構課程設計，機械工業(yè)出版社4、課程設計工作進度計劃第1天 完成方案設計與程序框圖 第2、3天 編寫程序代碼第4天 程序調試分析和結果第5天 課程設計報告和總結指導教師（簽字）日期年 月 日教研室意見：年 月 日學生（簽字）： 接受任務時間： 年 月 日注：任務書由指導教師填寫。課程設計（論文）指導教師成績評定表題目名稱二叉排序樹與平衡二叉樹的實現(xiàn)評分項目分值得分評價內涵工作表現(xiàn)20%01學習態(tài)度6遵守各項紀律，工作刻苦努力，具有良好的

4、科學工作態(tài)度。02科學實踐、調研7通過實驗、試驗、查閱文獻、深入生產實踐等渠道獲取與課程設計有關的材料。03課題工作量7按期圓滿完成規(guī)定的任務，工作量飽滿。能力水平35%04綜合運用知識的能力10能運用所學知識和技能去發(fā)現(xiàn)與解決實際問題，能正確處理實驗數(shù)據(jù)，能對課題進行理論分析，得出有價值的結論。05應用文獻的能力5能獨立查閱相關文獻和從事其他調研；能提出并較好地論述課題的實施方案；有收集、加工各種信息及獲取新知識的能力。06設計（實驗）能力，方案的設計能力5能正確設計實驗方案，獨立進行裝置安裝、調試、操作等實驗工作，數(shù)據(jù)正確、可靠；研究思路清晰、完整。07計算及計算機應用能力5具有較強的數(shù)據(jù)

5、運算與處理能力；能運用計算機進行資料搜集、加工、處理和輔助設計等。08對計算或實驗結果的分析能力（綜合分析能力、技術經濟分析能力）10具有較強的數(shù)據(jù)收集、分析、處理、綜合的能力。成果質量45%09插圖（或圖紙）質量、篇幅、設計（論文）規(guī)范化程度5符合本專業(yè)相關規(guī)范或規(guī)定要求；規(guī)范化符合本文件第五條要求。10設計說明書（論文）質量30綜述簡練完整，有見解；立論正確，論述充分，結論嚴謹合理；實驗正確，分析處理科學。11創(chuàng)新10對前人工作有改進或突破，或有獨特見解。成績指導教師評語指導教師簽名： 年月日摘要：二叉排序樹：(1)若左子樹不空，則左子樹上所有節(jié)點的值均小于它的根結點的值；(2)若右子樹不

6、空，則右子樹上所有節(jié)點均大于它的根結點的值；(3)它的左右子樹分別為二叉排序樹。二叉平衡樹：若不是空樹，則(1)左右子樹都是平衡二叉樹；(2)左右子樹的深度之差的絕對值不超過1。本次實驗是利用二叉排序樹和平衡二叉樹達到以下目的：(1)以回車(n)為輸入結束標志,輸入數(shù)列L，生成一棵二叉排序樹T；(2)對二叉排序樹T作中序遍歷，輸出結果；(3)計算二叉排序樹T查找成功的平均查找長度,輸出結果；(4)輸入元素x,查找二叉排序樹T,若存在含x的結點,則刪該結點,并作中序遍歷(執(zhí)行操作2)；否則輸出信息“無x”；(5)用數(shù)列L，生成平衡的二叉排序樹BT:當插入新元素之后，發(fā)現(xiàn)當前的二叉排序樹BT不是平

7、衡的二叉排序樹，則立即將它轉換成新的平衡的二叉排序樹BT； (6)計算平衡的二叉排序樹BT的平均查找長度，輸出結果。關鍵字：數(shù)列L,結點,二叉排序樹,平衡二叉樹目錄對二叉排序樹T作中序遍歷，輸出結果；2摘要：4第一章 分析61.1功能描述6第二章 系統(tǒng)設計62.1 基本概念介紹6樹的概念62.3 插入結點82.4 刪除結點9第一章 編碼103.1 總體編碼103.2 總流程圖113.3 以指針T所指結點為根的二叉樹作右平衡旋轉處理12bf=RH12其他旋轉類推12第二章 測試124.1 創(chuàng)建平衡二叉樹測試124.2 插入結點測試144.3 刪除結點測試144.4 中序遍歷二叉樹15第五章 體會

8、17參考文獻：17第一章 分析1.1描述平衡二叉樹（Balanced Binary Tree）又被稱為AVL樹（有別于AVL算法），且具有以下性質：它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。構造與調整方法 平衡二叉樹的常用算法有紅黑樹、AVL、Treap、伸展樹等。 最小二叉平衡樹的節(jié)點的公式如下 F(n)=F(n-1)+F(n-2)+1 這個類似于一個遞歸的數(shù)列，可以參考Fibonacci數(shù)列 1是根節(jié)點 F(n-1)是左子樹的節(jié)點數(shù)量 F(n-2)是右子數(shù)的節(jié)點數(shù)量。通過本程序的設計編寫所要求達到的目的是：1. 充分理解和掌握二叉樹、平衡

9、二叉樹的相關概念和知識。2. 掌握平衡二叉樹的生成、結點刪除、插入等操作過程。3. 并實現(xiàn)從鍵盤上輸入一系列數(shù)據(jù)（整型），建立一棵平衡二叉樹。4. 任意插入或刪除一個結點后仍然要求構成平衡二叉樹。5. 按先序和中序遍歷輸出這棵平衡二叉樹。第二章 系統(tǒng)設計2.1 基本概念介紹樹的概念樹（Tree）是n（n=0）個結點的有限集。在任意一棵非空樹中：1) 有且僅有一個特定的稱為根的結點；2) 當n1時，其余結點可分為m（m0）A個互不相交的有限集T1，T2.Tm，其中每一個集合又是一棵樹，并且稱為根的子樹（SubTree）。BCEDFGH圖1是有8個結點的樹，其中A是根，其余結點分成2個子集：T1=

10、B，D，T2=C，E，F(xiàn)，G，H；T1和T2都是根A的子樹，且本身也是一棵樹。平衡二叉樹的概念形態(tài)勻稱的二叉樹稱為平衡二叉樹 (Balanced binary tree) ：若 T 是一棵非空二叉樹，其左、右子樹分別為 TL 和 TR ，令 hl 和 hr 分別為左、右子樹的深度。當且僅當TL 、 TR 都是平衡二叉樹； hl hr 1；時，則 T 是平衡二叉樹?！纠咳鐖D1-2 所示：AAACBCBCBEFDDHG（a）平衡二叉樹 （b）非平衡二叉樹圖1-2 平衡二叉樹與非平衡二叉樹圖2-7 平衡二叉樹的生成過程2.3 插入結點在平衡二叉排序樹BBST上插入一個新數(shù)據(jù)元素e的遞規(guī)算法可以描述

11、如下：(1) 若BBST為空樹，則插入一個數(shù)據(jù)元素為e的新結點作為BBST的根結點，樹的深度增加1；(2) 若e的關鍵字和BBST的根結點的關鍵字相等，則不進行插入；(3) 若e的關鍵字小于BBST的根結點的關鍵字，而且在BBST的左子樹中不存在和e有相同關鍵字的結點，則將e插入在BBST的左子樹上，并且當插入之后的左子樹深度增加1時，分別就下列情況處理之：1. BBST的根結點的平衡因子為1（右子樹深度大于左子樹深度）：則將根結點的平衡因子更改為0，BBST的深度不變；2. BBST的根結點的平衡因子為0（左，右子樹深度相等）：則將根結點的平衡因子更改為1，BBST的深度增加1；3. BBS

12、T的根結點的平衡因子為1（左子樹深度大于右子樹深度）：若BBST的左子樹根結點的平衡因子為1，則需要進行單向右旋平衡處理，并且在右旋處理之后將根結點和右子樹根結點的平衡因子更改為0，樹的深度不變；若BBST的左子樹根結點的平衡因子為1，這需進行先向左后向右的雙向旋轉平衡處理，并且在旋轉處理之后，修改根結點和其左、右子樹根結點的平衡因子，樹的深度不變；(4) 若e的關鍵字大于BBST的根結點的關鍵字，而且在BBST的右子樹中不存在和e相同關鍵字的結點，則將e插入在BBST的右子樹上，并且當插入之后的右子樹深度增加1時，分別就不同情況處理。2.4 刪除結點刪除結點過程與插入結點的操作類似，基本過程

13、是：平衡二叉樹-找到要刪除的結點-刪除一個結點-變成二叉樹-旋轉-變回平衡二叉樹。具體過程將詳細設計中的代碼。2.5 中序遍歷右遍歷的定義可知，中序遍歷二叉樹的遞規(guī)算法可以定義為：若二叉樹為空，則空操作；否則1) 中序遍歷左子樹2) 訪問根結點3) 中序遍歷右子樹如中序遍歷圖2-8的二叉樹，結點的訪問順序為：abcdefg圖2-8第一章 編碼3.1 總體編碼#includestdio.h#includestring.h#include#define Max 20 /結點的最大個數(shù)typedef struct node char data; struct node *lchild,*rchild

14、;BinTNode; /自定義二叉樹的結點類型typedef BinTNode *BinTree; /定義二叉樹的指針int NodeNum,leaf; /NodeNum為結點數(shù)，leaf為葉子數(shù)/=基于先序遍歷算法創(chuàng)建二叉樹=/=要求輸入先序序列，其中加入虛結點#以示空指針的位置=BinTree CreatBinTree(void) BinTree T; char ch; if(ch=getchar()=#) return(NULL); /讀入#，返回空指針 else T=(BinTNode *)malloc(sizeof(BinTNode); /生成結點 T-data=ch; T-lchi

15、ld=CreatBinTree(); /構造左子樹 T-rchild=CreatBinTree(); /構造右子樹 return(T); /=NLR 先序遍歷=void Preorder(BinTree T) if(T) printf(%c,T-data); /訪問結點 Preorder(T-lchild); /先序遍歷左子樹 Preorder(T-rchild); /先序遍歷右子樹 /=LNR 中序遍歷=void Inorder(BinTree T) if(T) Inorder(T-lchild); printf(%c,T-data); Inorder(T-rchild); /=LRN 后序

16、遍歷=void Postorder(BinTree T) if(T) Postorder(T-lchild); Postorder(T-rchild); printf(%c,T-data); /=采用后序遍歷求二叉樹的深度、結點數(shù)及葉子數(shù)的遞歸算法= int hl,hr,max;TreeDepth(BinTree T) if(T) hl=TreeDepth(T-lchild); /求左深度 hr=TreeDepth(T-rchild); /求右深度 max=hlhr? hl:hr; /取左右深度的最大值 NodeNum=NodeNum+1; /求結點數(shù) if(hl=0&hr=0) leaf=l

17、eaf+1; /若左右深度為0，即為葉子。 return(max+1); else return(0);/=利用先進先出（FIFO）隊列，按層次遍歷二叉樹=void Levelorder(BinTree T) int front=0,rear=1; BinTNode *cqMax,*p; /定義結點的指針數(shù)組cq cq1=T; /根入隊 while(front!=rear) front=(front+1)%NodeNum; p=cqfront; /出隊 printf(%c,p-data); /出隊，輸出結點的值 if(p-lchild!=NULL) rear=(rear+1)%NodeNum;

18、 cqrear=p-lchild; /左子樹入隊 if(p-rchild!=NULL) rear=(rear+1)%NodeNum; cqrear=p-rchild; /右子樹入隊 /=主函數(shù)=void main() BinTree root; int i,depth; printf(n);printf(Creat Bin_Tree； Input preorder:); /輸入完全二叉樹的先序序列， / 用#代表虛結點，如ABD#CE#F# root=CreatBinTree(); /創(chuàng)建二叉樹，返回根結點 do /從菜單中選擇遍歷方式，輸入序號。 printf(t* select *n);

19、printf(t1: Preorder Traversaln); printf(t2: Iorder Traversaln); printf(t3: Postorder traversaln); printf(t4: PostTreeDepth,Node number,Leaf numbern); printf(t5: Level Depthn); /按層次遍歷之前，先選擇4，求出該樹的結點數(shù)。 printf(t0: Exitn); printf(t*n); scanf(%d,&i); /輸入菜單序號（0-5） switch (i) case 1: printf(Print Bin_tree

20、Preorder: ); Preorder(root); /先序遍歷 break; case 2: printf(Print Bin_Tree Inorder: ); Inorder(root); /中序遍歷 break; case 3: printf(Print Bin_Tree Postorder: ); Postorder(root); /后序遍歷 break; case 4: depth=TreeDepth(root); /求樹的深度及葉子數(shù) printf(BinTree Depth=%d BinTree Node number=%d,depth,NodeNum); printf( BinTree Leaf number=%d,leaf