二叉树的非递归后序遍历算法实例详解

前序、中序、后序的非递归遍历中，要数后序最为麻烦，如果只在栈中保留指向结点的指针，那是不够的，必须有一些额外的信息存放在栈中。
方法有很多，这里只举一种，先定义栈结点的数据结构

代码如下:

typedef struct{Node * p; int rvisited;}SNode //Node 是二叉树的结点结构，rvisited==1代表p所指向的结点的右结点已被访问过。

lastOrderTraverse(BiTree bt){
　　//首先，从根节点开始，往左下方走，一直走到头，将路径上的每一个结点入栈。
　　p = bt;
　　while(bt){
　　　　push(bt, 0); //push到栈中两个信息，一是结点指针，一是其右结点是否被访问过
　　　　bt = bt.lchild;
　　}

　　//然后进入循环体
　　while(!Stack.empty()){ //只要栈非空
　　　　sn = Stack.getTop(); // sn是栈顶结点

　　　　//注意，任意一个结点N，只要他有左孩子，则在N入栈之后，N的左孩子必然也跟着入栈了(这个体现在算法的后半部分)，所以当我们拿到栈顶元素的时候，可以确信这个元素要么没有左孩子，要么其左孩子已经被访问过，所以此时我们就不关心它的左孩子了，我们只关心其右孩子。

　　　　//若其右孩子已经被访问过，或是该元素没有右孩子，则由后序遍历的定义，此时可以visit这个结点了。
　　　　if(!sn.p.rchild || sn.rvisited){
　　　　　　p = pop();
　　　　　　visit(p);
　　　　}
　　　　else //若它的右孩子存在且rvisited为0，说明以前还没有动过它的右孩子，于是就去处理一下其右孩子。
　　　　{
　　　　　　//此时我们要从其右孩子结点开始一直往左下方走，直至走到尽头，将这条路径上的所有结点都入栈。

　　　　　　//当然，入栈之前要先将该结点的rvisited设成1，因为其右孩子的入栈意味着它的右孩子必将先于它被访问(这很好理解，因为我们总是从栈顶取出元素来进行visit)。由此可知，下一次该元素再处于栈顶时，其右孩子必然已被visit过了，所以此处可以将rvisited设置为1。
　　　　　　sn.rvisited = 1;

　　　　　　//往左下方走到尽头，将路径上所有元素入栈
　　　　　　p = sn.p.rchild;
　　　　　　while(p != 0){
　　　　　　　　push(p, 0);
　　　　　　　　p = p.lchild;
　　　　　　}
　　　　}//这一轮循环已结束，刚刚入栈的那些结点我们不必管它了，下一轮循环会将这些结点照顾的很好。
　　}
}

赞 (0)

相关推荐

  • 判断整数序列是否为二元查找树的后序遍历结果的解决方法

    题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果.如果是返回true,否则返回false.例如输入5.7.6.9.11.10.8,由于这一整数序列是如下树的后序遍历结果.    8    / \  6   10 / \    / \ 5  7 9 11因此返回true.如果输入7.4.6.5,没有哪棵树的后序遍历的结果是这个序列,因此返回false.本题网上已经有用递归单纯判断的解法. 个人解法: 先得到序列对应的中序序列, 然后看中序序列是否从小到大有序, 得出判断. 相比

  • C语言数据结构树之后序遍历的实现

    C语言数据结构树之后序遍历的实现

    后续遍历的实现: 数据结构树中的后续遍历,这里提供简单实例,代码中有注释,大家参考下! 看下实现效果: 题目及分析 给定树的先序遍历和中序遍历,求后续遍历 输入 abdec dbeac 输出 debca 三.实现代码: #include <iostream> #include <string> using namespace std; string s1="abdec";//先序遍历 string s2="dbeac";//中序遍历 void

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

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

  • C#使用前序遍历、中序遍历和后序遍历打印二叉树的方法

    本文实例讲述了C#使用前序遍历.中序遍历和后序遍历打印二叉树的方法.分享给大家供大家参考.具体实现方法如下: public class BinaryTreeNode { public BinaryTreeNode Left { get; set; } public BinaryTreeNode Right { get; set; } public int Data { get; set; } public BinaryTreeNode(int data) { this.Data = data;

  • 二叉树的非递归后序遍历算法实例详解

    前序.中序.后序的非递归遍历中,要数后序最为麻烦,如果只在栈中保留指向结点的指针,那是不够的,必须有一些额外的信息存放在栈中.方法有很多,这里只举一种,先定义栈结点的数据结构 复制代码 代码如下: typedef struct{Node * p; int rvisited;}SNode //Node 是二叉树的结点结构,rvisited==1代表p所指向的结点的右结点已被访问过. lastOrderTraverse(BiTree bt){ //首先,从根节点开始,往左下方走,一直走到头,将路径上

  • C语言数据结构之二叉树的非递归后序遍历算法

    C语言数据结构之二叉树的非递归后序遍历算法 前言: 前序.中序.后序的非递归遍历中,要数后序最为麻烦,如果只在栈中保留指向结点的指针,那是不够的,必须有一些额外的信息存放在栈中. 方法有很多,这里只举一种,先定义栈结点的数据结构 typedef struct{Node * p; int rvisited;}SNode //Node 是二叉树的结点结构,rvisited==1代表p所指向的结点的右结点已被访问过. lastOrderTraverse(BiTree bt){ //首先,从根节点开始,

  • C语言非递归后序遍历二叉树

    C语言非递归后序遍历二叉树

    本文实例为大家分享了C语言非递归后序遍历二叉树的具体代码,供大家参考,具体内容如下 法一:实现思路:一个栈 先按 根->右子树->左子树的顺序访问二叉树.访问时不输出.另一个栈存入前一个栈只进栈的结点. 最后输出后一个栈的结点数据. #include<stdio.h> #include<stdlib.h> typedef struct TreeNode{ char element; struct TreeNode *left,*right; }Tree,*BTree;

  • java非递归实现之二叉树的前中后序遍历详解

    二叉树的前中后序遍历 核心思想:用栈来实现对节点的存储.一边遍历,一边将节点入栈,在需要时将节点从栈中取出来并遍历该节点的左子树或者右子树,重复上述过程,当栈为空时,遍历完成. 前序遍历 //非递归 //根 左 右 class Solution { public List<Integer> preorderTraversal(TreeNode root) { //用数组来存储前序遍历结果 List<Integer> list = new ArrayList<>(); i

  • C++ 非递归实现二叉树的前中后序遍历

    C++ 非递归实现二叉树的前中后序遍历

    目录 二叉树的前序遍历 二叉树的中序遍历 二叉树的后序遍历 二叉树的前序遍历 在不使用递归的方式遍历二叉树时,我们可以使用一个栈模拟递归的机制.二叉树的前序遍历顺序是:根 → 左子树 → 右子树,我们可以先将二叉树的左路结点入栈,在入栈的同时便对其进行访问,此时就相当于完成了根和左子树的访问,当左路结点入栈完毕后再从栈顶依次取出结点,并用同样的方式访问其右子树即可. 具体步骤如下: 将左路结点入栈,入栈的同时访问左路结点. 取出栈顶结点top. 准备访问top结点的右子树. struct Tre

  • 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

  • Java 归并排序算法、堆排序算法实例详解

    Java 归并排序算法、堆排序算法实例详解

    基本思想: 归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序示例: 合并方法: 设r[i-n]由两个有序子表r[i-m]和r[m+1-n]组成,两个子表长度分别为n-i +1.n-m. j=m+1:k=i:i=i; //置两个子表的起始下标及辅助数组的起始下标 若i>m 或j>n,转⑷ //其中一个子表已合并完,比较选取结束 //选取r[i]和r[j]较小的存入辅助数组

  • JavaScript算法系列之快速排序（Quicksort）算法实例详解

    JavaScript算法系列之快速排序（Quicksort）算法实例详解

    "快速排序"的思想很简单,整个排序过程只需要三步: (1)在数据集之中,选择一个元素作为"基准"(pivot). (2)所有小于"基准"的元素,都移到"基准"的左边:所有大于"基准"的元素,都移到"基准"的右边. (3)对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止. 举例来说,现在有一个数据集{85, 24, 63, 45,

  • KnockoutJS数组比较算法实例详解

    这篇文章主要介绍了KnockoutJS数组比较算法实例详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 前端开发中,数组是一种非常有用的数据结构.这篇博客会解释并分析KnockoutJS实现中使用的数据比较算法. 算法的目的 KnockoutJS使用MVVM的思想,view model中的数组元素会对应data model中的数组数据,当用户进行输入或者请求后台时,数组数据会发生变更, 从而带动UI的更新.例如购物车类的页面,用户可以通过点击

  • java 中模式匹配算法-KMP算法实例详解

    java 中模式匹配算法-KMP算法实例详解

    java 中模式匹配算法-KMP算法实例详解 朴素模式匹配算法的最大问题就是太低效了.于是三位前辈发表了一种KMP算法,其中三个字母分别是这三个人名的首字母大写. 简单的说,KMP算法的对于主串的当前位置不回溯.也就是说,如果主串某次比较时,当前下标为i,i之前的字符和子串对应的字符匹配,那么不要再像朴素算法那样将主串的下标回溯,比如主串为"abcababcabcabcabcabc",子串为"abcabx".第一次匹配的时候,主串1,2,3,4,5字符都和子串相应的

随机推荐