《二叉排序樹與平衡二叉樹的實(shí)現(xiàn)(總18頁).doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《二叉排序樹與平衡二叉樹的實(shí)現(xiàn)(總18頁).doc（19頁珍藏版）》請(qǐng)?jiān)趨R文網(wǎng)上搜索。

1、課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目：二叉排序樹與平衡二叉樹的實(shí)現(xiàn)專 業(yè) 班 級(jí) 學(xué) 生 學(xué) 號(hào) 指導(dǎo)教師 起止時(shí)間 年 學(xué)期 目 錄1.需求分析：31.1課程設(shè)計(jì)題目、任務(wù)及要求：31.2課程設(shè)計(jì)思想：32.概要設(shè)計(jì)：42.1二叉排序樹的定義：52.2二叉排序的存儲(chǔ)結(jié)構(gòu)：52.3模塊劃分：52.4主函數(shù)流程圖：63.詳細(xì)設(shè)計(jì)和代碼：83.1二叉鏈表：83.2順序表：144.心得與體會(huì)：181.需求分析：1.1課程設(shè)計(jì)題目、任務(wù)及要求：用二叉鏈表作存儲(chǔ)結(jié)構(gòu)： (1)以回車(n)為輸入結(jié)束標(biāo)志,輸入數(shù)列L，生成一棵二叉排序樹T；(2)對(duì)二叉排序樹T作中序遍歷，輸出結(jié)果；(3)計(jì)算二叉排序樹T查找成功的平均查找長(zhǎng)

2、度,輸出結(jié)果；(4)輸入元素x,查找二叉排序樹T,若存在含x的結(jié)點(diǎn),則刪除該結(jié)點(diǎn),并作中序遍歷(執(zhí)行操作2)；否則輸出信息“無x”；用順序表(一維數(shù)組)作存儲(chǔ)結(jié)構(gòu)： (1)以回車(n)為輸入結(jié)束標(biāo)志,輸入數(shù)列L，生成一棵二叉排序樹T；(2)對(duì)二叉排序樹T作中序遍歷,輸出結(jié)果；(3)計(jì)算二叉排序樹T查找成功的平均查找長(zhǎng)度,輸出結(jié)果；(4)輸入元素x,查找二叉排序樹T:若存在含x的結(jié)點(diǎn),則刪除該結(jié)點(diǎn),并作中序遍歷(執(zhí)行操作2)；否則輸出信息“無x”；1.2課程設(shè)計(jì)思想：生成二叉排序樹：建立二叉排序樹采用的是邊查找邊插入的方式。查找函數(shù)采用遞歸的方式進(jìn)行查找。查找是按照二叉排序樹的性質(zhì)進(jìn)行的，通過比

3、較要插入元素的關(guān)鍵字與當(dāng)前結(jié)點(diǎn)關(guān)鍵字的大小來決定我們是遍歷當(dāng)前結(jié)點(diǎn)的哪個(gè)子樹。如果小于當(dāng)前結(jié)點(diǎn)關(guān)鍵字，則遍歷它的左子樹；大于當(dāng)前結(jié)點(diǎn)關(guān)鍵字，則遍歷它的右子樹；等于當(dāng)前關(guān)鍵字，則此元素不插入原樹。我們按照這樣的規(guī)律，一直向下遍歷，知道它的子樹為空，則返回當(dāng)前結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)。然后利用插入函數(shù)將該元素插入原樹。中序遍歷：對(duì)二叉排序樹進(jìn)行中序遍歷采用遞歸函數(shù)的方式。在根節(jié)點(diǎn)不為空的情況下，先訪問左子樹，在訪問根結(jié)點(diǎn)，最后訪問右子樹。平均查找長(zhǎng)度：計(jì)算二叉排序樹的平均查找長(zhǎng)度，仍采用類似中序遍歷的遞歸方式，用s記錄總查找長(zhǎng)度，j記錄每個(gè)結(jié)點(diǎn)的查找長(zhǎng)度，s置初值為0，采用累加的方式最終得到總查找長(zhǎng)度s，

4、平均查找長(zhǎng)度就等于s/j（i為樹中結(jié)點(diǎn)的總個(gè)數(shù)）。刪除結(jié)點(diǎn)：刪除結(jié)點(diǎn)函數(shù)，采用邊查找變刪除的方式。如果沒有查找到，則不對(duì)樹做任何的修改：如果查找到結(jié)點(diǎn)，則分四種情況分別進(jìn)行討論：（1） 該結(jié)點(diǎn)左右子樹均為空；（2） 該結(jié)點(diǎn)僅左子樹為空；（3） 該結(jié)點(diǎn)僅右子樹為空；（4） 該結(jié)點(diǎn)左右子樹都不為空；2.概要設(shè)計(jì)：2.1二叉排序樹的定義：二叉排序樹是一種動(dòng)態(tài)樹表。二叉排序樹的定義：二叉排序樹或者是一棵空樹，或者是一棵具有如下性質(zhì)的二叉樹：（1）每個(gè)結(jié)點(diǎn)都有一個(gè)作為搜索依據(jù)的關(guān)鍵字（key），所有結(jié)點(diǎn)的關(guān)鍵字互不相同。（2）若它的左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值；（3）若它的右子樹非

5、空，則右子樹上所有結(jié)點(diǎn)的值均大于根節(jié)點(diǎn)的值；（4）左、右子樹本身又各是一棵二叉排序樹。2.2二叉排序的存儲(chǔ)結(jié)構(gòu)：二叉鏈表：建二叉樹的結(jié)點(diǎn)應(yīng)該包含三個(gè)域，分別存放結(jié)點(diǎn)的數(shù)據(jù)域data。左孩子結(jié)點(diǎn)指針leftChild和右孩子結(jié)點(diǎn)指針rightChild。 順序表：順序表中應(yīng)該包含一個(gè)數(shù)組指針（動(dòng)態(tài)申請(qǐng)空間）和一個(gè)記錄數(shù)組長(zhǎng)度的size。2.3模塊劃分：二叉鏈表：mian():主函數(shù)模塊。在主函數(shù)模塊中調(diào)用一下函數(shù)：（1）int Insert(BiTreeNode *root,int item):插入函數(shù)；（2）int Search(BiTreeNode *root,int item)：查找函數(shù)；

6、（3）void InorderTraverse(BiTreeNode *root)：中序遍歷輸出函數(shù)；（4）BiTreeNode* Delete(BiTreeNode *root,int x)：刪除函數(shù)；順序表：main()：主函數(shù)模塊。在主函數(shù)模塊中調(diào)用以下函數(shù)：（1）void Insert(BST T,int i,int key)：插入函數(shù)；（2）BST Create(int *data,int num)：生成順序表BST；（3）void InorderTraverse(BST T,int i)：中序遍歷顯示函數(shù)；（4）int Search(BST T,int key,int i)：查找函

7、數(shù)；（5）BST Delete(BST T,int key)：刪除函數(shù)；（6）computeASL(BST T,int i,int *s,int j)：計(jì)算平均查找長(zhǎng)度函數(shù)。2.4主函數(shù)流程圖：回車（n）為輸入結(jié)束標(biāo)志生成二叉排序樹T，調(diào)用Insert（）； 開始調(diào)用menu函數(shù)顯示菜單輸入choice=1實(shí)現(xiàn)中序遍歷，輸入輸入choice=2計(jì)算二叉排序樹的平均長(zhǎng)度輸入choice=3輸入你要?jiǎng)h除的元素x元素是否存在刪除此元素，然后再輸出中序遍歷的結(jié)果輸入choice=0 結(jié) 束輸入此二叉排序樹無元素xNY3.詳細(xì)設(shè)計(jì)和代碼：3.1二叉鏈表：源程序：int Insert(BiTreeNode

8、 *root,int item) /插入BiTreeNode *current,*parent=NULL,*p;current= *root;while(current != NULL)if(current-data = item)return 0;parent=current;if(current-data rightChild;elsecurrent= current-leftChild;p=(BiTreeNode *)malloc(sizeof(BiTreeNode);if(p=NULL)printf(空間不夠！);exit(1);p-data = item;p-leftChild =

9、NULL;p-rightChild = NULL;if(parent = NULL)*root = p;else if(itemdata)parent-leftChild =p;elseparent-rightChild =p;return 1;int Search(BiTreeNode *root,int item)BiTreeNode *p;if(root!=NULL)p=root;while(p!=NULL)if(p-data = item)return 1;if(itemp-data)p=p-rightChild;elsep=p-leftChild;return 0;void Inor

10、derTraverse(BiTreeNode *root) /中序遍歷顯示if(root = NULL)return; if(root-leftChild != NULL)InorderTraverse(root-leftChild);printf(%d ,root-data);if(root-rightChild !=NULL)InorderTraverse(root-rightChild);BiTreeNode* Delete(BiTreeNode *root,int x) /刪除操作BiTreeNode *s,*curr,*f,*q;int flag=0;curr=root;while(

11、curr!=NULL)&(!flag) /找到要?jiǎng)h除的結(jié)點(diǎn)if(curr-data=x)flag=1;else if(xdata)f=curr; /記住雙親的指針curr=curr-leftChild;elsef=curr;curr=curr-rightChild;if(flag)if(curr-leftChild=NULL&curr-rightChild=NULL) /左右子樹都為空if(curr=root)free(curr);root=NULL;elseif(curr=f-leftChild)free(curr);f-leftChild=NULL;elsefree(curr);f-rig

12、htChild=NULL;else if(curr-leftChild=NULL&curr-rightChild!=NULL) /左子樹為空if(curr=root)root=curr-rightChild;free(curr);elses=curr-rightChild;if(curr=f-leftChild) /判斷要?jiǎng)h除結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左子樹還是右子樹 f-leftChild=s;elsef-rightChild=s;free(curr);else if(curr-rightChild=NULL&curr-leftChild!=NULL) /右子樹為空if(curr=root)root=curr-leftChild;free(curr);elses=curr-leftChild;if(curr=f-leftChild) /判斷要?jiǎng)h除結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左子樹還是右子樹f-leftChild=s;elsef-rightChild=s;free(curr);else /左，右子樹都有