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

題目：二叉排序樹的建立、插入、刪除和查找 完成日期：2010-7-一、需求分析1、 運行環(huán)境：VC+6.0;語言：C語言；程序所實現的功能：給出一組關鍵值，建立相應的二叉排序樹，完成：1結點的刪除操作，插入一個新結點的操作2對給定的值在二叉排序樹進行查找；3隨時顯示操作的結果。2、 程序的輸入：n個關鍵字，及要插入，刪除，查找的關鍵字；3、 程序的輸出：操作后的二叉排序樹的中序序列即遞增序列；4、 測試數據：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;二、概要設計 1、程序的主要流程圖： 否是開始建樹： 依次輸入n個關鍵字 插入二叉排序樹中 中序輸出創(chuàng)建過程刪除任意結點插入一個結點查找關鍵字中序輸出操作后二叉排序樹是否繼續(xù)結束2、主要模塊： 1）主函數模塊 Main()建立n個關鍵字的二叉排序樹并輸出；從二叉樹排序樹T中刪除任意結點,其關鍵字為x；在二叉樹排序樹T中，插入一個結點t,其關鍵字為key1；在二叉排序樹T中遞歸查找關鍵字等于 key2 的數據元素；查找成功則輸出SUCCESS；查找失敗則輸出NOSUCCESS；2）創(chuàng)建二叉排序樹模塊BiTree CreatBST(int n)建立n個關鍵字的二叉排序樹； 從鍵盤輸入調建立n個關鍵字依次用InsertBST1（插入函數）； 返回根結點T； 輸出過程； 3）刪除模塊DeleteNode(BiTree &T, int x)從二叉樹排序樹T中刪除任意結點,其關鍵字為x； 可以實現刪除根結點、葉子結點以及其它任意結點的功能； 4）插入模塊void InsertBST1(BiTree &T,BiTNode *s)在二叉樹排序樹T中，插入一個結點s(遞歸算法)； 被CreatBST函數調用； 5）查找模塊BiTree SearchBST1(BiTree T,TElemType key)在根指針T所指二叉排序樹中遞歸查找關鍵字等于 key 的數據元素； 若成功，返回指向該數據元素結點的指針； 否則返回空指針；3、抽象數據類型設計； 對于二叉樹排序樹而言，每個節(jié)點都是由“數據域”、左右 “指針域”三部分組成的，因此將二叉樹抽象成一個指向根結點由“關鍵字，左右孩子”構成 的二叉鏈表。三、詳細設計 1、二叉排序樹數據類型定義；typedef struct BiTNode TElemType data;struct BiTNode *lchild,*rchild;/左右孩子指針 BiTNode,*BiTree; BiTree T;/ 二叉樹排序樹T 2、主要函數說明：（偽代碼及算法設計思想） void main()T=CreatBST(n); /建立n個關鍵字的二叉排序樹,返回根結點T /從二叉樹排序樹T中刪除任意結點,其關鍵字為xDeleteNode(T, x);Inorder(T); /在二叉樹排序樹T中，插入一個結點t,其關鍵字為key1t=(BiTree)malloc(sizeof(BiTNode);t-data=key1;t-lchild=NULL; t-rchild=NULL; InsertBST1(T,t);Inorder(T);/在二叉排序樹T中遞歸查找關鍵字等于 key2 的數據元素s=SearchBST1(T,key2);if(s)printf(SUCESSn);/查找成功else printf(NOSUCESSn);/查找失敗BiTree SearchBST1(BiTree T, TElemType key)/在根指針T所指二叉排序樹中遞歸查找關鍵字等于 key 的數據元素 /若成功，返回指向該數據元素結點的指針，否則返回空指針；s為返回/指針if(T=NULL) return NULL; if(T-data=key) s=T;else if(T-datakey) /key大于當前結點的關鍵字 ，則查找左子樹s=SearchBST1(T-lchild,key);/key小于當前結點的關鍵字則查找右子樹 Else s=SearchBST1(T-rchild,key); return s;void Inorder(BiTree T)/中序輸出二叉樹排序樹T(非空時)if(T!=NULL) Inorder(T-lchild);/中序輸出左子樹printf(%3d,T-data);/訪問結點Inorder(T-rchild);/中序輸出右子樹void InsertBST1(BiTree &T,BiTNode *s)/在二叉樹排序樹T中，插入一個結點s的遞歸算法t=SearchBST1(T,s-data);/若s的關鍵字不在T中出現，則插入if(!t)if(T=NULL)T=s; /空樹時作為根結點 else if(s-datadata) InsertBST1(T-lchild,s); /將s插入T的左子樹else InsertBST1(T-rchild,s); /將s插入T的右子樹BiTree CreatBST(int n)/建立n個關鍵字的二叉排序樹, /從鍵盤輸入調建立n個關鍵字依次用InsertBST1（插入函數）， /返回根結點TT=NULL; printf(建樹過程：n);for(i=1;idata=key;s-lchild=NULL; s-rchild=NULL;InsertBST1(T,s); /調用插入算法 Inorder(T);/中序輸出return T;DeleteNode(BiTree &T, int x)/從二叉樹排序樹T中刪除任意結點,其關鍵字為x p=T; /從根結點開始查找 pParent = NULL; / T的雙親為NULL / 開始查找關鍵字為x的結點p,及雙親pParent while (p) if (x = p-data) break; pParent = p; p = x p-data ? p-rchild : p-lchild; if (p=NULL) printf(要刪除的結點不存在n); return false; / 至此已找到目標結點p / pChileNode = p存在的孩子或NULL,左右都存在時，取左 pChileNode = p-lchild!= NULL ? p-lchild : p-rchild; if(p-lchild=NULL|p-lchild=NULL) /當只存在1個孩子或2個孩子(葉子結點)都為空時，if (pParent = NULL) / 如果要刪除的是根，則把根設為找到的孩/或NULL T= pChileNode; else / 如果要刪除的不是根 /判斷一下要刪除的結點是其雙親的左還是右孩子做相應處理 if(p=pParent-lchild) /刪除結點，雙親相應的指針指向這個結點的孩子 pParent-lchild= pChileNode; else pParent-rchild = pChileNode; /同上 free(p);/釋放空間 / 當2個孩子都存在時 else /pChileNode已指向p-lchildq=p; while (pChileNode-rchild) /在p的左字樹中查找中序p的前驅pChileNode，q為其雙親q=pChileNode; pChileNode = pChileNode-rchild; p-data=pChileNode-data;/p的前驅pChileNodede 的關鍵值賦給pif(q!=p) /將刪除p轉化為刪除pChileNodede(最多只有左字樹)結點q-rchild=pChileNode-lchild;/p的左字樹有右孩子else q-lchild=pChileNode-lchild;/p的左字樹有右孩子free(pChileNode); return true; 四、上級結果及體會1、實際完成情況：實現二叉排序樹的建立、插入、刪除和查找功能； 支持的數據類型：二叉鏈表。2、程序的性能分析：假設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、源程序，程序運行時的初值和運行結果（見附件）4、程序的擴充和改進： 關鍵字類型可改為其他類型5、上機過程中出現的問題及其解決方案： 1）在編碼刪除結點DeleteNode函數的過程中遇到無法運行的問題，經請教老師，得到一定的提示：函數設計思路要理清； 2）在刪除根結點時出現不能執(zhí)行刪除結點左右子樹都存在的情況，魏近同學給出提示：結點轉換的思想； 6、收獲及體會： 通過這次的課程設計，我認識到：僅僅掌握課本上的知識是不夠的，在實際操作時，常常遇到一些問題，自己看不懂，更無法解決。不過，經過自己不斷的思考，嘗試著去更改代碼中出現的問題。雖然開始很困難，但在老師和同學的幫助下，我逐漸的熟悉了許多操作，為后繼工作的順利進行做了準備。個人的力量是薄弱的，