《用递归非递归两种方法遍历二叉树.doc》由会员分享，可在线阅读，更多相关《用递归非递归两种方法遍历二叉树.doc（16页珍藏版）》请在三一文库上搜索。
1、数据结构（双语）项目文档报告用递归、非递归两种方法遍历二叉树专 业： 计算机科学与技术班 级：指导教师：姓 名：号:一、设计思想 .03二、算法流程图 .04三、源代码 .06四、运行结果 .12五、遇到的问题及解决 .14六、心得体会 .15一、设计思想1 递归：(1) 主函数main ()主程序要包括：定义的二叉树 T、建树函数、先序遍 历函数、中序遍历函数、后序遍历函数。(2) 建树函数定义一个输入的数是字符型的，当 ch为空时，T就为空值， 否则的话就分配空间给T，T就指向它的结点，然后左指针域指向左孩子，右指 针指向右孩子，若还有，继续调用，依次循环下去，直到ch遇到空时，结束。最
2、后要返回建立的二叉树To(3) 先序遍历函数根据先序遍历规则，当 T为非空时，先输出结点处的数 据，指针指向左、右孩子，依次进行下去。(4) 中序遍历函数根据中序遍历规则，当T为非空时，先左指针指向左孩子 数据，然后输出结点处的数据，再右指针指向右孩子，依次进行下去。(5 )后序遍历函数根据后序遍历规则，当T为非空时，先右指针指向右孩子， 然后左指针指向左孩子，最后输出结点处的数据，依次进行下去。2.非递归：(1) 跟递归遍历二叉树的前提一样，首先应该创建一个二叉树，同样使用 先序递归的方式创建二叉树。(2) 然后是中序，先序，后序非递归遍历二叉树。(3) 中序非递归遍历二叉树的思想是： 首先
3、是根节点压栈，当根节点的左 子树不是空的时候，左子树压栈。直到左子树为空的时候，不再压栈。将栈顶元素出栈，访问栈顶元素，并将栈顶的右子树进栈。当右子树的左子树不是空的时 候，左子树一直进栈，直到左子树为空，则不再进栈。重复上面的操作，直到栈 空的时候。(4) 先序非递归遍历二叉树的思想是：首先是根节点进栈，然后当栈不为空 的时候，将栈顶元素出栈，然后访问。同时将出栈元素的右子树进栈，左子树进栈。重复上面的操作，直到栈为空。(5 )后序非递归遍历二叉树的思想：首先是根节点进栈，当根节点的左子 树不为空的时候，左子树进栈，直到左为空的时候，左子树不再进栈。指针指向 的是右子树，当右子树为空的时候，
4、直接访问根节点。当右子树不为空的时候， 则右子树的指针进栈，当右子树的左子树不为空的时候， 则左也进栈，直到左为 空。重复上面的操作，直到栈为空的时候，则遍历树完成。二、算法流程图1.递归2.非递归iE AV ：；征山：二殆彗3H5止俯桶*山屋机苛严人*Ji将P指旬外中的找#14, 的*H节点出按.JE 人別总艸SAffishI. I ;打同屮低顶诒TJ三、源代码1.递归#i nclude stdio.h#i nclude con io.h#i nclude #in cludetypedef struct no dechar data;struct node *lchild, *rchild;
5、Bi nTn ode;typedef BinTn ode * Bin Tree; /定义二叉树类型的指针/*先序创建二叉树*/int CreateB in Tree(Bi nTree *T)char ch;*T=(Bi nTree)malloc(sizeof(Bi nTno de);if(!*T) pri ntf(overflow);doch=getchar();if(ch=) *T=NULL;return 0;else(*T)-data=ch;CreateBi nTree(&(*T)-lchild);CreateBi nTree(&(*T)-rchild);return 1;while(ch
6、!=0);/*中序递归遍历*/void InorderTransverse(BinTree s)if (s)In orderTra nsverse(s-lchild);printf(%c, s-data);In orderTra nsverse(s-rchild);/先序递归遍历二叉树void PreOrderTra nverseTree(B in Tree s)if (s)prin tf(%c, s-data);PreOrderTra nverseTree(s-lchild);PreOrderTra nverseTree(s-rchild);/后序递归遍历二叉树void PostOrderT
7、ra nverseTree(B in Tree s)if (s)PreOrderTra nverseTree(s-lchild);PreOrderTra nverseTree(s-rchild); prin tf(%c, s-data);/*主方法*/void mai n()Bin Tree T;printf(”请按照先序的顺序输入要创建的树:n);CreateBi nTree( &T); /*中序序列创建二叉树 */printf(”中序递归遍历的序列是:);In orderTra nsverse(T);prin tf(n);/先序递归遍历printf(先序递归遍历的序列是：”)；PreOrd
8、erTra nverseTree(T);prin tf(n);/后序递归遍历printf(”后序递归遍历的序列是：”)；PostOrderTra nverseTree(T);prin tf(n);2.非递归#i nclude stdio.h#i nclude con io.h#in elude #i nclude typedef struct no dechar data;struct node p=S-dataS-top; -S-top;return 1;lchild, *rchild;定义二叉树类型的指针Bi nTn ode;typedef BinTnode * Bin Tree; / t
9、ypedef structBinTree data100;int top;SeqStack;void in itStack(SeqStack *S)S-top =-1;void Push(SeqStack *S,B in Tree x)if(S-top=100-1)prin tf(the stack is overflow);else S-top=S-top+1;S-dataS-top=x;int Pop(SeqStack *S,B in Tree *p) if(S-top=-1)prin tf(the stack is un derflow); return 0;else int Empty
10、Stack(SeqStack S)if(S.top=-1) return 1;else return 0; /*栈不空的情况*/int GetTop(SeqStack S,Bi nTree *p)if(S.top=-1)prin tf(the stack is empty);return 0;else *p=S.dataS.top;return 1;char visit(Bi nTree p)return (*p).data;/*创建二叉树*/int CreateB in Tree(Bi nTree *T)char ch;*T=(Bi nTree)malloc(sizeof(Bi nTno d
11、e); if(!*T) pri ntf(overflow);elsedoch=getchar();if(ch!=)*T=NULL;return 0;else(*T)-data=ch;CreateBi nTree(&(*T)-lchild); CreateBi nTree(&(*T)-rchild); return 1;while(ch!=0);/*中序非递归遍历*/void InorderTransverse(BinTree T)SeqStack S;Bi nTree p;in itStack(&S);初始化栈prin tf(中序非递归序列是:);Push(&S,T); /根指针进栈T为指向二
12、叉树的指针while(!EmptyStack(S) /栈不是空的情况while(GetTop(S,&p) & p)Push(&S,p-lchild); /gettop得到的结果也必须是一棵子树才行，进栈应该进的是树根的指针Pop(&S,&p);if(!EmptyStack(S)/prin tf(%c,visit(p);Pop(&S,&p);prin tf(%c,visit(p); Push(&S,p-rchild);/*先序非递归遍历*/void PreorderTra nsverse(Bi nTree T)SeqStack S;Bi nTree p;in itStack(&S);初始化栈Pu
13、sh(&S,T); /根指针进栈Tprin tf(先序非递归序列是：”)；while(!EmptyStack(S)Pop(&S,&p);/if(p!=NULL) prin tf(%c,visit(p); Push(&S,p-rchild); Push(&S,p-lchild);/*后序非递归遍历*/void PostorderTra nsverse(Bi nTree T) SeqStack S;Bi nTree p,q;in itStack(&S);初始化栈p=T;prin tf(后序非递归序列是：”)；while(p |!EmptyStack(S) / 为空了if(p!=q)while(p!
14、=NULL)为指向二叉树的指针根节点出栈跳出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);prin tf(%c,visit(p);p=q;elsep=q-rchild;/*主方法*/void mai n()Bin Tree T;printf(”请按照先序的顺序输入创建的树:n);/*创建树*/CreateBi nTree( &T);/中序非递归遍历I
15、n orderTra nsverse(T);prin tf(n);/先序非递归遍历PreorderTra nsverse(T);prin tf(n);/后序非递归遍历PostorderTra nsverse(T);四、运行结果1.递归输入结果2.非递归输入结果白raJ -ji 一 .JI Q- 二 -i 一二123123屈ue 曰.畫tin onS4Co B日B t 斤-wske五、遇到的问题及解决经过一个星期的写代码，我遇到了很多问题，并一一解决了，比如：1.创建二叉树时：void createBiTree(BiTNode *T)和 void createBiTree(BiTNode *&T
16、) 没分清楚区别。后来查找资料找到 void createBiTree(BiTNode *T)是将结点的指针(地址)传递到函数中进行处理void createBiTree(BiTNode *&T是将结点指针的引用传递到函数处理。才理解清楚。2.在写非递归算法时，一直逻辑混乱，后来查找了资料后，又自己缕了一遍，才得到 解决。尤其是后序遍历时。六、心得体会在做完本项目之后，体会最深的就是应该细心， 并且很多时候我们看见某些事情很简单 就不想去做，而做的时候又总会遗漏很多需要考虑的细节，或者根本就不知道从哪入手更好，在做这个项目时，错过很多次，很多时候有一种成功离自己很近很近，似乎可以看到，但就是无法接触到的感觉，我想，在以后的学习中，应该把一些必要的程序都敲一遍，而不要直接说句，简单，然后不屑去做，这样，其实最终很难真正学到什么！