C语言达成二叉树的递归遍历与非递归遍历
发布时间：2021-11-20 18:50:17 所属栏目：教程 来源：互联网
导读：本文实现了对二叉树的递归遍历和非递归遍历，当然还包括了一些栈操作。 二叉树的遍历本质上其实就是入栈出栈的问题，递归算法简单且容易理解，但是效率始终是个问题。非递归算法可以清楚的知道每步实现的细节，但是乍一看不想递归算法那么好理解，各有各的好
|
本文实现了对二叉树的递归遍历和非递归遍历，当然还包括了一些栈操作。 二叉树的遍历本质上其实就是入栈出栈的问题，递归算法简单且容易理解，但是效率始终是个问题。非递归算法可以清楚的知道每步实现的细节，但是乍一看不想递归算法那么好理解，各有各的好处吧。接下来根据下图讲讲树的遍历。 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的时候，说明左右子树都已输出，所以该节点也出栈打印出来。 以中序遍历为例，看看栈的内容是如何变化的：  （编辑：常州站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
