数据结构实验报告3.pdf

《数据结构实验报告3.pdf》由会员分享，可在线阅读，更多相关《数据结构实验报告3.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构实验报告实验名称：实验三二叉树学生姓名：班级：班内序号：学号：日期：2021 年1实验要求根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。其中二叉树的根本功能：1、二叉树的建立2、前序遍历二叉树3、中序遍历二叉树4、后序遍历二叉树5、按层序遍历二叉树6、求二叉树的深度7、求指定结点到根的路径8、二叉树的销毁2.程序分析2.1 存储结构二叉树：以数字的大小标示数据在数组中的顺序1325462.2 关键算法分析2.2.1 查找从指定节点到根的路径：关键算法：利用函数的递归调用进行遍历，利用返回值判断所指节点是否在所正确路径上。代码详细分析：1.传入参数：节点的指针，目标节点的数

2、据；2.判断传入指针是否为空，是那么返回0；3.判断传入节点的数据是否等于目标数据，是那么返回1；4.假设 3 中判断为否，那么令 m 等于将节点指针的左子指针作为参数传递递归调用此函数的返回值；那么令 n 等于将节点指针的右子指针作为参数传递递归调用此函数的返回值；假设 m+n 等于 0 那么返回 0，否那么输出该节点的数值并返回 1；5.在主函数中判断此递归函数的返回值，假设为0，那么输出“该节点不存在。设指定节点为 6，其中蓝色箭头代表输出，橙色箭头旁的数代表返回值算法的时间复杂度为 on、空间复杂度为 2。2.2.2 创立二叉树代码详细分析：假设数组下标 i 小于数组大小，那么：假设数

3、组内该位置的值不为 0，那么创立根节点并将数组内该位置的值赋值给根节点；递归创立左子树2i，递归创立右子树2i+1。否那么将根节点指针赋值为 0。否那么将根节点指针赋值为0。算法的时间复杂度为on、空间复杂度为 0。2.2.3 前序遍历代码详细分析：1.访问根节点；2.前序遍历访问根节点的左子树；3.前序遍历访问根节点的右子树。其中，中序遍历与前序遍历的不同仅在于：访问根节点为第二步。后序遍历与前序遍历的不同仅在于：访问根节点为第三步。算法的时间复杂度为 on、空间复杂度为 0。2.2.4 层序遍历代码详细分析：1.初始化空队列；2.假设根节点非空那么入队；3.如果队列不为空队头=队尾，那么：

4、3.1.队头元素出队并打印；3.2.假设该节点的左孩子非空，那么左孩子入队；3.3.假设该节点的右孩子非空，那么右孩子入队；66655443321123456算法的时间复杂度为 on、空间复杂度为 n。2.2.5 计算二叉树的深度代码详细分析：1.假设根节为空，那么返回0；2.假设根节点非空，那么：2.1.令 m 等于此函数遍历该节点左子树的返回值；2.2.令 n 等于此函数遍历该节点右子树的返回值；2.3.返回 m 和 n 大的那个。3.程序运行结果3.1 测试主函数流程：赋值测试条件构造二叉树二叉树的前序遍历二叉树的中序遍历二叉树的后序遍历二叉树的层序遍历i=查找从指定节点到根的路径i=0

5、？是输出该节点不存在j=求二叉树的深度j=0？是输出该二叉树为无结束3.2测试条件：test14=1,2,3,4,5,6,7,0,8,9,10,11,0,0;3.3 测试结论开始4.总结4.1 调试时出现的问题及解决的方法问题 1：create 函数在递归调用过程中会发生数组的访问越界，致使二叉树被额外赋值。解决方法:1.增加一参数 j 传递数组的大小，在给二叉树赋值前先进行判断，当数组的下标小于j 时才给二叉树赋值。2.在给数组赋值时多给每个叶子节点的左右子节点赋值为0。问题 2：当测试参数为字符时无法对标记为“0的节点进行正确操作。解决方法：将create函数中的一个判断条件：datai-1!=0，改为：datai-1!=0。4.2 心得体会经过本次试验我对二叉树有了更深一步的了解，熟练地掌握了二叉树的构造、四种遍历方法以及求二叉树的深度。同时通过本次实验，我能够更加娴熟地使用断点调试，通过分析参数的变化来发现、分析和解决错误；锻炼了我的动手能力、分析和解决问题的能力。1、下一步的改良