二叉排序樹的建立插入刪除和查找

1、題目：二叉排序樹的建立、插入、刪除和查找 完成日期：2016-11-10一、需求分析1、 運(yùn)行環(huán)境：VC+6.0;語言：C語言；程序所實(shí)現(xiàn)的功能：給出一組關(guān)鍵值，建立相應(yīng)的二叉排序樹，完成：1結(jié)點(diǎn)的刪除操作，插入一個(gè)新結(jié)點(diǎn)的操作2對給定的值在二叉排序樹進(jìn)行查找；3隨時(shí)顯示操作的結(jié)果。2、 程序的輸入：n個(gè)關(guān)鍵字，及要插入，刪除，查找的關(guān)鍵字；3、 程序的輸出：操作后的二叉排序樹的中序序列即遞增序列；4、 測試數(shù)據(jù)：1）8 12 5 10 6 11 13 9 （n=8）;10；7；11； 2）10 7 12 9 8 （n=5）;10;6;10; 3) 8 5 6 (n=3);6;9;8;二、概要

2、設(shè)計(jì) 1、程序的主要流程圖： 否是開始建樹： 依次輸入n個(gè)關(guān)鍵字 插入二叉排序樹中 中序輸出創(chuàng)建過程刪除任意結(jié)點(diǎn)插入一個(gè)結(jié)點(diǎn)查找關(guān)鍵字中序輸出操作后二叉排序樹是否繼續(xù)結(jié)束2、主要模塊： 1）主函數(shù)模塊 Main()建立n個(gè)關(guān)鍵字的二叉排序樹并輸出；從二叉樹排序樹T中刪除任意結(jié)點(diǎn),其關(guān)鍵字為x；在二叉樹排序樹T中，插入一個(gè)結(jié)點(diǎn)t,其關(guān)鍵字為key1；在二叉排序樹T中遞歸查找關(guān)鍵字等于 key2 的數(shù)據(jù)元素；查找成功則輸出SUCCESS；查找失敗則輸出NOSUCCESS；2）創(chuàng)建二叉排序樹模塊BiTree CreatBST(int n)建立n個(gè)關(guān)鍵字的二叉排序樹； 從鍵盤輸入調(diào)建立n個(gè)關(guān)鍵字依次用

3、InsertBST1（插入函數(shù)）； 返回根結(jié)點(diǎn)T； 輸出過程； 3）刪除模塊DeleteNode(BiTree &T, int x)從二叉樹排序樹T中刪除任意結(jié)點(diǎn),其關(guān)鍵字為x； 可以實(shí)現(xiàn)刪除根結(jié)點(diǎn)、葉子結(jié)點(diǎn)以及其它任意結(jié)點(diǎn)的功能； 4）插入模塊void InsertBST1(BiTree &T,BiTNode *s)在二叉樹排序樹T中，插入一個(gè)結(jié)點(diǎn)s(遞歸算法)； 被CreatBST函數(shù)調(diào)用； 5）查找模塊BiTree SearchBST1(BiTree T,TElemType key)在根指針T所指二叉排序樹中遞歸查找關(guān)鍵字等于 key 的數(shù)據(jù)元素； 若成功，返回指向該數(shù)據(jù)

4、元素結(jié)點(diǎn)的指針； 否則返回空指針；3、抽象數(shù)據(jù)類型設(shè)計(jì)； 對于二叉樹排序樹而言，每個(gè)節(jié)點(diǎn)都是由“數(shù)據(jù)域”、左右 “指針域”三部分組成的，因此將二叉樹抽象成一個(gè)指向根結(jié)點(diǎn)由“關(guān)鍵字，左右孩子”構(gòu)成 的二叉鏈表。三、詳細(xì)設(shè)計(jì) 1、二叉排序樹數(shù)據(jù)類型定義；typedef struct BiTNode TElemType data;struct BiTNode *lchild,*rchild;/左右孩子指針 BiTNode,*BiTree; BiTree T;/ 二叉樹排序樹T 2、主要函數(shù)說明：（偽代碼及算法設(shè)計(jì)思想） void main()T=CreatBST(n); /建立n個(gè)關(guān)鍵字的二叉排序樹

5、,返回根結(jié)點(diǎn)T /從二叉樹排序樹T中刪除任意結(jié)點(diǎn),其關(guān)鍵字為xDeleteNode(T, x);Inorder(T); /在二叉樹排序樹T中，插入一個(gè)結(jié)點(diǎn)t,其關(guān)鍵字為key1t=(BiTree)malloc(sizeof(BiTNode);t->data=key1;t->lchild=NULL; t->rchild=NULL; InsertBST1(T,t);Inorder(T);/在二叉排序樹T中遞歸查找關(guān)鍵字等于 key2 的數(shù)據(jù)元素s=SearchBST1(T,key2);if(s)printf("SUCESSn");/查找成功else print

6、f("NOSUCESSn");/查找失敗BiTree SearchBST1(BiTree T, TElemType key)/在根指針T所指二叉排序樹中遞歸查找關(guān)鍵字等于 key 的數(shù)據(jù)元素 /若成功，返回指向該數(shù)據(jù)元素結(jié)點(diǎn)的指針，否則返回空指針；s為返回/指針if(T=NULL) return NULL; if(T->data=key) s=T;else if(T->data>key) /key大于當(dāng)前結(jié)點(diǎn)的關(guān)鍵字 ，則查找左子樹s=SearchBST1(T->lchild,key);/key小于當(dāng)前結(jié)點(diǎn)的關(guān)鍵字則查找右子樹 Else s=Sear

7、chBST1(T->rchild,key); return s;void Inorder(BiTree T)/中序輸出二叉樹排序樹T(非空時(shí))if(T!=NULL) Inorder(T->lchild);/中序輸出左子樹printf("%3d",T->data);/訪問結(jié)點(diǎn)Inorder(T->rchild);/中序輸出右子樹void InsertBST1(BiTree &T,BiTNode *s)/在二叉樹排序樹T中，插入一個(gè)結(jié)點(diǎn)s的遞歸算法t=SearchBST1(T,s->data);/若s的關(guān)鍵字不在T中出現(xiàn)，則插入if(!t)

8、if(T=NULL)T=s; /空樹時(shí)作為根結(jié)點(diǎn) else if(s->data<T->data) InsertBST1(T->lchild,s); /將s插入T的左子樹else InsertBST1(T->rchild,s); /將s插入T的右子樹BiTree CreatBST(int n)/建立n個(gè)關(guān)鍵字的二叉排序樹, /從鍵盤輸入調(diào)建立n個(gè)關(guān)鍵字依次用InsertBST1（插入函數(shù)）， /返回根結(jié)點(diǎn)TT=NULL; printf("建樹過程：n");for(i=1;i<=n;i+) printf("插入結(jié)點(diǎn)關(guān)鍵值：n&qu

9、ot;);scanf(key); s=(BiTree)malloc(sizeof(BiTNode);/開辟存儲(chǔ)單元，并對結(jié)點(diǎn)賦值s->data=key;s->lchild=NULL; s->rchild=NULL;InsertBST1(T,s); /調(diào)用插入算法 Inorder(T);/中序輸出return T;DeleteNode(BiTree &T, int x)/從二叉樹排序樹T中刪除任意結(jié)點(diǎn),其關(guān)鍵字為x p=T; /從根結(jié)點(diǎn)開始查找 pParent = NULL; / T的雙親為NULL / 開始查找關(guān)鍵字為x的結(jié)點(diǎn)p,及雙親pParent while (p

10、) if (x = p->data) break; pParent = p; p = x > p->data ? p->rchild : p->lchild; if (p=NULL) printf("要?jiǎng)h除的結(jié)點(diǎn)不存在n"); return false; / 至此已找到目標(biāo)結(jié)點(diǎn)p / pChileNode = p存在的孩子或NULL,左右都存在時(shí)，取左 pChileNode = p->lchild!= NULL ? p->lchild : p->rchild; if(p->lchild=NULL|p->lchild

11、=NULL) /當(dāng)只存在1個(gè)孩子或2個(gè)孩子(葉子結(jié)點(diǎn))都為空時(shí)，if (pParent = NULL) / 如果要?jiǎng)h除的是根，則把根設(shè)為找到的孩/或NULL T= pChileNode; else / 如果要?jiǎng)h除的不是根 /判斷一下要?jiǎng)h除的結(jié)點(diǎn)是其雙親的左還是右孩子做相應(yīng)處理 if(p=pParent->lchild) /刪除結(jié)點(diǎn)，雙親相應(yīng)的指針指向這個(gè)結(jié)點(diǎn)的孩子 pParent->lchild= pChileNode; else pParent->rchild = pChileNode; /同上 free(p);/釋放空間 / 當(dāng)2個(gè)孩子都存在時(shí) else /pChileN

12、ode已指向p->lchildq=p; while (pChileNode->rchild) /在p的左字樹中查找中序p的前驅(qū)pChileNode，q為其雙親q=pChileNode; pChileNode = pChileNode->rchild; p->data=pChileNode->data;/p的前驅(qū)pChileNodede 的關(guān)鍵值賦給pif(q!=p) /將刪除p轉(zhuǎn)化為刪除pChileNodede(最多只有左字樹)結(jié)點(diǎn)q->rchild=pChileNode->lchild;/p的左字樹有右孩子else q->lchild=pChi

13、leNode->lchild;/p的左字樹有右孩子free(pChileNode); return true; 四、上級(jí)結(jié)果及體會(huì)1、實(shí)際完成情況：實(shí)現(xiàn)二叉排序樹的建立、插入、刪除和查找功能； 支持的數(shù)據(jù)類型：二叉鏈表。2、程序的性能分析：假設(shè)n個(gè)結(jié)點(diǎn)的二叉排序樹 創(chuàng)建：T(n)=O(n);刪除：T(n)=O(n)；插入：T(n)=O(1) 查找：T(n)=O(logn);中序輸出：T(n)=O(n)； 故程序:T(n)=O(n+logn)3、源程序，程序運(yùn)行時(shí)的初值和運(yùn)行結(jié)果（見附件）4、程序的擴(kuò)充和改進(jìn)： 關(guān)鍵字類型可改為其他類型5、上機(jī)過程中出現(xiàn)的問題及其解決方案： 1）在編碼刪除結(jié)點(diǎn)DeleteNode函數(shù)的過程中遇到無法運(yùn)行的問題，經(jīng)請教老師，得到一定的提示：函數(shù)設(shè)計(jì)思路要理清； 2）在刪除根結(jié)點(diǎn)時(shí)出現(xiàn)不能執(zhí)行刪除結(jié)點(diǎn)左右子樹都存在的情況，魏近同學(xué)給出提示：結(jié)點(diǎn)轉(zhuǎn)換的思想； 6、收獲及體會(huì)： 通過這次的課程設(shè)計(jì)，我認(rèn)識(shí)到：僅僅掌握課本上的知識(shí)是不夠的，在實(shí)際操作時(shí)，常常遇到一些問題，自己看不懂，更無法解決。不過，經(jīng)過自己不斷的思考，嘗試著去更改代碼中出現(xiàn)的問題。雖然開始很困難，但在老師和同學(xué)的幫助下，我逐漸的熟悉了許多操作，為后繼工作的順