文档介绍：一、设计思想1. 用递归算法遍历 设计思想:主要是通过不同程序顺序,从而实现递归的顺序遍历 前序遍历:先判断节点是否为空,如果不为空,则输出。再判断左节点是否为空,如果不为空,则递归调用,直到遍历到最左边。接着再遍历最左边的右子树,如果此时右子树不为空,则递归遍历左子树的操作,直到遍历到叶子节点。如果右子树为空,则回溯上次的递归调用,重复输出和遍历右子树的操作。 中序遍历: 先遍历左节点是否为空,如果不为空,则递归调用,直到遍历到最左边或者叶子节点,然后输出,接着再遍历最左边的右子树,如果此时右子树不为空,则递归重复遍历左子树的操作,直到遍历到叶子节点。如果右子树为空,则回溯到上次递归调用,重复输出和遍历右子树的操作。 后序遍历:先判断左节点是否为空,如果不为空则一直递归直到遍历到最左边,然后遍历右节点,再接着遍历到左子树的最右边,直到遍历到叶子节点。此时输出,回溯到上次递归,继续执行后面的操作,重复,直到将整个树遍历完毕。 2. 用非递归算法遍历 设计思想:主要是通过栈的存取,判空,从而实现树的遍历 前序遍历:通过一个循环实现。先输出节点的数值,因为栈的特性,则需要先判断右子树是否为空,如果不为空,则将右子树压栈。然后判断左子树是否为空,如果不为空,则将左子树压栈。接着再将栈里面的子树弹出赋给给当前节点变量,重复上述操作,直到栈为空后退出循环。 中序遍历:通过循环实现。将树一直遍历到最左端,并将中间所经过的节点保存在栈中,当遍历到最左边的时候,则弹出栈里面的子树。输出数值,将当前节点赋值为当前节点的右子树,遍历右子树,即重复上述操作,直到当前节点为空,并且栈内元素为0。 后序遍历:通过循环和标记栈实现。将数一直遍历到最左端,并将中间的节点保存在树栈中,同时同步的添加一个标记栈。当遍历到最左边的时候,弹栈并赋值给当前栈,然后判断标记栈的数值,如果数值为0的话则代表当前树没有遍历过,遍历右子树。然后重复上面的操作,如果数值为1的话则代表此时数已经遍历过了,可以开始输出了,为了避免重复输出,将当前栈赋为空。重复循环操作,直到栈内没有元素,且当前节点为空(因为一直左的操作并没有将右子树压栈)。二、算法流程图图1递归算法-先序遍历     图2递归算法-后序遍历    图3递归算法-中序遍历图4非递归算法-先序遍历              图5非递归算法-中序遍历图6非递归算法-后序遍历三、源代码#include<> #include<> typedefcharElemType; //定义树结构 typedefstructtree { ElemTypedata; structtree*lchild; structtree*rchild; unsignedintisOut; //专为后序遍历设置的,0为不需要被输出,1为需要被输出 }TreeNode,*Tree; //定义栈结构 typedefstructstack { Tree*base; Tree*top; intstacksize; }SqStack; voidInitStack(SqStack&s); voidPush(SqStack&s,Treee); voidGetTop(SqStacks,Tree&e); voidPop(SqStack&s,Tree&e); intStackEmpty(SqStacks);  voidCreateTree(Tree&t); voidPreOrder(Treet); voidPreOrder1(Treet); voidInOrder(Treet); voidInOrder1(Treet); voidPostOrder(Treet); voidPostOrder1(Treet); intmain() { TreeT; printf("\n按先序序列输入结点序列,'*'代表空:"); CreateTree(T); printf("\n递归先序遍历的结果:"); PreOrder(T);printf("\n非递归先序遍历的结果:"); PreOrder1(T); printf("\n递归中序遍历的结果:"); InOrder(T); printf("\n非递归中序遍历的结果:"); InOrder1(T); printf("\n递归后序遍历的结果:"); PostOrder(T);printf("\n非递归后序遍历的结果:"); PostOrder1(T);  printf("\n"); return0;} voidInitStack(SqStack&s) //初始化栈{ =(Tree*)malloc(100*sizeof(Tree)); if(!) { printf("InitStack内