文档介绍：用递归、非递归两种方法遍历二叉树一、设计思想二叉树的遍历分为三种方式,分别是先序遍历,中序遍历和后序遍历。先序遍历实现的顺序是:根左右,中序遍历实现的是:左根右,后续遍历实现的是:左右根。根据不同的算法分,又分为递归遍历和非递归遍历。递归算法::先序遍历就是首先判断根结点是否为空,为空则停止遍历,不为空则将左子作为新的根结点重新进行上述判断,左子遍历结束后,再将右子作为根结点判断,直至结束。到达每一个结点时,打印该结点数据,即得先序遍历结果。:中序遍历是首先判断该结点是否为空,为空则结束,不为空则将左子作为根结点再进行判断,打印左子,然后打印二叉树的根结点,最后再将右子作为参数进行判断,打印右子,直至结束。:指针到达一个结点时,判断该结点是否为空,为空则停止遍历,不为空则将左子作为新的结点参数进行判断,打印左子。左子判断完成后,将右子作为结点参数传入判断,打印右子。左右子判断完成后打印根结点。非递归算法::首先建立一个栈,当指针到达根结点时,打印根结点,判断根结点是否有左子和右子。有左子和右子的话就打印左子同时将右子入栈,将左子作为新的根结点进行判断,方法同上。若当前结点没有左子,则直接将右子打印,同时将右子作为新的根结点判断。若当前结点没有右子,则打印左子,同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子,则当前结点为叶子结点,此时将从栈中出栈一个元素,作为当前的根结点,打印结点元素,同时将当前结点同样按上述方法判断,依次进行。直至当前结点的左右子都为空,且栈为空时,遍历结束。:首先建立一个栈,首先将指针指向根结点,将根结点入栈,然后将指针指向左子,左子作为新的结点,将新结点入栈,然后再将指针指向当前结点的左子,直至左子为空,则指针返回,出栈一个元素,作为当前结点,打印该结点,然后将指针指向当前结点右子,将右子作为新的结点,结点入栈,再次进行上面的判断,直至当前结点右子也为空,则再出栈一个元素作为当前结点,一直到结束,使得当前结点右子为空,且栈空,遍历结束。:首先从根节点开始遍历,看根节点是否为空,如果根节点不为空,将根节点的元素压入栈中,继续遍历,如果根节点有左子,索引移动到左子,并以左子为根节点继续遍历。如果左子不为空,则索引移动到左子并入栈;如果左子为空,索引移动到栈顶元素所在的节点,如果此节点的右子不为空并且右子没有被访问过,则索引移动到右子,否则访问栈顶元素并输出,并且定义此节点为被访问过得节点,栈顶元素出栈,树节点定义为NULL,继续遍历。二、算法流程图递归算法:-1-用递归、非递归两种方法遍历二叉树创建二叉树调用自身调用对应函数输出结果图1递归算法流程图先序非递归遍历得到根节点输出当前节点当前节点的元判断当前节存是否存在左入栈,当前节移动到左子上不存存在当前节点跳当前节点到右子上是否存在右子不存在当前节出栈,为空不为空栈是否为空结束点为出栈元素2图先序遍历的非递归算法流程图-2-用递归、非递归两种方法遍历二叉树中序非递归遍历:得到根节判断当前节存当前节点的元是否存在左入栈,当前节点移动到左子不存输出当前节当前节点存判断当前节点到右子是否存在右子不存出栈当前不为为栈是否为点为出栈元结素图3中序遍历的非递归算法流程图-3-用递归、非递归两种方法遍历二叉树后序非递归遍历:得到根节点当前节点的元判断当前节存入栈,当前节是否存在左子移动到左子不存存当前节点判断当前节到右子是否存在右子不存输出当前节出栈当前节不为为栈是否为点为出栈结素后序遍历的非递归算法流程图4图-4-用递归、非递归两种方法遍历二叉树三、源代码前序非递归#include<>structelement//用结构体构建二叉树元素{structelement*lchild;intdata;structelement*rchild;};intmain(){inti=1;structelement*stack[30];structelementa,b,c,d,e;//=1;=2;=3;=4;=5;=&b;=&c;=&d;=&e;=0;=0;=0;=0;=0;=0;stack[i]=&a;while(i!=0)//用数组逐个处理二叉树的元素{while(stack[i]!=0)//取左子树直至为空{printf(%d\n,(*(stack[i])).data);//访问元素的数据部分i++;stack[i]=(*(stack[i-1])).lch