二叉树遍历C语言递归非递归六种算法样稿.doc

数据结构（双语）
——项目文档汇报
用两种方法实现表示式自动计算
专 业：
班 级：
指导老师：
姓 名：
学 号：
目 录
一、设计思想……………………………………………………….01
二、算法步骤图…………………………………………………….02
三、源代码………………………………………………………….04
四、运行结果……………………………………………………….11
五、碰到问题及处理…………………………………………….11
六、心得体会……………………………………………………….12
一、设计思想
二叉树遍历分为三种方法，分别是先序遍历，中序遍历和后序遍历。先序遍历实现次序是：根左右，中序遍历实现是：左根右，后续遍历实现是：左右根。依据不一样算法分，又分为递归遍历和非递归遍历。
递归算法：
1．先序遍历：先序遍历就是首先判定根结点是否为空，为空则停止遍历，不为空则将左子作为新根结点重新进行上述判定，左子遍历结束后，再将右子作为根结点判定，直至结束。抵达每一个结点时，打印该结点数据，即得先序遍历结果。
：中序遍历是首先判定该结点是否为空，为空则结束，不为空则将左子作为根结点再进行判定，打印左子，然后打印二叉树根结点，最终再将右子作为参数进行判定，打印右子，直至结束。
：指针抵达一个结点时，判定该结点是否为空，为空则停止遍历，不为空则将左子作为新结点参数进行判定，打印左子。左子判定完成后，将右子作为结点参数传入判定，打印右子。左右子判定完成后打印根结点。
非递归算法：
：首先建立一个栈，当指针抵达根结点时，打印根结点，判定根结点是否有左子和右子。有左子和右子话就打印左子同时将右子入栈，将左子作为新根结点进行判定，方法同上。若目前结点没有左子，则直接将右子打印，同时将右子作为新根结点判定。若目前结点没有右子，则打印左子，同时将左子作为新根结点判定。若目前结点既没有左子也没有右子，则目前结点为叶子结点，此时将从栈中出栈一个元素，作为目前根结点，打印结点元素，同时将目前结点一样按上述方法判定，依次进行。直至目前结点左右子全部为空，且栈为空时，遍历结束。
：首先建立一个栈，定义一个常量flag（flag为0或1），用flag统计结点左子是否去过，没有去过为0，去过为1，，将根结点入栈，然后将指针指向左子，左子作为新结点，将新结点入栈，然后再将指针指向目前结点左子，直至左子为空，则指针返回，flag置1，出栈一个元素，作为目前结点，打印该结点，然后判定flag，flag为1则将指针指向目前结点右子，将右子作为新结点，结点入栈，再次进行上面判定，直至目前
结点右子也为空，则再出栈一个元素作为目前结点，一直到结束，使得目前结点右子为空，且栈空，遍历结束。
：首先建立两个栈，然后定义两个常量。第一个为status，取值为0，1，，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，若没有右子，则打印目前结点，并将指针置空，然后再次判定flag。若目前结点status为2，且栈为空，则遍历结束。若指针指向了左子，则将左子作为目前结点，判定其左右子情况，按上述方法处理，直至遍历结束。
二、算法步骤图
图1 二叉树建立
用先序方法建立二叉树，为每个结点定义左右子，用0代表空，得到上述二叉树
图2 非递归二叉树遍历 先序
首先建立一个栈，当指针抵达根结点时，打印根结点，判定根结点是否有左子和右子。有左子和右子话就打印左子同时将右子入栈，将左子作为新根结