二叉查找树实现代码及运行结果

1、课程名称数据结构实验项目动态查找表的设计与实现实验目的实验内容(算法、实验目的实验内容(算法、程序、步骤和方法)通过实验加深对二叉查找树的理解，学会根据给定的数据建立二叉查找树，在二叉查找树中查找、插入、删除元素。实验内容: 实现抽象数据类型：二叉查找树。要求：实现下列操作:构造空表、销毁表、搜索指定关键字的元素、插入新元素、 删除指定关键字的元素、遍历表中所有元素.实验部分程序：/#define Maxsize 100typedef struct BiTNode /定义二叉树节点结构int data; 结点的数据域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 &); /删除二叉排序树的根结点 void InorderBST(BiTree); 中序遍历二叉排序树，并显示 int AMaxsize;void main()BiTree T,p;int

3、ch,keyword;char j=y;/控制程序结束与否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);/输入开始建立的二叉树的结点个数 scanf(%d,

4、 &n);printf(Please input every node:n);for(int i=0;ivn;i+)输入树的结点个数scanf(%d,&Ai);printf(Creat the BST!n);T=CreatBST(A,n);调用建树函数建树while(j!=n)printf(l.displayn); printf(2.searchn);printf(3.insertn); printf(4.deleten);printf(5.exitn);scanf( %d,&ch); /输入操作选项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); /输入要查找兀素的关键字 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); /输入要插入兀素的关键字 temp=InsertBST(T,keyword);/插 入 if(!temp) printf(%d has been existed!n,keyword); /该兀素已经存在 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); /输入要删除兀素的关键字 temp=DeleteBST(T,keyword);/删 除 if(!temp) printf(%d isnt existed!n,keyword); /该兀素不存在 else printf(Sucess to delete %dn,keyword); /成功删除 break;case 5: j=n;/跳出循环，结束程序printf(The program is over!nPress any key to shut off the window!n); getchar();getchar();BiTN

8、ode *CreatBST(int A,int n) 由数组A中的关键字建立一棵二叉排序树 BiTNode *bt=NULL;初始 bt 为空树int i=0;while(ivn)if(InsertBST(bt,Ai)=l)将数组 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);/递归调用中序遍历函数 if(T-rchild!=NULL)printf(”,”)；InorderBST(T-rchild); /递归调用中序遍历函数printf(”)”)；int SearchBST(BiTree T,int key,BiTree f,BiTree &p)在根指针T所指二叉排序树中递归的查找其关键字等于key的元素，若查找成功 则指针p指向该数据元素，并返回1,否则指针指向查找路径上访问的最后一 个结点并返回0,指针f指向T的双亲，其初始调用值为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);在左子树中继续查找 else tmp2=SearchBST(T-rchild,key,T,p); /在 右子树中继续查找 if(tmp1lltmp2) return 1; /若在子树中查找成功，向上级返回1else return 0; 否则返回 0int InsertBST(BiTree & T,int e)/当二叉排序树T中

11、不存在元素e时，插入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; 被插结点*s为新的根结点 else if(edata) p-lchild=s; /被插结点*$ 为左孩子 else p-rchild=s; 被插结点*s为右孩子 return 1; 成功插入else return 0; /树中已存在关键字为e的数据元素int DeleteBST(BiTree & T,in

12、t key)若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点 并返回1,否则返回0int tmp1,tmp2;tmp1=tmp2=0;if(!T) return 0; 不存在关键字等于key的数据元素else if(key=T-data) Delete(T); return 1; 找到关键字等于key的数据元素并删除它 else if(keyvT-data) tmp1=DeleteBST(T-lchild,key); /继续在左子树中删除 else tmp2=DeleteBST(T-rchild,key); /继续在右子树中删除 if(tmp1lltmp2) return

13、 1; /在子树中删除成功，返回1else return 0; 不存在该元素，返回0void Delete(BiTree &p)/在二叉排序树中删除结点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; /转左，然后向右走到尽头 p-data=s-data; /s指向被删结点的“前驱” 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