二叉排序树的实现.docx
《二叉排序树的实现.docx》由会员分享,可在线阅读,更多相关《二叉排序树的实现.docx(14页珍藏版)》请在第壹文秘上搜索。
1、目录1、设计内容22、概要设计21.1 所需模块21.2 功能模块关系图23 .算法描述31 .1模块流程图33 . 2各模块代码41.1.1 1主函数菜单模块 41.1.2 查找模块51.1.3 插入模块51.1.4 中序遍历模块51.1.5 删除模块64 .运行结果及算法分析71 .1运行结果74 . 2算法分析95 .实验心得96 .程序代码107 .参考资料12K设计内容用二叉链表为存储结构1)以回车(n)为输入结束标志,输入数列L,生成一棵二叉排序树T;2)对二叉排序树T作中序遍历,输出结果;3)输入元素X,查找二叉排序树T,假设存在含X的结点,那么删除该结点,并作中 序遍历(执行操
2、作;否那么输出信息“无x .2、概要设计2. 1所需模块根据程序功能,确定所需模块如下:1)主函数菜单模块;2)查找模块;3)插入模块;4)中序遍历模块;5)删除模块.2 . 2功能模块关系图二叉树排序树的实现主函数菜单模块删除艮一中序遍历模块-一插入模块.查找模块图1功能模块图3 .算法描述3.1 模块流程图Main()开始退出程序删除功能删除成功中序遍历功能显示相应的报错、运行结果及相应的界面.3.2.1主函数菜单模块该模块功能主要是给用户提供清楚的可操作界面,易于人机操作.并能很好 的调用其他各模块,使程序更加优化,思路更加清楚,结构更加明了,提升了程 序 的实用性.其算法如下:void
3、 main() node T=NULL;int num;int ch=O;node p=NULL;printf(,please input a list of numbers end with zero:);doscanf(%d,&num);if(!num) printf(you have finished your input!n);else insertBST(&T,num);while(num);printf(nn-the menu of the Opperationn); *主程序菜单*/printf(n 0: exit);printf(n 1: inorder travel the
4、tree);printf(n 2: delete);while(ch=ch)printf(n choose the opperation to continue:);scanf(%d,ch);switch(ch)case O: exit(O); *0退出 */case 1: printf( The result of the inorder traverse is:n );inorderTraverse(fcT); *1 中序遍历*/break;case 2: printf(, Please input the number you want to delete:);scanf(%d,&num
5、); *3删除某个结点 */if(scarchBST(T,num,NULL,(fep)T=Delete(T,num);printf( You have delete the number successfulIy !n );inordcrTraverse(data) (*p=t;retum (1);/*查找成功*/else if(keydata) searchBST(t-lchild,key,t,p);/*在左子树中继续查找*/else searchBST(t-rchild,key,t,p);/*在右子树中继续查找*/)4. 2. 3插入模块在二叉排序树中插入新结点,要保证插入后的二叉树仍符合
6、二叉排序树的定 义.插入过程:假设二叉排序树为空,那么待插入结点*p作为根结点插入到空树中; 当非空时,将待插结点关键字p-item和树根关键字t- item进行比拟,假设 p-item = t- item,那么无须插入,假设p- item item,那么插入到根的 左子 树中,假设p-item t- item,那么插入到根的右子树中.而子树中的插 入过程 和在树中的插入过程相同,如此进行下去,直到把结点*p作为一个新的树 叶插 入到二叉排序树中,或者直到发现树已有相同关键字的结点为止.其算法如 下:insertBST(node *t,int 卜必丫)/*插入函数*/(node p=NULL,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉排序树 实现
