数据结构实验报告3.doc

数据结构实验报告实验名称： 实验三二叉树学生姓名：班 级：班内序号： 学 号： 日 期： 2012年1实验要求根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。 其中二叉树的基本功能：1、二叉树的建立2、前序遍历二叉树3、中序遍历二叉树4、后序遍历二叉树5、按层序遍历二叉树6、求二叉树的深度7、求指定结点到根的路径8、二叉树的销毁2. 程序分析2.1 存储结构二叉树： 以数字的大小标示数据在数组中的顺序 1 3 2 6 5 4 2.2 关键算法分析2.2.1查找从指定节点到根的路径：关键算法： 利用函数的递归调用进行遍历，利用返回值判断所指节点是否在所正确路径上。代码详细分析： 1.传入参数：节点的指针，目标节点的数据； 2.判断传入指针是否为空，是则返回0； 3.判断传入节点的数据是否等于目标数据，是则返回1； 4.若3中判断为否，则令m等于将节点指针的左子指针作为参数传递递归调用此函数的返回值；则令n等于将节点指针的右子指针作为参数传递递归调用此函数的返回值；若m+n等于0则返回0，否则输出该节点的数值并返回1； 5.在主函数中判断此递归函数的返回值，若为0，则输出“该节点不存在”。 设指定节点为6，其中蓝色箭头代表输出，橙色箭头旁的数代表返回值算法的时间复杂度为o（n）、空间复杂度为2。2.2.2创建二叉树 代码详细分析：若数组下标i小于数组大小，则：若数组内该位置的值不为0，则创建根节点并将数组内该位置的值赋值给根节点；递归创建左子树（2i），递归创建右子树（2i+1）。否则将根节点指针赋值为0。 否则将根节点指针赋值为0。 算法的时间复杂度为o（n）、空间复杂度为0。2.2.3前序遍历 代码详细分析：1. 访问根节点；2. 前序遍历访问根节点的左子树；3. 前序遍历访问根节点的右子树。 （其中，中序遍历与前序遍历的不同仅在于：访问根节点为第二步。后序遍历与前序遍历的不同仅在于：访问根节点为第三步。） 算法的时间复杂度为o（n）、空间复杂度为0。 2.2.4层序遍历 代码详细分析：1. 初始化空队列；2. 若根节点非空则入队；3. 如果队列不为空（队头=队尾），则：3.1. 队头元素出队并打印；3.2. 若该节点的左孩子非空，则左孩子入队；3.3. 若该节点的右孩子非空，则右孩子入队； 6 6 6 5 5 4 4 3 3 2 1 1 2 3 4 5 6算法的时间复杂度为o（n）、空间复杂度为n。 2.2.5计算二叉树的深度 代码详细分析：1. 若根节为空，则返回0；2. 若根节点非空，则：2.1. 令m等于此函数遍历该节点左子树的返回值；2.2. 令n等于此函数遍历该节点右子树的返回值；2.3. 返回m和n大的那个。3. 程序运行结果3.1测试主函数流程： 开始赋值测试条件i=0？i=查找从指定节点到根的路径二叉树的层序遍历二叉树的后序遍历二叉树的中序遍历二叉树的前序遍历构造二叉树是输出该节点不存在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心得体会经过本次试验我对二叉树有了更深一步的了解，熟练地掌握了二叉树的构造、四种遍历方法以及