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