《数据结构》第六次实验报告学生姓名学生班级学生学号指导老师一、实验内容1) 采用二叉树链表作为存储结构,完成二叉树的建立,先序、中序和后序以及按层次遍历的操作,求所有叶子及结点总数的操作。2) 输出树的深度,最大元,最小元。二、需求分析遍历二叉树首先有三种方法,即先序遍历,中序遍历和后序遍历。递归方法比较简单, 首先获得结点指针如果指针不为空,且有左子, 从左子递归到下一层,如果没有左子,从右子递归到下一层,如果指针为空,则结束一层递归调用。直到递归全部结束。下面重点来讲述非递归方法:首先介绍先序遍历:先序遍历的顺序是根左 右,也就是说先访问根结点然后访问其左子再然后访问其右子。具体算法实现如下:如果结点的指针不为空,结点指针入栈,输出相应结点的数据,同时指针指向其左子, 如果结点的指针为空, 表示左子树访问结束,栈顶结点指针出栈,指针指向其右子,对其右子树进行访问,如此循环,直至结点指针和栈均为空时,遍历结束。再次介绍中序遍历:中序遍历的顺序是左根 右,中序遍历和先序遍历思想差不多,只是打印顺序稍有变化。具体实现算法如下: 如果结点指针不为空, 结点入栈,指针指向其左子,如果指针为空, 表示左子树访问完成, 则栈顶结点指针出栈, 并输出相应结点的数据,同时指针指向其右子, 对其右子树进行访问。 如此循环直至结点指针和栈均为空,遍历结束。最后介绍后序遍历:后序遍历的顺序是左右 根,后序遍历是比较难的一种,首先需要建立两个栈,一个用来存放结点的指针, 另一个存放标志位, 也是首先访问根结点, 如果结点的指针不为空,根结点入栈,与之对应的标志位也随之入标志位栈,并赋值0,表示该结点的右子还没有访问,指针指向该结点的左子, 如果结点指针为空, 表示左子访问完成, 父结点出栈, 与之对应的标志位也随之出栈,如果相应的标志位值为 0,表示右子树还没有访问,指针指向其右子,父结点再次入栈,与之对应的标志位也入栈,但要给标志位赋值为1,表示右子访问过。如果相应的标志位值为 1,表示右子树已经访问完成,此时要输出相应结点的数据,同时将结点指针赋值为空,如此循环直至结点指针和栈均为空,遍历结束。三、详细设计源代码:#include #define MAX 100 // 表示栈的最大容量#define FULL 99// 表示栈满#define EMPTY -1// 表示栈空typedef struct Tnode // 定义结点{ char data;//存储结点...