用递归非递归两种方法遍历二叉树

1、用递归、非递归两种方法遍历二叉树数据结构（双语）项目文档报告用递归、非递归两种方法遍历二叉树专 业：计算机科学与技术班 级：指导教师：姓 名：学 号：目 录一、设计思想.03二、算法流程图.04三、源代码.06四、运行结果.12五、遇到的问题及解决.14六、心得体会.15-14 -一、设计思想1 .递归：(1)主函数main ()主程序要包括：定义的二叉树 T、建树函数、先序遍 历函数、中序遍历函数、后序遍历函数。(2)建树函数定义一个输入的数是字符型的，当 ch为空时，T就为空值， 否则的话就分配空间给T, T就指向它的结点，然后左指针域指向左孩子，右指 针指向右孩子，若还有，继续调用，依次

2、循环下去，直到ch遇到空时，结束。最 后要返回建立的二叉树To(3)先序遍历函数根据先序遍历规则，当 T为非空时，先输出结点处的数 据，指针指向左、右孩子，依次进行下去。(4)中序遍历函数根据中序遍历规则，当T为非空时，先左指针指向左孩子 数据，然后输出结点处的数据，再右指针指向右孩子，依次进行下去。(5)后序遍历函数根据后序遍历规则，当T为非空时，先右指针指向右孩子， 然后左指针指向左孩子，最后输出结点处的数据，依次进行下去。2 .非递归：(1)跟递归遍历二叉树的前提一样，首先应该创建一个二叉树，同样使用 先序递归的方式创建二叉树。(2)然后是中序，先序，后序非递归遍历二叉树。(3)中序非递

3、归遍历二叉树的思想是： 首先是根节点压栈，当根节点的左 子树不是空的时候，左子树压栈。直到左子树为空的时候，不再压栈。将栈顶元 素出栈，访问栈顶元素，并将栈顶的右子树进栈。当右子树的左子树不是空的时 候，左子树一直进栈，直到左子树为空，则不再进栈。重复上面的操作，直到栈 空的时候。(4)先序非递归遍历二叉树的思想是：首先是根节点进栈，然后当栈不为空 的时候，将栈顶元素出栈，然后访问。同时将出栈元素的右子树进栈，左子树进 栈。重复上面的操作，直到栈为空。(5)后序非递归遍历二叉树的思想：首先是根节点进栈，当根节点的左子 树不为空的时候，左子树进栈，直到左为空的时候，左子树不再进栈。指针指向 的是

4、右子树，当右子树为空的时候，直接访问根节点。当右子树不为空的时候， 则右子树的指针进栈，当右子树的左子树不为空的时候， 则左也进栈，直到左为 空。重复上面的操作，直到栈为空的时候，则遍历树完成。二、算法流程图1.递归蚣子附右予鞘就颤2.非递归企口两个T，ft花“a.指 白身两方点的悔排玲根疗息入枝，|将口布芍5l牛附中 禀元*并骅0|中 的垠节点出枝.压 人到板*'f| X山率 L. K L 二川山>naht空？王人心I；iHli'H." i.EfjV.档口的兀巢他 次山栈三、源代码1 .递归#include "stdio.h"#includ

5、e "conio.h"#include <stdlib.h>#include<stack>typedef struct nodechar data;struct node *lchild, *rchild;BinTnode;typedef BinTnode * BinTree; 定义二叉树类型的指针/*先序创建二叉树*/int CreateBinTree(BinTree *T)char ch;*T=(BinTree)malloc(sizeof(BinTnode);if(!*T) printf("overflow");doch=ge

6、tchar();if(ch='') *T=NULL;return 0;else(*T)->data=ch;CreateBinTree(&(*T)->lchild);CreateBinTree(&(*T)->rchild);return 1;while(ch!='0');/*中序递归遍历*/void InorderTransverse(BinTree s)ifInorderTransverse(s->lchild);printf("%c", s->data);InorderTransverse(s-

7、>rchild);/先序递归遍历二叉树void PreOrderTranverseTree(BinTree s) if printf("%c", s->data);PreOrderTranverseTree(s->lchild); PreOrderTranverseTree(s->rchild); /后序递归遍历二叉树 void PostOrderTranverseTree(BinTree s) if PreOrderTranverseTree(s->lchild);PreOrderTranverseTree(s->rchild); pr

8、intf("%c", s->data);/*主方法*/void main()BinTree T;printf(" 请按照先序的顺序输入要创建的树 ：n"); CreateBinTree(&T); /* 中序序列创建二叉树 */ printf("中序递归遍历的序列是：")；InorderTransverse(T);printf("n");/先序递归遍历printf("先序递归遍历的序列是：")；PreOrderTranverseTree(T); printf("n"

9、;);/后序递归遍历printf("后序递归遍历的序列是：")；PostOrderTranverseTree(T); printf("n");2 .非递归#include "stdio.h"#include "conio.h"#include <stack>#include <stdlib.h>typedef struct nodechar data;struct node *lchild, *rchild;BinTnode;typedef BinTnode * BinTree; 定义二叉树

10、类型的指针typedef structBinTree data100;int top;SeqStack;void initStack(SeqStack *S)S->top =-1;void Push(SeqStack *S,BinTree x)if(S->top=100-1)printf("the stack is overflow");else S->top=S->top+1;S->dataS->top=x;int Pop(SeqStack *S,BinTree *p)if(S->top=-1)printf("the s

11、tack is underflow");return 0;else *p=S->dataS->top;-S->top;return 1;int EmptyStack(SeqStack S)if(S.top=-1) return 1;else return 0; /*栈不空的情况*/int GetTop(SeqStack S,BinTree *p)if(S.top=-1)printf("the stack is empty");return 0;else *p=S.dataS.top;return 1;char visit(BinTree p)re

12、turn (*p).data;/*创建二叉树*/int CreateBinTree(BinTree *T)char ch;*T=(BinTree)malloc(sizeof(BinTnode);if(!*T) printf("overflow");else do ch=getchar(); if(ch!='') q=NULL; return 0; else (*T)->data=ch;CreateBinTree(&(*T)->lchild);CreateBinTree(&(*T)->rchild);return 1;whil

13、e(ch!='0');/*中序非递归遍历*/void InorderTransverse(BinTree T)SeqStack S;BinTree p;initStack(&S);/初始化栈printf("中序非递归序列是：")；Push(&S,T); /根指针进栈T为指向二叉树的指针while(!EmptyStack(S) / 栈不是空的情况while(GetTop(S,&p) && p)Push(&S,p->lchild); /gettop得到的结果也必须是一棵子树才行，进栈应该进的是树根的指针Pop

14、(&S,&p);if(!EmptyStack(S)printf("%c",visit(p);Pop(&S,&p);printf("%c",visit(p);Push(&S,p->rchild); /*先序非递归遍历*/ void PreorderTransverse(BinTree T)SeqStack S;BinTree p;initStack(&S);/ 初始化栈Push(&S,T); /根指针进栈Tprintf("先序非递归序列是：")；while(!EmptySta

15、ck(S)Pop(&S,&p);/if(p!=NULL) printf("%c",visit(p); Push(&S,p->rchild); Push(&S,p->lchild); /*后序非递归遍历*/ void PostorderTransverse(BinTree T)SeqStack S;BinTree p,q;initStack(&S);/ 初始化栈p=T;printf("后序非递归序列是：")；while(p |!EmptyStack(S) / 为空了if(p!=q)while(p!=NUL

16、L)为指向二叉树的指针根节点出栈跳出while循环的原因是因为左子树或者右子树Push(&S,p);if(p->lchild!=NULL)p=p->lchild;elsep=p->rchild;if(EmptyStack(S) break;GetTop(S,&q);if(q->rchild=p)/进栈的是右子树Pop(&S,&p);printf("%c",visit(p);p=q;elsep=q->rchild;/*主方法*/void main()BinTree T;printf("请按照先序的顺序输入

17、创建的树：n");/*创建树*/CreateBinTree(&T);/中序非递归遍历InorderTransverse(T);printf("n");/先序非递归遍历PreorderTransverse(T);printf("n");/后序非递归遍历PostorderTransverse(T);四、运行结果1 .递归输入*氏 bugVU请柠照斗.序以加字知51!建的即1 2 3 4 5 & 7:文- M拼音输入法全：结果* * E:S2De bu g4.exe'口 回 SS2.非递归输入青按照先序的H同序输入要创建的树;12 3 4s 6 7口又QQ拼舌输入法全：结果ti 皿 7历历历y 5归归归y 4修弦逆arl 一二 i 二二 3 -二二二二 S五、遇到的问题及解决经过一个星期的写代码，我遇到了很多问题，并一一解决了，比如：1 .创建二叉树时：void createBiTree(BiTNode *T) 和 void createBiTree(BiTNode *&T) 没分清楚区别。后来查找资料找到 void createBiTree(BiTNode *T)是将结点的指针(地址)传递到函数中进行处理void createBiTree(BiT