二叉树遍历C语言(递归,非递归)六种算法(考试类别)

仅供参考数据结构（双语）——项目文档报告用两种方式实现表达式自动计算专业：班级：指导教师：姓名：学号：贝眉贝脚可一键删除I仅供参与目录一、设计思想.01TOC\o"1-5"\h\z算法流程图.02源代码.04运行结果.11遇到的问题及解决.11心得体会.12页眉K页眉K脚可-键删除仅供参考一、设计思想二叉树的遍历分为三种方式，分别是先序遍历，中序遍历和后序遍历。先序遍历实现的顺序是：根左右，中序遍历实现的是：左根右，后续遍历实现的是：左右根。根据不同的算法分，又分为递归遍历和非递归遍历。递归算法：1?先序遍历：先序遍历就是首先判断根结点是否为空，为空则停止遍历，不为空则将左子作为新的根结点重新进行上述判断，左子遍历结束后，再将右子作为根结点判断，直至结束。到达每一个结点时，打印该结点数据，即得先序遍历结果。2?中序遍历：中序遍历是首先判断该结点是否为空，为空则结束，不为空则将左子作为根结点再进行判断，打印左子，然后打印二叉树的根结点，最后再将右子作为参数进行判断，打印右子，直至结束。3?后续遍历：指针到达一个结点时，判断该结点是否为空，为空则停止遍历，不为空则将左子作为新的结点参数进行判断，打印左子。左子判断完成后，将右子作为结点参数传入判断，打印右子。左右子判断完成后打印根结点。非递归算法：1金序遍历：首先建立一个栈，当指针到达根结点时，打印根结点，判断根结点是否有左子和右子。有左子和右子的话就打印左子同时将右子入栈，将左子作为新的根结点进行判断，方法同上。若当前结点没有左子，则直接将右子打印，同时将右子作为新的根结点判断。若当前结点没有右子，则打印左子，同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子，则当前结点为叶子结点，此时将从栈中出栈一个元素，作为当前的根结点，打印结点元素，同时将当前结点同样按上述方法判断，依次进行。直至当前结点的左右子都为空，且栈为空时，遍历结束。2?中序遍历：首先建立一个栈，定义一个常量flag（flag为0或者1）,用flag记录结点的左子是否去过，没有去过为0,去过为1,默认为0情先将指针指向根结点，将根结点入栈，然后将指针指向左子，左子作为新的结点，将新结点入栈，然后再将指针指向当前结点的左子，直至左子为空，则指针返回，flag置1,出栈一个元素，作为当前结点，打印该结点，然后判断flag,flag为1则将指针指向当前结点右子，将右子作为新的结点，结点入栈，再次进行上面的判断，直至当前结点右子也为空，则再出栈一个元素作为当前结点，一直到结束，使得当前结点右子为空，且栈空，遍历结束。3?后续遍历：首先建立两个栈，然后定义两个常量。第一个为status,取值为0,1,2.0代表左右子都没有去过，1代表去过左子，2,代表左右子都去过，默认为0。第二个常量为flag,取值为0或者1,0代表进左栈，1代表进右栈。初始时指针指向根结点，判断根结点是否有左子，有左子则，将根结点入左栈，status置0,flag置0,若没有左子则判断结点有没有右子，有右子就把结点入右栈，status置0,flag置1,若左右子都没有，则打印该结点，弁将指针指向空，此时判断flag,若flag为0,则从左栈出栈一个元素作为当前结点，重新判断；若flag为1则从右栈出栈一个元素作为当前结点，重新判断左右子是否去过，若status为1,则判断该结点有没有右子，若有右子，则将该结点入右栈，status置1,flag置1,若没有右子，则打印当前结点，弁将指针置空，然后再次判断flago若当前结点status为2,且栈为空，则遍历结束。若指针指向了左子，则将左子作为当前结点，判断其左右子情况，按上述方法处理，直至遍历结束。

二、算法流程图页眉贞脚可一键删除仅洪琴考二、算法流程图页眉贞脚可一键删除仅洪琴考图1二叉树的建立用先序方法建立二叉树，为每个结点定义左右子，用0代表空，得到上述二叉树节点和性淳v/学悔节本是r＜为主索引指向左子

一子人栈图2昨递归二文树遍，万先序首先建立一个栈，当指针到达根结点时，打印根结点，判断根结点是否有左子和右子。有左子和右子的话就打印左子同时将右子入栈，将左子作为新的根结点进行判断，方法同上。若当前结点没有左子，则直接将右子打印，同时将右子作为新的根结点判断。若当前结点没有右子,则打印左子，同时将左子作为新的根结点判断