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

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

数据结构（双语）

——项目文档报告

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

专 业： 计算机科学与技术 班 级： 指导教师： 姓 名： 学 号：

- 1 -

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

目 录

一、设计思想……………………………………………………….03 二、算法流程图…………………………………………………….04 三、源代码………………………………………………………….06 四、运行结果……………………………………………………….12 五、遇到的问题及解决…………………………………………….14 六、心得体会……………………………………………………….15

- 2 -

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

一、设计思想

1．递归：

（1）主函数main（）主程序要包括：定义的二叉树T、建树函数、先序遍历函数、中序遍历函数、后序遍历函数。

（2）建树函数定义一个输入的数是字符型的，当ch为空时，T就为空值，否则的话就分配空间给T，T就指向它的结点，然后左指针域指向左孩子，右指针指向右孩子，若还有，继续调用,依次循环下去，直到ch遇到空时，结束。最后要返回建立的二叉树T。

（3）先序遍历函数根据先序遍历规则，当T为非空时，先输出结点处的数据，指针指向左、右孩子，依次进行下去。

(4) 中序遍历函数根据中序遍历规则，当T为非空时，先左指针指向左孩子数据，然后输出结点处的数据，再右指针指向右孩子，依次进行下去。

(5）后序遍历函数根据后序遍历规则，当T为非空时，先右指针指向右孩子，然后左指针指向左孩子，最后输出结点处的数据，依次进行下去。

2.非递归：

（1）跟递归遍历二叉树的前提一样，首先应该创建一个二叉树，同样使用先序递归的方式创建二叉树。

（2）然后是中序，先序，后序非递归遍历二叉树。

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

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

(5）后序非递归遍历二叉树的思想：首先是根节点进栈，当根节点的左子树不为空的时候，左子树进栈，直到左为空的时候，左子树不再进栈。指针指向的是右子树，当右子树为空的时候，直接访问根节点。当右子树不为空的时候，则右子树的指针进栈，当右子树的左子树不为空的时候，则左也进栈，直到左为空。重复上面的操作，直到栈为空的时候，则遍历树完成。

- 3 -

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

二、算法流程图

1.递归

- 4 -

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

2.非递归

- 5 -

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

三、源代码

1.递归

#include \#include \#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(\ 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(\

InorderTransverse(s->rchild); } }

//先序递归遍历二叉树

- 6 -

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

void PreOrderTranverseTree(BinTree s){ if (s) {

printf(\

PreOrderTranverseTree(s->lchild); PreOrderTranverseTree(s->rchild); } }

//后序递归遍历二叉树

void PostOrderTranverseTree(BinTree s){ if (s) {

PreOrderTranverseTree(s->lchild); PreOrderTranverseTree(s->rchild); printf(\ } }

/*主方法*/ void main(){ BinTree T;

printf(\请按照先序的顺序输入要创建的树:\\n\ CreateBinTree(&T); /*中序序列创建二叉树*/ printf(\中序递归遍历的序列是:\ InorderTransverse(T); printf(\ //先序递归遍历

printf(\先序递归遍历的序列是:\ PreOrderTranverseTree(T); printf(\ //后序递归遍历

printf(\后序递归遍历的序列是:\ PostOrderTranverseTree(T); printf(\ }

- 7 -

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

2.非递归

#include \#include \#include #include typedef struct node{ char data;

struct node *lchild, *rchild; }BinTnode;

typedef BinTnode * BinTree; //定义二叉树类型的指针 typedef struct{

BinTree data[100]; int top; }SeqStack;

void initStack(SeqStack *S){ S->top =-1; }

void Push(SeqStack *S,BinTree x){ if(S->top==100-1){

printf(\ }

else {

S->top=S->top+1; S->data[S->top]=x; } }

int Pop(SeqStack *S,BinTree *p){ if(S->top==-1){

printf(\ return 0; }

else {

*p=S->data[S->top]; --S->top; return 1; } }

int EmptyStack(SeqStack S){ if(S.top==-1) return 1;

else return 0; /* 栈不空的情况*/ }

int GetTop(SeqStack S,BinTree *p){

- 8 -

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

if(S.top==-1){

printf(\ return 0; }

else {

*p=S.data[S.top]; return 1; } }

char visit(BinTree p){ return (*p).data; }

/*创建二叉树*/

int CreateBinTree(BinTree *T){ char ch;

*T=(BinTree)malloc(sizeof(BinTnode)); if(!*T) printf(\ 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);

- 9 -

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

if(!EmptyStack(S)){

//printf(\ Pop(&S,&p);

printf(\ 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(\ 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);

- 10 -

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

printf(\ p=q; } else{

p=q->rchild; } } }

/*主方法*/ void main(){ BinTree T;

printf(\请按照先序的顺序输入创建的树:\\n\ /*创建树*/

CreateBinTree(&T); //中序非递归遍历 InorderTransverse(T); printf(\

//先序非递归遍历 PreorderTransverse(T); printf(\

//后序非递归遍历

PostorderTransverse(T); }

四、运行结果

1.递归 输入

- 11 -

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

结果

2.非递归 输入

结果

- 12 -

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

五、遇到的问题及解决

经过一个星期的写代码，我遇到了很多问题，并一一解决了，比如： 1. 创建二叉树时：void createBiTree(BiTNode *T)和void createBiTree(BiTNode *&T)

没分清楚区别。

后来查找资料找到void createBiTree(BiTNode *T)是将结点的指针（地址）传递到函数中进行处理

void createBiTree(BiTNode *&T是将结点指针的引用传递到函数处理。 才理解清楚。

2. 在写非递归算法时，一直逻辑混乱，后来查找了资料后，又自己缕了一遍，才得到

解决。尤其是后序遍历时。

六、心得体会

在做完本项目之后，体会最深的就是应该细心，并且很多时候我们看见某些事情很简单

就不想去做，而做的时候又总会遗漏很多需要考虑的细节，或者根本就不知道从哪入手更好，在做这个项目时，错过很多次，很多时候有一种成功离自己很近很近，似乎可以看到，但就是无法接触到的感觉，我想，在以后的学习中，应该把一些必要的程序都敲一遍，而不要直接说句，简单，然后不屑去做，这样，其实最终很难真正学到什么！

- 13 -

本文来源：https://www.bwwdw.com/article/060o.html