二叉树前序遍历的非递归算法

二叉树的前序遍历是先根节点，然后如果有左子树则再先序遍历左子树，然后如果有右子树则再先序遍历其又子树。
递归算法如下


代码如下:

void   preorder(Betree *t)
{   if(t==null) return;visit(t);//访问该节点preorder(t->lchild);preorder(t->rchild); }

当然递归算法是隐式使用了栈。我们仔细分析这个过程，先是取出了根节点进行了访问，然后我们把根节点退栈，退栈后必然有节点进栈，怎么办呢？根节点只能直接访问到rchild和lchild，如果是左子树的根节点进了栈，那么必然是后访问之，所以必然是rchild先进栈，lchild后进栈。可以画图加深理解。
那么现在写出先序遍历二叉树的算法。


代码如下:

void preorder(Betree *t)
{ //算法中我们使用一维数组来模拟一个顺序栈
     if(t==null) return;//为空树的话完全没有必要进行下面的操作    
     Betree *stack[max];
     top=1;stack[top]=t;//根节点入栈
     while(top>0)
    {   nd=stack[top];//取出根节点  top=top-1;//退栈   visit(nd->data); //访问根节点 if(nd->rchild!=null) { top=top+1;stack[top]=nd->rchild;} //根节点有右子树，将其进栈，等到左子树访问完后再访问之
if(nd->lchild!=null) { top=top+1;stack[top]=nd->lchild;}
   }
}

赞 (0)

相关推荐

  • 数据结构 二叉树的递归与非递归

    数据结构 二叉树的递归与非递归 实例代码: #include <iostream> #include <queue> #include <stack> #include <assert.h> using namespace std; template<class T> struct BinaryTreeNode { BinaryTreeNode<T>* _left; BinaryTreeNode<T>* _right; T

  • c语言版本二叉树基本操作示例(先序 递归 非递归)

    c语言版本二叉树基本操作示例(先序 递归 非递归)

    复制代码 代码如下: 请按先序遍历输入二叉树元素(每个结点一个字符,空结点为'='):ABD==E==CF==G== 先序递归遍历:A B D E C F G中序递归遍历:D B E A F C G后序递归遍历:D E B F G C A层序递归遍历:ABCDEFG先序非递归遍历:A B D E C F G中序非递归遍历:D B E A F C G后序非递归遍历:D E B F G C A深度:请按任意键继续. . . 复制代码 代码如下: #include<stdio.h>#include&

  • 二叉树先序遍历的非递归算法具体实现

    二叉树先序遍历的非递归算法具体实现

    在前面一文,说过二叉树的递归遍历算法(二叉树先根(先序)遍历的改进),此文主要讲二叉树的非递归算法,采用栈结构 总结先根遍历得到的非递归算法思想如下: 1)入栈,主要是先头结点入栈,然后visit此结点 2)while,循环遍历当前结点,直至左孩子没有结点 3)if结点的右孩子为真,转入1)继续遍历,否则退出当前结点转入父母结点遍历转入1) 先看符合此思想的算法: 复制代码 代码如下: int PreOrderTraverseNonRecursiveEx(const BiTree &T, int

  • C++基于递归和非递归算法求二叉树镜像的方法

    本文实例讲述了C++基于递归和非递归算法求二叉树镜像的方法.分享给大家供大家参考,具体如下: /*求二叉树镜像 -- 采用递归和非递归方法 经调试可运行源码及分析如下: ***/ #include <stdlib.h> #include <iostream> #include <queue> using std::cout; using std::cin; using std::endl; using std::queue; /*二叉树结点定义*/ typedef st

  • C++非递归建立二叉树实例

    C++非递归建立二叉树实例

    本文实例讲述了C++非递归建立二叉树的方法.分享给大家供大家参考.具体分析如下: 思路: 设置一个标记变量flag并初始化为1. flag = 1表示现在需要创建当前结点的左孩子,2表示需要创建右孩子,3则表示当前结点的左右孩子都已经创建完毕,需要执行出栈操作,直到当前结点不是父结点的右孩子为止. 以先序创建如图所示二杈树: 实现代码: PBTree create() { char ch[20]; scanf("%s",ch); int len = strlen(ch); PBTree

  • C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法

    本文实例讲述了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法.分享给大家供大家参考,具体如下: /*求二叉树叶子节点个数 -- 采用递归和非递归方法 经调试可运行源码及分析如下: ***/ #include <stdlib.h> #include <iostream> #include <stack> using std::cout; using std::cin; using std::endl; using std::stack; /*二叉树结点定义*/

  • C#非递归先序遍历二叉树实例

    本文实例讲述了C#非递归先序遍历二叉树的方法.分享给大家供大家参考.具体如下: using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace ConsoleApplication5 { class Program { static void Main(string[] args) { Node treeRoo

  • 深入遍历二叉树的各种操作详解（非递归遍历）

    深入遍历二叉树的各种操作详解（非递归遍历）

    先使用先序的方法建立一棵二叉树,然后分别使用递归与非递归的方法实现前序.中序.后序遍历二叉树,并使用了两种方法来进行层次遍历二叉树,一种方法就是使用STL中的queue,另外一种方法就是定义了一个数组队列,分别使用了front和rear两个数组的下标来表示入队与出队,还有两个操作就是求二叉树的深度.结点数... 复制代码 代码如下: #include<iostream>#include<queue>#include<stack>using namespace std;/

  • 二叉树前序遍历的非递归算法

    二叉树的前序遍历是先根节点,然后如果有左子树则再先序遍历左子树,然后如果有右子树则再先序遍历其又子树.递归算法如下 复制代码 代码如下: void   preorder(Betree *t){   if(t==null) return;visit(t);//访问该节点preorder(t->lchild);preorder(t->rchild); } 当然递归算法是隐式使用了栈.我们仔细分析这个过程,先是取出了根节点进行了访问,然后我们把根节点退栈,退栈后必然有节点进栈,怎么办呢?根节点只能直

  • C语言数据结构系列篇二叉树的遍历

    C语言数据结构系列篇二叉树的遍历

    目录 前言: Ⅰ. 定义二叉树 0x00二叉树的概念(回顾) 0x00定义二叉树 0x01 手动创建二叉树 Ⅱ. 二叉树的遍历 0x00关于遍历 0x01二叉树前序遍历 0x02二叉树中序遍历 0x03二叉树后序遍历 0x04层序遍历 前言: 学习二叉树的基本操作前,需要先创建一颗二叉树,然后才能学习其相关的基本操作,考虑到我们刚刚接触二叉树,为了能够先易后难地进行讲解,我们将暂时手动创建一颗简单的二叉树,用来方便大家学习.等二叉树结构了解的差不多后,后期我们会带大家研究二叉树地真正的创建方式.

  • C语言详解实现链式二叉树的遍历与相关接口

    C语言详解实现链式二叉树的遍历与相关接口

    目录 前言 一.二叉树的链式结构 二.二叉树的遍历方式 1.1 遍历方式的规则 1.2 前序遍历 1.3 中序遍历 1.4 后序遍历 1.5 层序遍历 三.二叉树的相关接口实现 3.1 二叉树节点个数 3.2 二叉树叶子节点个数 3.3 二叉树第 k 层节点个数 3.4 二叉树的深度(高度) 3.5 二叉树查找值为 x 的节点 3.6 总结 & 注意 四.二叉树的创建和销毁 4.1 通过前序遍历的字符串来构建二叉树 4.2 二叉树销毁 4.3 判断二叉树是否是完全二叉树 前言 二叉树的顺序结构就

  • PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例

    本文实例讲述了PHP基于非递归算法实现先序.中序及后序遍历二叉树操作.分享给大家供大家参考,具体如下: 概述: 二叉树遍历原理如下: 针对上图所示二叉树遍历: 1. 前序遍历:先遍历根结点,然后遍历左子树,最后遍历右子树. ABDHECFG 2.中序遍历:先遍历左子树,然后遍历根结点,最后遍历右子树. HDBEAFCG 3.后序遍历:先遍历左子树,然后遍历右子树,最后遍历根节点. HDEBFGCA 实现方法: 先序遍历:利用栈先进后出的特性,先访问根节点,再把右子树压入,再压入左子树.这样取出的

  • C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】

    C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】

    本文实例讲述了C语言二叉树常见操作.分享给大家供大家参考,具体如下: 一.基本概念 每个结点最多有两棵子树,左子树和右子树,次序不可以颠倒. 性质: 1.非空二叉树的第n层上至多有2^(n-1)个元素. 2.深度为h的二叉树至多有2^h-1个结点. 满二叉树:所有终端都在同一层次,且非终端结点的度数为2. 在满二叉树中若其深度为h,则其所包含的结点数必为2^h-1. 完全二叉树:除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐,即集中在左面的位置上,不能有空位置. 对于完全二叉

  • PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解

    PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解

    本文实例讲述了PHP实现二叉树深度优先遍历(前序.中序.后序)和广度优先遍历(层次).分享给大家供大家参考,具体如下: 前言: 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次.要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历.中序遍历.后序遍历.具体说明如下: 前序遍历:根节点->左子树->右子树 中序遍历:左子树->根节点->右子树 后序遍历:左子树->右子树->根节点 广度优先遍历:又叫层次遍历,从上往下对每一层依

  • Java开发深入分析讲解二叉树的递归和非递归遍历方法

    Java开发深入分析讲解二叉树的递归和非递归遍历方法

    目录 前言 1.递归遍历 2.非迭代遍历 3.二叉树的统一迭代法 前言 二叉树的遍历方法分为前序遍历,中序遍历,后续遍历,层序遍历. 1.递归遍历 对于递归,就不得不说递归三要素:以前序遍历为例 递归入参参数和返回值 因为要打印出前序遍历节点的数值,所以参数里需要传入List在放节点的数值,除了这一点就不需要在处理什么数据了也不需要有返回值,所以递归函数返回类型就是void,代码如下: public void preorder(TreeNode root, List<Integer> resu

随机推荐