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

2021年1月25日发(作者：京戏)
用递归、非递归两种方法遍历二叉树




数据结构（双语）

——项目文档报告


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






专




业：


计算机科学与技术








班




级：





















指导教师：















姓




名：



















学




号：























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

目




录

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















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

一、设计思想

1
．递归：

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

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

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

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

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

2.
非递归：

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

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

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

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

(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 -