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

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

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

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

4、接访问根节点。当右子树不为空的时候，则右子树的指针进栈，当右子树的左子树不为空的时候，则左也进栈，直到左为空。重复上面的操作，直到栈为空的时候，则遍历树完成。 二、算法流程图1.递归2.非递归三、源代码1.递归#include "stdio.h"#include "conio.h"#include <stdlib.h>#include<stack>typedef struct node char data; struct node *lchild, *rchild;BinTnode;typedef BinTnode * BinTr

5、ee; /定义二叉树类型的指针/*先序创建二叉树*/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

6、; 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);P

7、reOrderTranverseTree(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); /*中序序列创建二叉树*/

8、printf("中序递归遍历的序列是:"); InorderTransverse(T); printf("n"); /先序递归遍历 printf("先序递归遍历的序列是:"); PreOrderTranverseTree(T); printf("n"); /后序递归遍历 printf("后序递归遍历的序列是:"); PostOrderTranverseTree(T); printf("n");2.非递归#include "stdio.h"#include

9、"conio.h"#include <stack>#include <stdlib.h>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

10、(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.to

11、p=-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

12、) 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; initStac

13、k(&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

14、); 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"

15、;,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->lc

16、hild!=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);/中序非递归遍

17、历 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 *&