用递归非递归两种方法遍历二叉树2957.pdf
实用文档 标准文案 数据结构（双语）项目文档报告 用递归、非递归两种方法遍历二叉树 专 业：计算机科学与技术 班 级：指导教师：姓 名：学 号：实用文档 标准文案 目 录 一、设计思想.03 二、算法流程图.04 三、源代码.06 四、运行结果.12 五、遇到的问题及解决.14 六、心得体会.15 实用文档 标准文案 一、设计思想 1递归：（1）主函数 main（）主程序要包括：定义的二叉树 T、建树函数、先序遍历函数、中序遍历函数、后序遍历函数。（2）建树函数定义一个输入的数是字符型的，当 ch 为空时，T 就为空值，否则的话就分配空间给 T，T就指向它的结点，然后左指针域指向左孩子，右指针指向右孩子，若还有，继续调用,依次循环下去，直到 ch 遇到空时，结束。最后要返回建立的二叉树 T。（3）先序遍历函数根据先序遍历规则，当 T为非空时，先输出结点处的数据，指针指向左、右孩子，依次进行下去。(4)中序遍历函数根据中序遍历规则，当 T为非空时，先左指针指向左孩子数据，然后输出结点处的数据，再右指针指向右孩子，依次进行下去。(5）后序遍历函数根据后序遍历规则，当 T为非空时，先右指针指向右孩子，然后左指针指向左孩子，最后输出结点处的数据，依次进行下去。2.非递归：（1）跟递归遍历二叉树的前提一样，首先应该创建一个二叉树，同样使用先序递归的方式创建二叉树。（2）然后是中序，先序，后序非递归遍历二叉树。（3）中序非递归遍历二叉树的思想是：首先是根节点压栈，当根节点的左子树不是空的时候，左子树压栈。直到左子树为空的时候，不再压栈。将栈顶元素出栈，访问栈顶元素，并将栈顶的右子树进栈。当右子树的左子树不是空的时候，左子树一直进栈，直到左子树为空，则不再进栈。重复上面的操作，直到栈空的时候。(4)先序非递归遍历二叉树的思想是：首先是根节点进栈，然后当栈不为空的时候，将栈顶元素出栈，然后访问。同时将出栈元素的右子树进栈，左子树进栈。重复上面的操作，直到栈为空。(5）后序非递归遍历二叉树的思想：首先是根节点进栈，当根节点的左子树不为空的时候，左子树进栈，直到左为空的时候，左子树不再进栈。指针指向的是右子树，当右子树为空的时候，直接访问根节点。当右子树不为空的时候，则右子树的指针进栈，当右子树的左子树不为空的时候，则左也进栈，直到左为空。重复上面的操作，直到栈为空的时候，则遍历树完成。实用文档 标准文案 二、算法流程图 1.递归 实用文档 标准文案 2.非递归 实用文档 标准文案 三、源代码 1.递归#include stdio.h#include conio.h#include#include typedef struct node char data;struct node*lchild,*rchild;BinTnode;typedef BinTnode*BinTree;/定义二叉树类型的指针/*先序创建二叉树*/int CreateBinTree(BinTree*T)char ch;*T=(BinTree)malloc(sizeof(BinTnode);if(!*T)printf(overflow);do ch=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 s)if(s)InorderTransverse(s-lchild);printf(%c,s-data);InorderTransverse(s-rchild);/先序递归遍历二叉树 实用文档 标准文案 void PreOrderTranverseTree(BinTree s)if(s)printf(%c,s-data);PreOrderTranverseTree(s-lchild);PreOrderTranverseTree(s-rchild);/后序递归遍历二叉树 void PostOrderTranverseTree(BinTree s)if(s)PreOrderTranverseTree(s-lchild);PreOrderTranverseTree(s-rchild);printf(%c,s-data);/*主方法*/void main()BinTree T;printf(请按照先序的顺序输入要创建的树:n);CreateBinTree(&T);/*中序序列创建二叉树*/printf(中序递归遍历的序列是:);InorderTransverse(T);printf(n);/先序递归遍历 printf(先序递归遍历的序列是:);PreOrderTranverseTree(T);printf(n);/后序递归遍历 printf(后序递归遍历的序列是:);PostOrderTranverseTree(T);printf(n);实用文档 标准文案 2.非递归#include stdio.h#include conio.h#include#include typedef struct node char data;struct node*lchild,*rchild;BinTnode;typedef BinTnode*BinTree;/定义二叉树类型的指针 typedef struct BinTree 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 stack 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)return(*p).data;/*创建二叉树*/int CreateBinTree(BinTree*T)char ch;*T=(BinTree)malloc(sizeof(BinTnode);if(!*T)printf(overflow);else do ch=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)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(&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);/根指针进栈 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)SeqStack S;BinTree p,q;initStack(&S);/初始化栈 p=T;printf(后序非递归序列是:);while(p|!EmptyStack(S)/跳出 while 循环的原因是因为左子树或者右子树为空了 if(p!=q)while(p!=NULL)Push(&S,p);if(p-lchild!=NULL)p=p-lchild;else p=p-rchild;if(EmptyStack(S)break;GetTop(S,&q);if(q-rchild=p)/进栈的是右子树 Pop(&S,&p);printf(%c,visit(p);实用文档 标准文案 p=q;else p=q-rchild;/*主方法*/void main()BinTree T;printf(请按照先序的顺序输入创建的树:n);/*创建树*/CreateBinTree(&T);/中序非递归遍历 InorderTransverse(T);printf(n);/先序非递归遍历 PreorderTransverse(T);printf(n);/后序非递归遍历 PostorderTransverse(T);四、运行结果 1.递归 输入 实用文档 标准文案 结果 2.非递归 输入 结果 实用文档 标准文案 五、遇到的问题及解决 经过一个星期的写代码，我遇到了很多问题，并一一解决了，比如：1.创建二叉树时：void createBiTree(BiTNode*T)和 void createBiTree(BiTNode*&T)没分清楚区别。后来查找资料找到 void createBiTree(BiTNode*T)是将结点的指针（地址）传递到函数中进行处理 void createBiTree(BiTNode*&T 是将结点指针的引用传递到函数处理。才理解清楚。2.在写非递归算法时，一直逻辑混乱，后来查找了资料后，又自己缕了一遍，才得到解决。尤其是后序遍历时。六、心得体会 在做完本项目之后，体会最深的就是应该细心，并且很多时候我们看见某些事情很简单就不想去做，而做的时候又总会遗漏很多需要考虑的细节，或者根本就不知道从哪入手更好，在做这个项目时，错过很多次，很多时候有一种成功离自己很近很近，似乎可以看到，但就是无法接触到的感觉，我想，在以后的学习中，应该把一些必要的程序都敲一遍，而不要直接说句，简单，然后不屑去做，这样，其实最终很难真正学到什么！
