二叉排序树的实现(最终版).doc

二叉排序树的实现(最终版).doc

ID:58489358

大小:886.50 KB

页数:33页

时间:2020-05-17

二叉排序树的实现(最终版).doc_第1页
二叉排序树的实现(最终版).doc_第2页
二叉排序树的实现(最终版).doc_第3页
二叉排序树的实现(最终版).doc_第4页
二叉排序树的实现(最终版).doc_第5页
资源描述:

《二叉排序树的实现(最终版).doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、实验报告课程名称数据结构课程设计题目名称二叉树的实现学生学院应用数学学院专业班级14信安1班学号学生姓名阮志敏指导教师刘志煌2016年12月9日二叉排序树的实现一、内容和要求。1)编程实现二叉排序树,包括生成、插入、删除;2)对二叉排序树进行先根、中根和后根非递归遍历;3)每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。4)分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率,并说明在什么情况下二叉排序树效率高,为什么?5)

2、格式按照作业的要求,对数据测试,分析,总结和改进的工作要做详细一点。二、解决方案和关键代码1.二叉排序树的实现。1)首先定义二叉树的结构体,代码如下:structTreeNode;typedefstructTreeNode*TreePosition;typedefstructTreeNode*SearchTree;typedefstructTreeNode*Tree;typedefintTreeElementType;structTreeNode{//二叉树TreeElementTypeelemen

3、t;//节点中的元素SearchTreeleft;//左儿子SearchTreeright;//右儿子intleght;//节点的深度,用于打印intposition;//节点的位置,用于打印};1)实现插入和生成二叉树节点的方法。在这里用到了递归插入的方法。SearchTreeinsertTreeNode(TreeElementTypex,SearchTreetree){if(tree==NULL){tree=makeTree(x,NULL,NULL);//插入在该处}elseif(x

4、>element){tree->left=insertTreeNode(x,tree->left);}elseif(x>tree->element){tree->right=insertTreeNode(x,tree->right);}//如果相等,什么也不做returntree;}当tree==NULL时,就是递归终止的条件,也是插入该节点的地方,在这里,用makeTree()方法创建一个节点,其代码如下:staticSearchTreemakeTree(TreeElementTypex,Sear

5、chTreeleft,SearchTreeright){SearchTreenode=(SearchTree)malloc(sizeof(structTreeNode));if(node==NULL){printf("makeTreeNodefail!");}else{node->element=x;node->left=left;node->right=right;}returnnode;}1)实现二叉树节点删除的方法。删除节点时有3种情况:情况一:被删除的节点同时含有左儿子和右儿子。在这种情

6、况下,必须找出一个合适的节点来替代被删除的节点。由于二叉树的特性,被删除节点右子树中的节点都比左子树节点大,因此,可以替代原节点的节点必然在被删除节点的右子树中,并且是右子树的最小节点。所以,在这种情况下,应该把被删除节点的右子树中最小节点替代被删除节点。情况二:被删除节点只有一个子节点。显然,应该把它的子节点替代它。情况三:被删除节点没有子节点。此时,直接删除它。具体代码如下,同样使用递归删除的方法:SearchTreedeleteTreeNode(TreeElementTypex,SearchT

7、reetree){TreePositiontmpNode;if(tree==NULL){//到叶节点了,还没找到可以删除的printf("notfound!");}elseif(xelement){tree->left=deleteTreeNode(x,tree->left);}elseif(x>tree->element){tree->right=deleteTreeNode(x,tree->right);}elseif(x==tree->element){if(tree->le

8、ft&&tree->right){tmpNode=findMin(tree->right);//找出右子树中最小的tree->element=tmpNode->element;//把右子树中最小的值给当前树>节点//把tree右子树中最小值的节点删除了,那个要删除的节点不可能有左>儿子tree->right=deleteTreeNode(tree->element,tree->right);}else{//只有一个子节点,或者没有子节点tmpNode=tree;if(

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。