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

在前面一文,说过二叉树的递归遍历算法(二叉树先根(先序)遍历的改进),此文主要讲二叉树的非递归算法,采用栈结构

总结先根遍历得到的非递归算法思想如下:

1)入栈,主要是先头结点入栈,然后visit此结点

2)while,循环遍历当前结点,直至左孩子没有结点

3)if结点的右孩子为真,转入1)继续遍历,否则退出当前结点转入父母结点遍历转入1)

先看符合此思想的算法:

代码如下:

int PreOrderTraverseNonRecursiveEx(const BiTree &T, int (*VisitNode)(TElemType data))
{
 if (T == NULL)
 {
  return -1;
 }

BiTNode *pBiNode = T;
 SqStack S;
 InitStack(&S);
 Push(&S, (SElemType)T);

while (!IsStackEmpty(S))
 {
  while (pBiNode)
  {
   VisitNode(pBiNode->data);
   if (pBiNode != T)
   {
    Push(&S, (SElemType)pBiNode);
   }   
   pBiNode = pBiNode->lchild;
  }
  if(pBiNode == NULL)
  {
   Pop(&S, (SElemType*)&pBiNode);
  }  
  if ( pBiNode->rchild == NULL)
  {
   Pop(&S, (SElemType*)&pBiNode); //如果此时栈已空,就有问题
  }
  pBiNode = pBiNode->rchild;
 }

return 0;
}

注意:1)这里使用了栈结构,可参看上文顺序结构存储的栈

2)这里在保存结点的时候,我保存的是指针也就是结点的地址,将其变为int型存储,在pop的时候里面使用的是指针,所以取的是&pBiNode,而不是pBiNode,为什么请自行思考指针的使用,最好理解的就是BiTNode *pBiNode;定义改为BiTree pBiNode就很好理解了。

上面这个算法其实是错误的!为什么呢? 这里我检查好久,期间出现还出现过无限循环,也出现过从左子树退出后右边子树不显示,最后我修改了第一个while判断条件,为什么呢?因为如果在pop之后,栈已空但是右子树还有,就无法继续了,这个在我写出后并没有进行太多验证,后面再阐述,这里并没有压入null指针,看一下压入空指针的例子,主要是左子树为空的时候才压入栈的,如下:

代码如下:

int PreOrderTraverseNonRecursive(const BiTree &T, int (*VisitNode)(TElemType data))
{
 if (T == NULL)
 {
  return -1;
 }

BiTNode *pBiNode = T;
 SqStack S;
 InitStack(&S);
 Push(&S, (SElemType)T);

while (!IsStackEmpty(S))
 {
  GetTop(S, (SElemType*)&pBiNode);
  while (pBiNode)
  {
   VisitNode(pBiNode->data);  
   pBiNode = pBiNode->lchild;
   Push(&S, (SElemType)pBiNode);
  }
  if(pBiNode == NULL)
  {
   Pop(&S, (SElemType*)&pBiNode);
  }  
  if ( !IsStackEmpty(S))
  {
   Pop(&S, (SElemType*)&pBiNode);
   pBiNode = pBiNode->rchild;
   Push(&S, (SElemType)pBiNode);
  }
 }

return 0;
}

这里是这样的,先压入根节点,然后判断左子树是否为空,不为空就压入栈,否则退出while循环之后就将NULL结点出栈,再判断当前栈是否为空,如果非空就出栈得到父节点然后判断右孩子,压入右孩子结点,再判断此右子树的左孩子是否为空,继续循环。

这里有两个浪费的地方:一个就是压入空孩子结点入栈,二就是频繁使用GetTop获得栈顶元素

这里返回过来再看初开始设计的算法,那里正好没有压入NULL指针或者说空的孩子结点,但是并不能输出完整,这里我们想到可以在判断栈的时候加入,当前的结点是否为NULL就可以了,这样就不会出现不会显示退出左子树结点不能显示右子树结点的尴尬了,如下:

代码如下:

//非递归先序遍历二叉树
int PreOrderTraverseNonRecursiveEx(const BiTree &T,
           int (*VisitNode)(TElemType data))
{
 if (T == NULL)
 {
  return -1;
 }

BiTNode *pBiNode = T;
 SqStack S;
 InitStack(&S);
 Push(&S, (SElemType)T);

while ( !IsStackEmpty(S) || pBiNode)  //主要修改的就是这句
 {
  while (pBiNode)
  {
   VisitNode(pBiNode->data);
   if (pBiNode != T)
   {
    Push(&S, (SElemType)pBiNode);
   }   
   pBiNode = pBiNode->lchild;
  }
  if(pBiNode == NULL)
  {
   Pop(&S, (SElemType*)&pBiNode);
  }  
  if ( pBiNode->rchild == NULL)
  {
   Pop(&S, (SElemType*)&pBiNode); //如果此时栈已空,就有问题
  }
  pBiNode = pBiNode->rchild;
 }
 return 0;
}

在第一个while循环加入这个之后,就可以了,测试用例与二叉树先序遍历类似。如下测试上节的二叉树例子:

此时输入的数据仍然还是 12 34 0 0 78 0 0,测试结果如下:

--- BiTree ---
Please Enter BiTree Node data:
12
Please Enter BiTree Node data:
34
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
78
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
0
12 34 78

这个还不足以测试,再看如下的二叉树

此时输入数据应该为:12 34 24 0 0 50 0 0 78 37 0 0 0,测试结果如下:

--- BiTree ---
Please Enter BiTree Node data:
12
Please Enter BiTree Node data:
34
Please Enter BiTree Node data:
24
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
50
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
78
Please Enter BiTree Node data:
37
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
0
Please Enter BiTree Node data:
0
12 34 24 50 78 37

由先序遍历可知,正好是正确的,另外这些算法不光是对先序遍历的,如果想变为中序或者后序,只需将上面算法中的visit之类的先去掉,然后将它加入合适的位置,就可以了

(0)

相关推荐

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

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

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

    先使用先序的方法建立一棵二叉树,然后分别使用递归与非递归的方法实现前序.中序.后序遍历二叉树,并使用了两种方法来进行层次遍历二叉树,一种方法就是使用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++基于递归和非递归算法求二叉树镜像的方法.分享给大家供大家参考,具体如下: /*求二叉树镜像 -- 采用递归和非递归方法 经调试可运行源码及分析如下: ***/ #include <stdlib.h> #include <iostream> #include <queue> using std::cout; using std::cin; using std::endl; using std::queue; /*二叉树结点定义*/ typedef st

  • 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&

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

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

  • 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

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

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

  • 先序遍历二叉树的递归实现与非递归实现深入解析

    1.先序遍历二叉树  递归实现思想:若二叉树为空,返回.否则 1)遍历根节点:2)先序遍历左子树:3)先序遍历右子树: 代码: 复制代码 代码如下: template<typename elemType> void PreOrder(nodeType<elemType> *root)  {      if(root==NULL)          return ;      visit(root->data); // visit the data    PreOrder(ro

  • 探讨:C++实现链式二叉树(用非递归方式先序,中序,后序遍历二叉树)

    如有不足之处,还望指正! 复制代码 代码如下: // BinaryTree.cpp : 定义控制台应用程序的入口点.//C++实现链式二叉树,采用非递归的方式先序,中序,后序遍历二叉树#include "stdafx.h"#include<iostream>#include<string>#include <stack>using namespace std;template<class T>struct BiNode{ T data; 

  • C++实现LeetCode(145.二叉树的后序遍历)

    [LeetCode] 145. Binary Tree Postorder Traversal 二叉树的后序遍历 Given a binary tree, return the postorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3},    1 \ 2 / 3 return [3,2,1]. Note: Recursive solution is trivial, could you d

  • 通过先序遍历和中序遍历后的序列还原二叉树(实现方法)

    当我们有一个 先序遍历序列:1,3,7,9,5,11 中序遍历序列:9,7,3,1,5,11 我们可以很轻松的用笔写出对应的二叉树.但是用代码又该如何实现? 下面我们来简单谈谈基本思想. 首先,先序遍历的顺序是根据 根-左孩子-右孩子 的顺序遍历的,那么我们可以率先确认的是先序遍历序列的第一个数就是根节点,然后中序遍历是根据 左孩子-根-右孩子 的顺序遍历的.我们通过先序遍历确认了根节点,那么我们只需要在中序遍历中找到根节点的位置,然后就可以很好地区分出,那些属于左子树的节点,那些是属于右子树的

  • JavaScript实现二叉树定义、遍历及查找的方法详解

    本文实例讲述了JavaScript实现二叉树定义.遍历及查找的方法.分享给大家供大家参考,具体如下: 二叉树(binary tree) 在写这篇文章之前说一下数据结构和算法这个系列,这个系列包含了很多东西,比如啥子排序,线性表,广义表,树,图这些大家都是知道的,但是这些东西我们学了之后工作中能用到的又有多少呢,据我所知绝大部分公司,一线码农,屌丝,程序猿是用不到这些东西,既然这样为啥子我还要强调这个系列呢,本人觉得算法和数据结构是程序的基本功,前提想脱离一线码农,普通程序猿行列,说得通俗一点就是

  • Java实现二叉树的深度优先遍历和广度优先遍历算法示例

    本文实例讲述了Java实现二叉树的深度优先遍历和广度优先遍历算法.分享给大家供大家参考,具体如下: 1. 分析 二叉树的深度优先遍历的非递归的通用做法是采用栈,广度优先遍历的非递归的通用做法是采用队列. 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次.要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历.中序遍历.后序遍历.具体说明如下: 先序遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树. 中序遍历:对任一子树,先遍历其左子树,然

  • C语言进阶练习二叉树的递归遍历

    目录 二叉树的前中后序遍历 遍历二叉树求二叉树的结点个数 遍历二叉树求二叉树的叶子结点个数 求二叉树中data为x的结点 求二叉树的深度 二叉树的前中后序遍历 所谓二叉树遍历(Traversal)是按照某种特定的规则,依次对二叉树中的节点进行相应的操作,并且每个节点只操作一次.访问结点所做的操作依赖于具体的应用问题. 遍历 是二叉树上最重要的运算之一,也是二叉树上进行其它运算的基础. 按照规则,二叉树的遍历有:前序/中序/后序的递归结构遍历: 1. 前序遍历(Preorder Traversal

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

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

随机推荐