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

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

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

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

4、空的时候，左子树进栈，直到左为空的时候，左子树不再进栈。指针指向的是右子树，当右子树为空的时候，直接访问根节点。当右子树不为空的时候，那么右子树的指针进栈，当右子树的左子树不为空的时候，那么左也进栈，直到左为空。重复上面的操作，直到栈为空的时候，那么遍历树完成。专业资料整理WORD格式标准文案专业资料整理WORD格式实用文档二、算法流程图1. 递归专业资料整理WORD格式标准文案专业资料整理WORD格式实用文档2. 非递归专业资料整理WORD格式标准文案专业资料整理WORD格式实用文档三、源代码1. 递归#include "stdio.h"#include "co

5、nio.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=getchar();

6、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)专业资料整理WORD格式标准文案专业资料整理WORD格式实用文档InorderTransverse(s->lchild);printf("%c", s

7、->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);PreOr

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

9、eTree(T);printf("n");/ 后序递归遍历printf("后序递归遍历的序列是:");PostOrderTranverseTree(T);printf("n");专业资料整理WORD格式标准文案专业资料整理WORD格式实用文档2. 非递归#include "stdio.h"#include "conio.h"#include <stack>#include <stdlib.h>typedef struct nodechar data;struct node

10、 *lchild, *rchild;BinTnode;typedef BinTnode * BinTree; / 定义二叉树类型的指针 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;in

11、t 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;专业资料整理WORD格式标准文案专业资料整理WORD格式实用文档int EmptyStack(SeqStack S)if(S.top=-1) return 1;else return 0; /*栈不空的情况*/int GetTop(SeqStack S,BinTree *p)if(S.top=-1)print

12、f("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");elsedoch=getchar();if(ch!=' ')*T=NULL;return 0;else(*T)->d

13、ata=ch;CreateBinTree(&(*T)->lchild);CreateBinTree(&(*T)->rchild);return 1;while(ch!='0');/* 中序非递归遍历*/void InorderTransverse(BinTree T)SeqStack S;BinTreep;initStack(&S);/初始化栈printf("中序非递归序列是:");专业资料整理WORD格式标准文案专业资料整理WORD格式实用文档Push(&S,T); /根指针进栈T为指向二叉树的指针while(!

14、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(B

15、inTree T)SeqStack S;BinTreep;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)

16、SeqStack S;BinTreep,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;elsep=p->rchild;专业资料整理WORD格式标准文案专业资料整理WORD格式实用文档if(EmptyStack(S) break;GetTop(S,&q);if(q-&

17、gt;rchild=p)/进栈的是右子树Pop(&S,&p);printf("%c",visit(p);p=q;elsep=q->rchild;/* 主方法 */void main()BinTreeT;printf("请按照先序的顺序输入创立的树:n");/* 创立树 */CreateBinTree(&T);/ 中序非递归遍历InorderTransverse(T);printf("n");/ 先序非递归遍历PreorderTransverse(T);printf("n");/ 后序非

18、递归遍历PostorderTransverse(T);四、运行结果1. 递归输入专业资料整理WORD格式标准文案专业资料整理WORD格式实用文档结果2. 非递归输入专业资料整理WORD格式标准文案专业资料整理WORD格式实用文档结果五、遇到的问题及解决经过一个星期的写代码，我遇到了很多问题，并一一解决了，比方：1.创立二叉树时： void createBiTree(BiTNode*T) 和 void createBiTree(BiTNode*&T)没分清楚区别。后来查找资料找到void createBiTree(BiTNode *T)是将结点的指针地址传递到函数中进展处理void createBiTree(BiTNode *&T是将结点指针的引用传递到函数处理。才理解清楚。专业资料整理WORD格式标