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

《用递归非递归两种方法遍历二叉树.pdf》由会员分享，可在线阅读，更多相关《用递归非递归两种方法遍历二叉树.pdf（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、.-数据构造双语数据构造双语工程文档报告工程文档报告用递归、非递归两种方法遍历二叉树用递归、非递归两种方法遍历二叉树专专业：业：计算机科学与技术计算机科学与技术班班级：级：指导教师：指导教师：-.word.zl.-姓姓名：名：学学号：号：目目录录一、设计思想.03二、算法流程图.04三、源代码.06四、运行结果.12五、遇到的问题及解决.14六、心得体会.15-.word.zl.-一、设计思想一、设计思想1递归：1主函数 main主程序要包括：定义的二叉树 T、建树函数、先序遍历函数、中序遍历函数、后序遍历函数。2建树函数定义一个输入的数是字符型的，当 ch 为空时，T 就为空值，否那么的话就

2、分配空间给 T，T 就指向它的结点，然后左指针域指向左孩子，右指针指向右孩子，假设还有，继续调用,依次循环下去，直到 ch 遇到空时，完毕。最后要返回建立的二叉树 T。3先序遍历函数根据先序遍历规那么，当 T 为非空时，先输出结点处的数据，指针指向左、右孩子，依次进展下去。(4) 中序遍历函数根据中序遍历规那么，当 T 为非空时，先左指针指向左孩子数据，然后输出结点处的数据，再右指针指向右孩子，依次进展下去。(5后序遍历函数根据后序遍历规那么，当T 为非空时，先右指针指向右孩子，然后左指针指向左孩子，最后输出结点处的数据，依次进展下去。2.非递归：1跟递归遍历二叉树的前提一样，首先应该创立一个

3、二叉树， 同样使用先序递归的方式创立二叉树。-.word.zl.-2然后是中序，先序，后序非递归遍历二叉树。3中序非递归遍历二叉树的思想是：首先是根节点压栈，当根节点的左子树不是空的时候，左子树压栈。直到左子树为空的时候，不再压栈。将栈顶元素出栈，访问栈顶元素，并将栈顶的右子树进栈。当右子树的左子树不是空的时候，左子树一直进栈，直到左子树为空，那么不再进栈。重复上面的操作，直到栈空的时候。(4)先序非递归遍历二叉树的思想是：首先是根节点进栈，然后当栈不为空的时候，将栈顶元素出栈，然后访问。同时将出栈元素的右子树进栈，左子树进栈。重复上面的操作，直到栈为空。(5后序非递归遍历二叉树的思想：首先是

4、根节点进栈，当根节点的左子树不为空的时候，左子树进栈，直到左为空的时候，左子树不再进栈。指针指向的是右子树，当右子树为空的时候，直接访问根节点。当右子树不为空的时候，那么右子树的指针进栈，当右子树的左子树不为空的时候，那么左也进栈，直到左为空。重复上面的操作，直到栈为空的时候，那么遍历树完成。二、算法流程图二、算法流程图1. 1.递归递归-.word.zl.-2. 2.非递归非递归-.word.zl.-三、源代码三、源代码1. 1.递归递归-.word.zl.-#include stdio.h#include conio.h#include #includetypedef struct nod

5、echar 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=getchar();if(ch= )*T=NULL;return 0;else(*T)-data=ch;CreateBinTree(&(*T)-lchild);CreateBinTree(&(*T)

6、-rchild);return 1;while(ch!=0);/*中序递归遍历*/void InorderTransverse(BinTree s)if (s)InorderTransverse(s-lchild);printf(%c, s-data);InorderTransverse(s-rchild);/先序递归遍历二叉树void PreOrderTranverseTree(BinTree s)if (s)-.word.zl.-printf(%c, s-data);PreOrderTranverseTree(s-lchild);PreOrderTranverseTree(s-rchild

7、);/后序递归遍历二叉树void PostOrderTranverseTree(BinTree s)if (s)PreOrderTranverseTree(s-lchild);PreOrderTranverseTree(s-rchild);printf(%c, s-data);/*主方法*/void main()BinTreeT;printf(请按照先序的顺序输入要创立的树:n);CreateBinTree(&T);/*中序序列创立二叉树*/printf(中序递归遍历的序列是:);InorderTransverse(T);printf(n);/先序递归遍历printf(先序递归遍历的序列是:)

8、;PreOrderTranverseTree(T);printf(n);/后序递归遍历printf(后序递归遍历的序列是:);PostOrderTranverseTree(T);printf(n);2. 2.非递归非递归#include stdio.h#include conio.h-.word.zl.-#include #include typedef struct nodechar data;struct node *lchild, *rchild;BinTnode;typedef BinTnode * BinTree;/定义二叉树类型的指针typedef structBinTree da

9、ta100;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;intPop(SeqStack *S,BinTree *p)if(S-top=-1)printf(the stack is underflow);return 0;else *p=S-dataS-top;-S-top;return 1;int EmptySta

10、ck(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;-.word.zl.-else *p=S.dataS.top;return 1;char visit(BinTree p)return (*p).data;/*创立二叉树*/int CreateBinTree(BinTree *T)char ch;*T=(BinTree)malloc(sizeof(BinTnode

11、);if(!*T) printf(overflow);elsedoch=getchar();if(ch!= )*T=NULL;return 0;else(*T)-data=ch;CreateBinTree(&(*T)-lchild);CreateBinTree(&(*T)-rchild);return 1;while(ch!=0);/*中序非递归遍历*/void InorderTransverse(BinTree T)SeqStackS;BinTreep;initStack(&S);/初始化栈printf(中序非递归序列是:);Push(&S,T);/根指针进栈T 为指向二叉树的指针while

12、(!EmptyStack(S)/栈不是空的情况while(GetTop(S,&p) & p)Push(&S,p-lchild);/gettop 得到的结果也必须是一棵子树才行,进栈应该进的是树根的指针Pop(&S,&p);if(!EmptyStack(S)/printf(%c,visit(p);Pop(&S,&p);-.word.zl.-printf(%c,visit(p);Push(&S,p-rchild);/*先序非递归遍历*/void PreorderTransverse(BinTree T)SeqStackS;BinTreep;initStack(&S);/初始化栈Push(&S,T)

13、;/根指针进栈T 为指向二叉树的指针printf(先序非递归序列是:);while(!EmptyStack(S)Pop(&S,&p);/根节点出栈if(p!=NULL)printf(%c,visit(p);Push(&S,p-rchild);Push(&S,p-lchild);/*后序非递归遍历*/void PostorderTransverse(BinTree T)SeqStackS;BinTreep,q;initStack(&S);/初始化栈p=T;printf(后序非递归序列是:);while(p |!EmptyStack(S)/跳出 while 循环的原因是因为左子树或者右子树为空了i

14、f(p!=q)while(p!=NULL)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;-.word.zl.-elsep=q-rchild;/*主方法*/void main()BinTreeT;printf(请按照先序的顺序输入创立的树:n);/*创立树*/CreateBinTree(&T);/中序非递归遍历InorderTransverse(T);

15、printf(n);/先序非递归遍历PreorderTransverse(T);printf(n);/后序非递归遍历PostorderTransverse(T);四、运行结果四、运行结果1. 1.递归递归输入结果-.word.zl.-2. 2.非递归非递归输入结果-.word.zl.-五、遇到的问题及解决五、遇到的问题及解决经过一个星期的写代码，我遇到了很多问题，并一一解决了，比方：1.创立二叉树时：void createBiTree(BiTNode *T)和 void createBiTree(BiTNode *&T)没分清楚区别。后来查找资料找到 void createBiTree(BiT

16、Node *T)是将结点的指针地址传递到函数中进展处理void createBiTree(BiTNode *&T是将结点指针的引用传递到函数处理。才理解清楚。2.在写非递归算法时，一直逻辑混乱，后来查找了资料后，又自己缕了一遍，才得到解决。尤其是后序遍历时。六、心得体会六、心得体会在做完本工程之后， 体会最深的就是应该细心， 并且很多时候我们看见某些事情很简单就不想去做，而做的时候又总会遗漏很多需要考虑的细节， 或者根本就不知道从哪入手更好， 在做这个工程时，错过很屡次，很多时候有一种成功离自己很近很近，似乎可以看到，但就是无法接触到的感觉，我想，在以后的学习中， 应该把一些必要的程序都敲一遍，而不要直接说句，简单，然后不屑去做，这样，其实最终很难真正学到什么！-.word.zl