C语言实现二叉树的递归遍历与非递归遍历
本文实现了对二叉树的递归遍历和非递归遍历,当然还包括了一些栈操作。
二叉树的遍历本质上其实就是入栈出栈的问题,递归算法简单且容易理解,但是效率始终是个问题。非递归算法可以清楚的知道每步实现的细节,但是乍一看不想递归算法那么好理解,各有各的好处吧。接下来根据下图讲讲树的遍历。
1、先序遍历:先序遍历是先输出根节点,再输出左子树,最后输出右子树。上图的先序遍历结果就是:ABCDEF
2、中序遍历:中序遍历是先输出左子树,再输出根节点,最后输出右子树。上图的中序遍历结果就是:CBDAEF
3、后序遍历:后序遍历是先输出左子树,再输出右子树,最后输出根节点。上图的后序遍历结果就是:CDBFEA
其中,后序遍历的非递归算法是最复杂的,我用了一个标识符isOut来表明是否需要弹出打印。因为只有当节点的左右子树都打印后该节点 才能弹出栈打印,所以标识isOut为1时打印,isOut初始值为0,这主要是为了处理非叶子节点。由后序遍历的原理决定,左右子树都被打印该节点才能打印,所以该节点肯定会被访问2次,第一次的时候不要打印,第二次打印完右子树的时候打印。叶子节点打印完后将isOut置为1。(纯粹是自己想的,应该还有逻辑更简单的算法)
isOut处理具体如下:
- 所有节点入栈的时候初始化为0;
- 叶子节点打印输出后将isOut置为1;
- 非叶子节点分两种情况。如果存在左子树,则输出左子树后将isOut置为1,此时指针已获得其右子树节点;如果不存在左子树,则将isOut置为1,此时指针已获得其右子树节点;在代码中分别体现在 if ( (p->lchild) && (p->lchild->isOut == 1) ) {//如果存在左子树,并且左子树已经遍历完,则说明该节点已经入栈,不用再次Push,直接走向右子树
p->isOut = 1;
p = p->rchild;
}和 if (!StackEmpty(s))
{
GetTop(s,p);
if ( p->lchild == NULL )
p->isOut = 1; //右子树已输出,将父节点isOut置1
}; - 遇到isOut=1的时候,说明左右子树都已输出,所以该节点也出栈打印出来。
以中序遍历为例,看看栈的内容是如何变化的:
相关阅读:
相关推荐
baike 2020-05-09
steeven 2020-11-10
Tips 2020-10-14
nongfusanquan0 2020-08-18
yedaoxiaodi 2020-07-26
清溪算法君老号 2020-06-27
pengkingli 2020-06-25
yishujixiaoxiao 2020-06-25
清溪算法 2020-06-21
RememberMePlease 2020-06-17
nurvnurv 2020-06-05
SystemArchitect 2020-06-02
码墨 2020-05-29
清溪算法 2020-05-27
choupiaoyi 2020-05-27
清溪算法 2020-05-25
bluewelkin 2020-05-19
dbhllnr 2020-05-15
steeven 2020-05-09