c语言二叉树的先序,中序,后序遍历.pdf

c语言二叉树的先序,中序,后序遍历--第1页

c语言二叉树的先序,中序,后序遍历

1、先序遍历

先序遍历可以想象为，一个小人从一棵二叉树根节点为起点，沿

着二叉树外沿，逆时针走一圈回到根节点，路上遇到的元素顺序，就

是先序遍历的结果

先序遍历结果为：ABDHIEJCFKG

2、中序遍历

中序遍历可以看成，二叉树每个节点，垂直方向投影下来（可以

理解为每个节点从最左边开始垂直掉到地上），然后从左往右数，得

出的结果便是中序遍历的结果

中遍历结果为：HDIBEJAFKCG

c语言二叉树的先序,中序,后序遍历--第1页

c语言二叉树的先序,中序,后序遍历--第2页

3、后序遍历

后序遍历就像是剪葡萄，我们要把一串葡萄剪成一颗一颗的。

还记得我上面提到先序遍历绕圈的路线么？（不记得翻上面理解）

就是围着树的外围绕一圈，如果发现一剪刀就能剪下的葡萄（必须是

一颗葡萄）（也就是葡萄要一个一个掉下来，不能一口气掉超过1个

这样），就把它剪下来，组成的就是后序遍历了。

后序遍历中，根节点默认最后面

后序遍历结果：HIDJEBKFGCA

c语言二叉树的先序,中序,后序遍历--第2页

c语言二叉树的先序,中序,后序遍历--第3页

4、口诀

先序遍历：先根再左再右

中序遍历：先左再根再右

后序遍历：先左再右再根

这里的根，指的是每个分叉子树（左右子树的根节点）根节点，

并不只是最开始头顶的根节点，需要灵活思考理解

5、代码展示

#includestdio.h

#includestdlib.h

typedefstructTree{

intdata;//存放数据域

structTree*lchild;//遍历左子树指针

structTree*rchild;//遍历右子树指针

}Tree,*BitTree;

c语言二叉树的先序,中序,后序遍历--第3页

c语言二叉树的先序,中序,后序遍历--第4页

BitTreeCreateLink()

{

intdata;

inttemp;

BitTreeT;

//输入数据

temp=getchar();//吸收空格

if(data==-1){//输入-1代表此节点

下子树不存数据，也就是不继续递归创建

returnNULL;

}else{

T=

(BitTree)malloc(sizeof(Tree));//分

配内存空间

T-data=

d