二叉查找樹實(shí)現(xiàn)代碼及運(yùn)行結(jié)果

1、課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)項(xiàng)目動(dòng)態(tài)查找表的設(shè)計(jì)與實(shí)現(xiàn)實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)內(nèi)容(算法、實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)內(nèi)容(算法、程序、步驟和方法)通過實(shí)驗(yàn)加深對(duì)二叉查找樹的理解，學(xué)會(huì)根據(jù)給定的數(shù)據(jù)建立二叉查找樹，在二叉查找樹中查找、插入、刪除元素。實(shí)驗(yàn)內(nèi)容: 實(shí)現(xiàn)抽象數(shù)據(jù)類型：二叉查找樹。要求：實(shí)現(xiàn)下列操作:構(gòu)造空表、銷毀表、搜索指定關(guān)鍵字的元素、插入新元素、 刪除指定關(guān)鍵字的元素、遍歷表中所有元素.實(shí)驗(yàn)部分程序：/#define Maxsize 100typedef struct BiTNode /定義二叉樹節(jié)點(diǎn)結(jié)構(gòu)int data; 結(jié)點(diǎn)的數(shù)據(jù)域struct BiTNode *lchild,*rchild; 左右孩子指針域

2、BiTNode,*BiTree;BiTNode *CreatBST(int A,int n);int SearchBST(BiTree,int,BiTree,BiTree&); /在二叉排序樹中查找元素int InsertBST(BiTree &,i nt); /在二叉排序樹中插入元素int DeleteBST(BiTree &,i nt); /在二叉排序樹中刪除元素 void Delete(BiTree &); /刪除二叉排序樹的根結(jié)點(diǎn) void InorderBST(BiTree); 中序遍歷二叉排序樹，并顯示 int AMaxsize;void main()BiTree T,p;int

3、ch,keyword;char j=y;/控制程序結(jié)束與否int temp;printf(Identificationn);printf(This program will show how to operate to a Binary Sort Tree.n);printf(You can display all elems,search a elem,ninsert a elem,delete a elem.n); printf(n);int n;printf(Please input the number of the node:n);/輸入開始建立的二叉樹的結(jié)點(diǎn)個(gè)數(shù) scanf(%d,

4、 &n);printf(Please input every node:n);for(int i=0;ivn;i+)輸入樹的結(jié)點(diǎn)個(gè)數(shù)scanf(%d,&Ai);printf(Creat the BST!n);T=CreatBST(A,n);調(diào)用建樹函數(shù)建樹while(j!=n)printf(l.displayn); printf(2.searchn);printf(3.insertn); printf(4.deleten);printf(5.exitn);scanf( %d,&ch); /輸入操作選項(xiàng)switch(ch) case 1:if(!T) printf(The BST has no

5、elem.n);else InorderBST(T);printf(n); 中序遍歷并顯示 break;case 2:printf(Input the keyword of elem to be searched(a number):); scanf( %d, &keyword); /輸入要查找兀素的關(guān)鍵字 temp=SearchBST(T,keyword,NULL,p);/查找 if(!temp) printf(%d isnt existed!n,keyword); /沒有找到 else printf(%d has been found!n,keyword); /成功找到 break;cas

6、e 3:printf(Input the keyword of elem to be inserted(a number):); scanf( %d, &keyword); /輸入要插入兀素的關(guān)鍵字 temp=InsertBST(T,keyword);/插 入 if(!temp) printf(%d has been existed!n,keyword); /該兀素已經(jīng)存在 else printf(Sucess to inert %d!n,keyword); /成功插入 break;case 4:printf(Input the keyword of elem to be deleted(a

7、number):); scanf( %d, &keyword); /輸入要?jiǎng)h除兀素的關(guān)鍵字 temp=DeleteBST(T,keyword);/刪 除 if(!temp) printf(%d isnt existed!n,keyword); /該兀素不存在 else printf(Sucess to delete %dn,keyword); /成功刪除 break;case 5: j=n;/跳出循環(huán)，結(jié)束程序printf(The program is over!nPress any key to shut off the window!n); getchar();getchar();BiTN

8、ode *CreatBST(int A,int n) 由數(shù)組A中的關(guān)鍵字建立一棵二叉排序樹 BiTNode *bt=NULL;初始 bt 為空樹int i=0;while(ivn)if(InsertBST(bt,Ai)=l)將數(shù)組 Ai插入二叉排序樹 bt 中printf( Step%d, Insert： %d:,i+1,Ai);InorderBST(bt); printf(n);i+;return bt;返回建立的二叉排序樹的根指針void InorderBST(BiTree T)以中序方式遍歷二叉排序樹T,并顯示if(T!=NULL)printf(%d,T-data);if(T-lchil

9、d!=NULLIIT-rchild!=NULL)printf();InorderBST(T-lchild);/遞歸調(diào)用中序遍歷函數(shù) if(T-rchild!=NULL)printf(”,”)；InorderBST(T-rchild); /遞歸調(diào)用中序遍歷函數(shù)printf(”)”)；int SearchBST(BiTree T,int key,BiTree f,BiTree &p)在根指針T所指二叉排序樹中遞歸的查找其關(guān)鍵字等于key的元素，若查找成功 則指針p指向該數(shù)據(jù)元素，并返回1,否則指針指向查找路徑上訪問的最后一 個(gè)結(jié)點(diǎn)并返回0,指針f指向T的雙親，其初始調(diào)用值為NULLint tmp1

10、,tmp2;tmp1=tmp2=0;if(!T) p=f;return 0; 查找不成功else if(key=T-data) p=T;return 1; /查找成功else if(keyvT-data) tmp1=SearchBST(T-lchild,key,T,p);在左子樹中繼續(xù)查找 else tmp2=SearchBST(T-rchild,key,T,p); /在 右子樹中繼續(xù)查找 if(tmp1lltmp2) return 1; /若在子樹中查找成功，向上級(jí)返回1else return 0; 否則返回 0int InsertBST(BiTree & T,int e)/當(dāng)二叉排序樹T中

11、不存在元素e時(shí)，插入e并返回1,否則返回0BiTree p,s; if(!SearchBST(T,e,NULL,p) /查找不成功，插入 s=(BiTree)malloc(sizeof(BiTNode); s-data=e;s-lchild=s-rchild=NULL;if(!p) T=s; 被插結(jié)點(diǎn)*s為新的根結(jié)點(diǎn) else if(edata) p-lchild=s; /被插結(jié)點(diǎn)*$ 為左孩子 else p-rchild=s; 被插結(jié)點(diǎn)*s為右孩子 return 1; 成功插入else return 0; /樹中已存在關(guān)鍵字為e的數(shù)據(jù)元素int DeleteBST(BiTree & T,in

12、t key)若二叉排序樹T中存在關(guān)鍵字等于key的數(shù)據(jù)元素時(shí)，則刪除該數(shù)據(jù)元素結(jié)點(diǎn) 并返回1,否則返回0int tmp1,tmp2;tmp1=tmp2=0;if(!T) return 0; 不存在關(guān)鍵字等于key的數(shù)據(jù)元素else if(key=T-data) Delete(T); return 1; 找到關(guān)鍵字等于key的數(shù)據(jù)元素并刪除它 else if(keyvT-data) tmp1=DeleteBST(T-lchild,key); /繼續(xù)在左子樹中刪除 else tmp2=DeleteBST(T-rchild,key); /繼續(xù)在右子樹中刪除 if(tmp1lltmp2) return

13、 1; /在子樹中刪除成功，返回1else return 0; 不存在該元素，返回0void Delete(BiTree &p)/在二叉排序樹中刪除結(jié)點(diǎn)p,并重接它的左或右子樹BiTree s,q; if(!p-rchild) /右子樹空，只需重接它的左子樹q=p; p=p-lchild; free(q);else if(!p-lchild) /左子樹空，只需重接它的右子樹q=p; p=p-rchild; free(q);else 左右子樹均不空q=p;s=p-lchild;while(s-rchild)q=s;s=s-rchild; /轉(zhuǎn)左，然后向右走到盡頭 p-data=s-data; /s指向被刪結(jié)點(diǎn)的“前驅(qū)” if(q!=p) q-rchild=s-rchild; 重接*q 的右子樹 else q-lchild=s-lchild; 重接*q 的左子樹 free(s);1 dent if icat ion This program will shou hou to operate to a Binary Sort Tree.You can display all elems,search a elem,ninseit a elem,delete a elemPlease input the number of the node