1、計算機科學與技術系課程設計報告20082009學年第 二 學期課程 數據結構與算法課程設計名稱二叉排序樹運算學生姓名學號專業班級指導教師2009 年 6月一、問題分析和任務定義題目：二叉排序樹運算任務定義：對一組數據構造二叉排序樹，并在二叉排序樹中實現多種方式的查找。基本任務：（1）選擇合適的存儲結構構造二叉排序樹；（2） 對二叉排序樹T作中序遍歷，輸出結果；（3）在二叉排序樹中實現多種方式的查找，并給出二叉排序樹中插入和刪除的操作。（4）盡量給出“順序和鏈式”兩種不同結構下的操作，并比較。若要完成題目的要求，需要解決以下幾個問題：1、選擇一種數據結構存儲二叉樹的信息。2、建立一個新

2、的二叉排序樹3、在二叉排序樹中插入，刪除，查找相關節點二、數據結構的選擇和概要設計1、數據結構的選擇：題目要求選擇合適的存儲結構構造二叉排序樹，我選擇鏈式結構存儲。用鏈表的方式構造節點，存儲二叉排序樹中的節點！節點類型和指針類型如下！typedef struct nodeint key;int other ;struct node *lchild,*rchild;Bstnode;2、概要設計：為了完成所需的功能，需要的函數及其功能如下：main()：主函數模塊Bsearch()：查找相應的節點InsertBST ()：插入一個新節點CreateBST ()：創建一棵二叉排序樹Inorder (

3、)：對二叉排序樹進行中序遍歷menu()：主函數顯示菜單模塊DeleteBST ()：刪除節點主函數流程圖：開始結束調用menu函數輸入二叉排序樹中的元素輸入k=1k=2k=4顯示菜單調用子函數DeleteBST ()Inorder ()調用子函數Bsearch()調用子函數InsertBST ()Inorder ()zNk=3 圖（a）主函數流程圖子函數流程圖：插入子函數InsertBST ()的流程圖：開始x=p->keyNYp=p->lchildp=p->rchildx<p->keyYN 圖（b）子函數InsertBST ()的流程圖 子函數Bsearch(

4、p)的流程圖開始結束輸入需要查找的值調用查找函數并返回flag=0找不到值為%d的節點已找到該節點YN 圖（c）子函數Bsearch(p)的流程圖三、詳細設計和編碼二叉排序樹的基本操作1、 二叉排序樹的查找算法（1） 若二叉排序樹為空，則查找失敗。（2） 否則，將根結點的關鍵字與待查關鍵字進行比較，若相等，則查找成功；若根節點關鍵字大于待查值，則進入左子樹重復次步驟，否則，進入右子樹進行此步驟；若在查找過程中遇到二叉排序樹的葉子節點時，還沒有找到待查節點，則查找不成功。算法如下：Bstnode *Bsearch(Bstnode *t,int x)/查找Bstnode *p;int flag=0

5、;p=t;while(p!=NULL) if(p->key=x) printf("已找到該節點！");flag=1;return(p);break; if (x<p->key) p=p->lchild; else p=p->rchild; if(flag=0) printf("找不到值為%d的節點！",x); return NULL; 2、 二叉排序樹的節點插入算法在二叉排序樹中插入一個新節點，首先要查找該節點在二叉排序樹中是否已經存在。若二叉排序樹中不存在關鍵字等于x的節點，則插入。將一個關鍵字值為x的節點s插入到二叉排序

6、樹中，可以用下面的方法：（1） 若二叉排序樹為空，則關鍵字為x的節點s成為二叉排序樹的根（2） 若二叉排序樹非空，則將x與二叉排序樹根進行比較，如果x的值等于根節點關鍵值，則停止插入；如果x的根節點值小于根節點關鍵值，則將x插入左子樹；如果x的值大于根節點關鍵字的值，則將x插入右子樹。在左右兩個子樹的插入方法與整個二叉排序樹相同。算法如下：Bstnode *InsertBST(Bstnode *t,int x)/插入Bstnode *s,*p,*f;p=t;while (p!=NULL) f=p; /查找過程中，f指向*p的父節點if(x=p->key) return t; /二叉排序樹

7、中已有關鍵字為x的元素，無序插入if(x<p->key) p=p->lchild; else p=p->rchild;s=(Bstnode *)malloc(sizeof(Bstnode);s->key=x;s->lchild=NULL;s->rchild=NULL;if(t=NULL) return s; /原樹為空，新節點成為二叉排序樹的根if(x<f->key) f->lchild=s; /新節點作為*f的左孩子else f->rchild=s; /新節點作為*f的右孩子return t;3、 二叉排序樹的節點刪除算法在二

8、叉排序樹中刪除節點，首先要進行查找操作，以確定被刪除的節點是否在二叉排序樹中若不在，則不做任何操作；否則，假設要刪除的節點為*p，節點*p的父節點為*f，并假設*p是*f的左孩子。根據被刪除節點*p有無孩子，刪除部分可做以下3中情況討論：（1）若*p為葉子節點，則可令其父節點*f的左孩子指針域為空，直接將其刪除。（2）若*p節點只有右子樹或左子樹，則可以將p的左子樹或右子樹直接改為其雙親節點f的左子樹。（3）若*p既有左子樹又有右子樹；將節點*s為*p的中序前驅。首先找到*p的中序前驅節點*s，然后用節點*s的值代替節點*p的值，再將節點*s刪除，節點*s的原左子樹改為*s的雙親節點*q的右子

9、樹；算法如下：Bstnode *DeleteBST(Bstnode *t,int k)/刪除Bstnode *p,*f,*s,*q;p=t;f=NULL;while(p) /查找關鍵字為k的待刪節點*pif(p->key=k) break; /找到，則退出循環f=p; /節點*f為節點*p的父節點if(p->key>k) p=p->lchild;else p=p->rchild;if (p=NULL) return t; /若找不到，則返回原二叉排序樹的根指針if (p->lchild=NULL)|(p->rchild=NULL) /若*p無左孩子或右

10、孩子if(f=NULL) /若*p是原二叉排序樹的根 if(p->lchild=NULL) t=p->rchild;else t=p->lchild;else if (p->lchild=NULL) /若*p無左孩子if(f->lchild=p) f->lchild=p->rchild; /p是*f的左孩子else f->rchild=p->rchild; else if(f->lchild=p) /若*p無右孩子f->lchild=p->lchild; /p是*f的左孩子else f->lchild=p->l

11、child; /p是*f的右孩子free(p);else q=p;s=p->lchild; /若p有左右子樹while(s->rchild)q=s;s=s->rchild; /在*p的左子樹中查找最右下節點if(q=p) q->lchild=s->lchild;p->key=s->key; /將*s的值賦給*pfree(s);return t;四、上機調試1、 我所寫的程序和課本上的二叉排序樹基本相同！但是在調試過程中遇到了一些問題。我采用的是非遞歸思想進行遍歷，所以存在的基本的語法錯誤，問題主要在于函數和變量的定義。關鍵字和函數名的書寫。2、 時間，

12、空間性能分析：二叉排序樹的的查找與二分查找類似，是一個逐一縮小查找范圍的過程。具有n個節點的排序二叉樹是一棵深度為n的單枝樹，平均查找長度與順序查找相同，為（n+1）/2；即平均查找長度的數量級為O（n）。五測試結果及其分析1、輸入節點信息： 圖（1）輸入節點信息圖2、顯示菜單后，根據提示選擇操作選擇插入一個新節點 圖（2）插入新節點圖3、繼續選擇操作，查找一個已有的節點 圖（3）查找一個已有節點圖4、查找一個沒有的節點。 圖（4）查找一個沒有的節點圖5、刪除一個節點 圖（5）刪除一個節點圖6、若操作已完成，則退出程序。 圖（6）退出圖六、用戶使用說明1、用戶更具提示輸入二叉排序樹的節點信息并

13、且以0結束輸入2、根據菜單提示選擇相應的操作3、輸出的結果是中序遍歷后的結果七、參考文獻1王昆侖,李紅等編著. 數據結構與算法. 北京:中國鐵道出版社,2007.2李業麗，鄭良斌編著。數據結構（c）實驗教程。北京理工大學出版社 2005八、附錄（源代碼）#include "stdio.h"#include "malloc.h"#define NULL 0typedef struct nodeint key;int other ;struct node *lchild,*rchild;Bstnode;Bstnode *Bsearch(Bstnode *t,

14、int x)/查找Bstnode *p;int flag=0;p=t;while(p!=NULL) if(p->key=x) printf("已找到該節點！");flag=1;return(p);break; if (x<p->key) p=p->lchild; else p=p->rchild; if(flag=0) printf("找不到值為%d的節點！",x); return NULL; Bstnode *InsertBST(Bstnode *t,int x)/插入Bstnode *s,*p,*f;p=t;while

15、(p!=NULL) f=p; /查找過程中，f指向*p的父節點if(x=p->key) return t; /二叉排序樹中已有關鍵字為x的元素，無序插入if(x<p->key) p=p->lchild; else p=p->rchild;s=(Bstnode *)malloc(sizeof(Bstnode);s->key=x;s->lchild=NULL;s->rchild=NULL;if(t=NULL) return s; /原樹為空，新節點成為二叉排序樹的根if(x<f->key) f->lchild=s; /新節點作為*f

16、的左孩子else f->rchild=s; /新節點作為*f的右孩子return t; Bstnode *CreateBST()/創建一個新的二叉樹Bstnode *t;int key; t=NULL; /設置二叉排序樹的初態為空scanf("%d",&key); /讀入第一個節點的關鍵字while(key!=0)t=InsertBST(t,key);scanf("%d",&key);return t;void Inorder(Bstnode *T)/中序遍歷if(T) /若二叉樹不空Inorder(T->lchild); /

17、中序遍歷左子樹printf("%4d",T->key); /訪問根節點Inorder(T->rchild); /中序遍歷右子樹Bstnode *DeleteBST(Bstnode *t,int k)/刪除Bstnode *p,*f,*s,*q;p=t;f=NULL;while(p) /查找關鍵字為k的待刪節點*pif(p->key=k) break; /找到，則退出循環f=p; /節點*f為節點*p的父節點if(p->key>k) p=p->lchild;else p=p->rchild;if (p=NULL) return t;

18、/若找不到，則返回原二叉排序樹的根指針if (p->lchild=NULL)|(p->rchild=NULL) /若*p無左孩子或右孩子if(f=NULL) /若*p是原二叉排序樹的根 if(p->lchild=NULL) t=p->rchild;else t=p->lchild;else if (p->lchild=NULL) /若*p無左孩子if(f->lchild=p) f->lchild=p->rchild; /p是*f的左孩子else f->rchild=p->rchild; else if(f->lchild=

19、p) /若*p無右孩子f->lchild=p->lchild; /p是*f的左孩子else f->lchild=p->lchild; /p是*f的右孩子free(p);else q=p;s=p->lchild; /若p有左右子樹while(s->rchild)q=s;s=s->rchild; /在*p的左子樹中查找最右下節點if(q=p) q->lchild=s->lchild;p->key=s->key; /將*s的值賦給*pfree(s);return t;void menu() printf("n"); printf("1-插入節點-n"); printf("n"); printf("2-查找節點-n"); printf("n"); printf("3-刪除節點-n"); printf("n"); printf("4-退出-n"); printf("n");void main()Bstnode *tree,*p;int seai,deli,x;int k,flag=1;printf("請輸入節點信息，并以0結束: