《二叉树遍历C语言(递归-非递归)六种算法》由会员分享，可在线阅读，更多相关《二叉树遍历C语言(递归-非递归)六种算法（14页珍藏版）》请在金锄头文库上搜索。
1、HEBEI UNITED UMVERSITY数据结构（双语）项目文档报告用两种方式实现表达式自动计算专 业：班 级：指导教师：姓 名：学 号：目 录一、设计思想.01二、算法流程图.02三、源代码.04四、运行结果.11五、遇到的问题及解决.11六、心得体会 .12一、设计思想二叉树的遍历分为三种方式，分别是先序遍历，中序遍历和后序遍历。 先序遍历实现的顺序是：根左右，中序遍历实现的是：左根右，后续遍历实现的是：左右根。根据不同的算 法分，又分为递归遍历和非递归遍历。递归算法：1 .先序遍历：先序遍历就是首先判断根结点是否为空，为空则停止遍历，不为空则将 左子作为新的根结点重新进行上述判断，左
2、子遍历结束后，再将右子作为根结点判断， 直至结束。到达每一个结点时，打印该结点数据，即得先序遍历结果。2 .中序遍历：中序遍历是首先判断该结点是否为空，为空则结束，不为空则将左子作为 根结点再进行判断，打印左子，然后打印二叉树的根结点，最后再将右子作为参数进行判断， 打印右子，直至结束。3 .后续遍历：指针到达一个结点时，判断该结点是否为空，为空则停止遍历，不为空则 将左子作为新的结点参数进行判断，打印左子。左子判断完成后，将右子作为结点参数传入判断，打印右子。左右子判断完成后打印根结点。非递归算法：1 .先序遍历：首先建立一个栈，当指针到达根结点时，打印根结点，判断根结点是否有 左子和右子。
3、有左子和右子的话就打印左子同时将右子入栈，将左子作为新的根结点进行判断，方法同上。若当前结点没有左子， 则直接将右子打印，同时将右子作为新的根结点判断。 若当前结点没有右子，则打印左子，同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子，则当前结点为叶子结点，此时将从栈中出栈一个元素，作为当前的根结点， 打印结点元素，同时将当前结点同样按上述方法判断，依次进行。直至当前结点的左右子都为空，且栈为空时，遍历结束。2 .中序遍历：首先建立一个栈，定义一个常量 flag （flag为。或者1）,用flag记录结点 的左子是否去过，没有去过为0,去过为1,默认为0.首先将指针指向根结点，将根
4、结点入栈，然后将指针指向左子，左子作为新的结点，将新结点入栈，然后再将指针指向当前结点 的左子，直至左子为空，则指针返回，flag置1,出栈一个元素，作为当前结点，打印该结点，然后判断flag, flag为1则将指针指向当前结点右子，将右子作为新的结点， 结点入栈，再次进行上面的判断，直至当前结点右子也为空，则再出栈一个元素作为当前结点，一直到结束，使得当前结点右子为空，且栈空，遍历结束。3 .后续遍历：首先建立两个栈，然后定义两个常量。第一个为status,取彳1为0, 1, 2.0代表左右子都没有去过，1代表去过左子，2,代表左右子都去过，默认为 0。第二个常量为 flag,取值为0或者1
5、, 0代表进左栈，1代表进右栈。初始时指针指向根结点，判断根结点 是否有左子，有左子则，将根结点入左栈，status置0, flag置0,若没有左子则判断结点有没有右子，有右子就把结点入右栈，status置0, flag置1,若左右子都没有，则打印该结点， 并将指针指向空，此时判断 flag ,若flag为0,则从左栈出栈一个元素作为当前结点，重新 判断；若flag为1则从右栈出栈一个元素作为当前结点，重新判断左右子是否去过， 若status为1,则判断该结点有没有右子，若有右子，则将该结点入右栈，status置1, flag置1,若没有右子，则打印当前结点，并将指针置空，然后再次判断flag
6、。若当前结点status为2,且栈为空，则遍历结束。若指针指向了左子，则将左子作为当前结点，判断其左右子情况， 按上述方法处理，直至遍历结束。二、算法流程图图1二叉树的建立用先序方法建立二叉树，为每个结点定义左右子，用0代表空，得到上述二叉树图2非递归二叉树遍历先序首先建立一个栈，当指针到达根结点时，打印根结点，判断根结点是否有左子和右子。有左子和右子的话就打印左子同时将右子入栈，将左子作为新的根结点进行判断， 方法同上。若当前结点没有左子， 则直接将右子打印，同时将右子作为新的根结点判断。若当前结点没有右子，则打印左子，同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子， 则当前结
7、点为叶子结点，此时将从栈中出栈一个元素，作为当前的根结点，打印结点元素，同时将当前结点同样按上述方法判断，依次进行。直至当前结点的左右子都为空，且栈为空时，遍历结束。二.二冬克当的巧产台工培丰有可椽落土无益占 才的豆加rue打和当E幽点、送f叁点 苑W装酎耄史的志于.flag 为 fei图3非递归二叉树遍历中序中序遍历：首先建立一个栈，定义一个常量flag （flag为。或者1）,用flag记录结点的左子是否去过，没有去过为0,去过为1,默认为0.首先将指针指向根结点，将根结点入栈，然后将指针指向左子，左子作为新的结点，将新结点入栈，然后再将指针指向当前结点的左子，直至左子为空，则指针返回，
8、flag置1,出栈一个元素，作为当前结点，打印该结点， 然后判断flag, flag为1则将指针指向当前结点右子，将右子作为新的结点，结点入栈，再 次进行上面的判断， 直至当前结点右子也为空，则再出栈一个元素作为当前结点，一直到结度我白刘、而左 营 到点让 啤培岩当南辅导3向做共弹出的拈百，staiua当前结古相向右啕世姆后点，etalui寿？当市缩占搐三黄法仲W娜多加闻f为i1 no注隶“ 埼为主二前转点也右 推，当曲五担 向其百子“112 5fctJ3t-0甲导当曲占束，使得当前结点右子为空，且栈空，遍历结束。图4非递归二叉树遍历后序首先建立两个栈，然后定义两个常量。第一个为status,
9、取彳1为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,则判 断该结点有
10、没有右子，若有右子，则将该结点入右栈，status置1, flag置1,若没有右子，则打印当前结点，并将指针置空，然后再次判断flag。若当前结点status为2,且栈为空，则遍历结束。若指针指向了左子，则将左子作为当前结点，判断其左右子情况，按上述方法 处理，直至遍历结束。三、源代码卜面给出的是用递归算法实现的程序的源代码:#include#include用递归的方式遍历二叉树typedef struct node int data;struct node*lChild,*rChild;Node;int i=-1;Node *buildTree(int *b)Node *p;if(b+i=0
11、)p=NULL;else p=(Node*)malloc(sizeof(Node);p-data=bi;p-lChild=buildTree(b);p-rChild=buildTree(b);return p;定义二叉树的结点结点的数据结点左右子控制下面函数中循环的产生二叉树（利用先序递归产生）创建一个根结点指针如果传入的当前值为 0则设其为空结点开辟内存设置当前结点的数据左子结点右子把创建的树的根节点返回前序遍历void preOrder(Node *root) if(root!=0)printf(%d ,root-data); preOrder(root-lChild); preOrder
12、(root-rChild);void inOrder(Node *root)if(root!=0)inOrder(root-lChild);printf(%d ,root-data); inOrder(root-rChild);void postOrder(Node *root)if(root!=0)postOrder(root-lChild);postOrder(root-rChild); printf(%d ,root-data);如果根节点不为0打印当前结点指向左子指向右子中序遍历如果根节点不为0指向左子打印当前结点指向右子指向左子指向右子打印当前结点void main()按先序次序输入
13、树的结点(非0整数)来创建一个树空结点用int a口 = 1,2,4,0,7,0,0,0,3,5,0,0,6,8,0,0,9,0,0;int *b = a;0表不将指向数组首地址的指针传给Node *root = buildTree(b);bulidTree函数来创建树printf(用递归方法nn前序遍历：); preOrder(root);printf(n 中序遍历：)；inOrder(root);printf(n 后序遍历:);postOrder(root);getch()；打印提示内容调用前序遍历函数打印提示内容调用中序遍历函数打印提示内容调用后序遍历函数定义二叉树的结点结点的数据结点左
14、右子创建栈栈底指针栈顶指针初始化栈为指针开辟内存栈顶指针指向栈底指针判断栈是否为空的函数栈空返回1/不为空返回 0栈的push方法给栈顶赋值然后top+1出栈函数/声明一 Node类型遍量/node为栈顶元素然后top-1返回pop出的结点看栈顶元素返回栈顶元素创建栈（MyStack）结构体栈底指针栈顶指针下面给出的是用非递归算法实现的程序的源代码：#include#include用非递归的方式遍历二叉树typedef struct node int data;struct node *lChild,*rChild;Node;typedef struct Node *bottom;Node *top;Stack;void init(Stack *s) s-bottom=(Node *)
