二叉排序树实验报告

1、实验3实现二叉排序树一 实验目的：1.掌握二叉排序树的定义以及基本操作的实现算法。2编写实验报告3。 熟练掌握顺序查找、折半查找及二叉排序树、平衡二叉树上的查找、插入和删除 的方法。问题描述：实现二叉排序树的查找、插入和删除操作。步骤：1定义二叉链表结构存储二叉排序树。2实现二叉排序树的查找、插入和删除操作算法。3设计测试用二叉排序树并使用插入算法创建对应的内存二叉树，能够测试查找、插入和删 除算法的边界。4完成实验的实验报告，报告的格式采用数据结构题集的模板格式。两周之后提交。 设备和环境：PC计算机、Windows操作系统、C/C+开发环境结论：能够理解和掌握二叉排序树的基本算法。二需求分

2、析查找是数据处理的重要操作。请设计并实现基于二叉排序树的商品信息查询 算法。完成信息的查询、插入、删除、查询频度的统计等功能。三、概要设计建立二叉排序树，并实现基本操作，验证其准确性。四、详细设计#include#includetypedef struct nodeint key;struct node*lch,*rch;bitnode;bitnode*creat_bt();/二叉顺序树的建立bitnode*search(bitnode*root,int data);/查找是 data 存在与否，若不存在返回待查找data的父结点指针void searchx(bitnode*root,int

3、data);/判断所查找的元素data是否存在，并给出相应的提示void display(bitnode*t);/中序遍历二叉树，以验证二叉树的正确bitnode*deletex(bitnode*t,int data);/在二叉树中删除key为data的结点bitnode*add(bitnode*t,int k);/在二叉树中添加 key为data的结点int n=l;/用于记数的全局变量void main()bitnode*t;int a,key; do printf(*王菜单 *) printf(n 1.建立二叉树)；printf(n 2.删除二叉树中指定元素为key的结点)； print

4、f(n 3.向二叉树中添加指定元素为key的结点)； printf(n 4.在二叉树中查找指定元素为key的结点)； printf(n 5.中序遍历二叉树，以检验正确性); printf(n 6.结束程序运行);printf(n 请输入您的选择(1,2,3,4,5,6):); scanf(%d, &a);switch(a) case 1: t=creat_bt();break;case 2:printf(请输入所要删除的结点的key值：);scanf(%d, &key);t=deletex(t,key);break; case 3:printf(请输入要添加的元素的key值作为第0个结点：，n

5、+);scanf(%d, &key);t=add(t,key);break; case 4:printf(请输入所要查找的元素的key值：);scanf(%d, &key);searchx(t,key);break; case 5: display(t);printf(nnn);printf(nnn);while(a!=6);printf(GOOD BYE!); bitnode*creat_bt()/二叉顺序树的建立int k;bitnode*t=NULL,*s,*f;printf(请输第d个关键字key的值(以输入0为结束)：，n); scanf(%d, &k);while(k!=0)n+;

6、/用于记数s=(bitnode*)malloc(sizeof(bitnode); s-key=k;s-lch=NULL;s-rch=NULL;if(t=NULL)t=s;else f=search(t,k);if(k=f-key)/已存在 k元素 printf(n提示：已存在该元素，请重新输入);n_；else if(kkey)f_lch=s;else f_rch=s;printf(请输入第d个关键字key的值(以输入0为结束)：，n); scanf(%d, &k);return t;bitnode*search(bitnode*root,int data)/查找是 data 存在与否，若不存

7、在返回待查找data的父结点指针bitnode*p=NULL,*q=root;while(q)p=q;/已存在元素/已存在元素data,返回data所在的位置qelse if(datakey)q=q-lch;else q=q-rch;return p;/返回待查找data的父结点指针/判断所查找的元素void searchx(bitnode*root,int data) data/判断所查找的元素bitnode*p=NULL,*q=root;int tag=0;while(q & tag=0)p=q;if(data=q-key) tag=l;break;/找到元素 dataelse if(da

8、takey)q=q-lch;else q=q-rch;if(tag=1)printf(n二叉树中存在所查找的元素%d,data);else printf(n二叉树中不存在所查找的元素%d,data);/在二叉树中删除keybitnode*deletex(bitnode*t,int data) 为/在二叉树中删除key bitnode*p,*f,*s,*q;int flag=0;p=t;f=NULL; while(p!=NULL) if(p-key=data) flag=1;break; f=p;if(p-keydata)p=p-lch;else p=p-rch;if(p=NULL)printf

9、(在此二叉树中无此值，无法完成删除操作。);return t;/无此值if(p-lch=NULL)if(f=NULL)t=p-rch;else if(f-lch=p) f-lch=p-rch;else f-rch=p-rch;free(p);elseq=p;s=p_lch;while(s-rch) q=s;s=s_rch;if(q=p)q_lch=s_lch;else q_rch=s_lch;p_key=s_key;free(s);n_;return t;bitnode *add(bitnode *t,int k)/在二叉树中添加 key为data的结点bitnode*s,*f;s=(bitn

10、ode*)malloc(sizeof(bitnode);s_key=k;s_lch=NULL;s_rch=NULL;f=search(t,k);if(k=f_key)/已存在 k 元素printf(n提示：已存在该元素，请重新输入要添加的元素的key值作为第0 个结点：)；else if(kkey) f_lch=s;else f_rch=s;return t;void display(bitnode*t)/中序遍历二叉树，以验证二叉树的正确性if(t)display(t_lch);printf(%5d,t_key); display(t_rch);五、调试过程应该划分模块，对不同的操作应用不同

11、的函数来完成。在调试过程中，关于 添加节点的那部分比较难，没能实现文件的储存和读取功能（其实本来就没 打算实现）六、结果分析这个程序有人性化的界面，还可以用中序遍历输出明了的建树的结果，可以很方便地来 操作。以下是操作界面截图： G:micro 5oft_visua lc6M SDev98BinDeb u gzj. exe点点 点结结 结的的 的ey門系验a!2 3 4 5 6 7 0 :豆豆豆豆豆豆豆 菽士口士口士口士口士口士口士口T-#士勺勺7勺勺勺勺勺. 宀 “7.斗/斗/斗/斗/斗/斗. 0 0 0 0 0 0 0 0-iAI.A(lll以以以以以以 .5I.-值值值值值值值LX 一-r.-J“ ?韦TIDg中馨叉行,4書的的的的的的斗胃$二运,3的历序,2y y y y y y y eeeeeee ykkkkkkkkeIHMMMMH于 二亠舟软宀子键键键键键键键 4 5 6 2 3 4 5 6 7 8 您/第第第第第第第 AMAAAAAAA .:j 刖 j 刖 j 刖 j FFk一 刖宀一刖宀一刖宀一刖宀一別主冃主冃主冃主冃青青青青青屮6 5 A 3 2 1 鼬論刍鋼 蔽邪则l| I舉煤 a谕斂眉1 il I l沏胡茸畫眉眉 訂丽