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

本公众号主要推送关于对算法的思考以及应用的消息。算法思想说来有,分而治之,搜索,动态规划,回溯,贪心等,结合这些思想再去思考如今很火的大数据,云计算和机器学习,是不是也别有一番风味呢? 在这个征程中,免不了读英文博客,paper,书籍等,提升英语阅读能力也至关重要呀,为了满足大家需要,本公众号也推送这方面的消息。

01—你会学到什么?

树的递归遍历算法很容易理解,代码也很精简,但是如果想要从本质上理解二叉树常用的三种遍历方法,还得要思考树的非递归遍历算法。

读完后的收获:

  • “”将学到二叉树的后序遍历的非递归版本
  • 明白栈这种数据结构该怎么使用

02—讨论的问题是什么?

主要讨论二叉树的非递归版后序遍历该如何实现,包括借助什么样的数据结构,迭代的构思过程等。

03—相关的概念和理论

  • 遍历

Traversal 指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。

  • 二叉树组成

二叉树由根结点及左、右子树这三个基本部分组成。

  • 后序遍历

Postorder Traversal 访问根结点的操作发生在遍历其左、右子树之后。

04—思考过程

后序遍历是从左子树,再到右子树,最后到根节点的遍历次序。如果借助栈来实现,我们自然想到先推入根节点,再推入右子树,最后推入左子树,然后出栈的顺序便是与推入顺序相反的。

那么这个问题,岂不是非常简单,是的,如果这棵树的左子树仅包括一个节点,右子树也仅仅包括一个节点,就像下图这样,

很显然,我们这样考虑树结构,思维是很局限的,我们要考虑的是节点2下还重复以上结构,节点3当然也是如此,每个节点都有可能重复这种结构,或仅有左右孩子之一,或都没有也就是叶子。

那么,如此递归结构,该如何思考写出非递归算法呢?

A 我们还是坚持从定义出发,不管一颗多么复杂的二叉树,在后序遍历中,一定先遍历的节点都位于节点2这一枝上,如图所示,所以我们会沿着2这一枝往下遍历,一直找,一直入栈,直到找到一个没有左孩子的节点,假设为节点2;

B 接下来要看下节点2有没有右孩子,如果没有,则表明节点2为叶子节点,直接访问这个节点2,然后出栈节点2;

C 如果节点2存在右孩子,如上图所示,那么我们该怎么办呢?我们把这个右孩子看成以其为根的子树,然后重复step A。如图所示,我们假设2下的右孩子是个叶子节点。分析这个过程,我们当然要入栈这个节点,然后观察到它没有左孩子,也没有右孩子,符合上文提到的step B;

D 这个节点出栈后,此时的栈顶元素为节点2,也就是我们下一个想要访问的元素,这是这个算法最难的地方,不是很容易能想到。

此处的访问条件不再是step B中的条件,而是刚才这个节点2的右孩子我们已经访问过了,所以该轮到其父节点2了。

需要用到一个指针存储着上一迭代的访问过的节点。

以上就是后序遍历非递归版的思路。

05—实现代码

这里我们以二叉树为例,讨论二叉树的后序遍历的非递归版实现。

我们先看下二叉树的节点TreeNode的数据结构定义。

节点的数据域的类型定义为泛型 T,含有左、右子树,及一个带有数据域的构造函数。

    public class TreeNode<T>
    {
        public T val { get; set; }
 
        public TreeNode<T> left { get; set; }
        public TreeNode<T> right { get; set; }
 
        public TreeNode(T data)
        {
            val = data;
        }
    }

二叉树的后序遍历的非递归版实现代码:

public static IList<T> PostorderTraversal<T>(TreeNode<T> root)
        {
            IList<T> rtn = new List<T>();
            var s = new Stack<TreeNode<T>>();
            if (root == null) return rtn;
            s.Push(root);
            TreeNode<T> cur = root;
            TreeNode<T> r = null; //标记访问过的右子树
            while (s.Count > 0)
            {
 //延伸到左子树
 if (cur != null && cur.left != null)
                {
                    s.Push(cur.left);
                    cur = cur.left;
                }
                else
                {
                    cur = s.Peek();
 //访问右子树的操作
                    if (cur.right != null && cur.right != r)
                    {
                        cur = cur.right;
                        s.Push(cur);
                    }
                    else //访问节点的操作
                    {
                 rtn.Add(s.Pop().val);
                        r = cur;
                        cur = null;
                    }
                }
            }
            return rtn;
        }

代码分析

代码中用到了两个非常重要的指针 cur,r 。

cur是每次迭代都会更新的指针,它没有非常明确的语义,它在某步迭代中可能是某个子树上的左节点抑或是右节点,也可能含义是标记着上一步迭代中访问到了一个叶子节点,此时需要从栈顶中拿值了。

r 的语义很明确,它是某次迭代过程中,如果发生了访问节点的操作,那么它指向这个访问过的节点,目的是为了判断是否向右子树展开,如下决定是否伸向向右子树的一个且条件的一部分。

也就是同时满足右子树不为空,并且右子树不等于上一迭代中的节点,然后才伸向右子树。

//访问右子树的操作 if (cur.right != null && cur.right != r) { cur = cur.right; s.Push(cur); }

05—算法评价

非递归版后序遍历算法的时间复杂度为 O(n),空间复杂度为栈所占的内存空间为 O(n)。

06—总结

讨论了二叉树的非递归版后序遍历算法,算法借助栈,相比于前序遍历和中序遍历,它多了一个指针指向上一迭代中访问过的节点,目的是为了判断是否向右子树展开,算法的时间和空间复杂度都为 O(n)。

原文发布于微信公众号 - 算法channel(alg-channel)

原文发表时间:2017-10-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏向治洪

HashMap原理解析

1. HashMap的数据结构 数据结构中有数组和链表来实现对数据的存储,但这两者基本上是两个极端。       数组 数组存储区间是连续的,占用内存严...

1959
来自专栏aCloudDeveloper

百炼OJ 2972 2973

一、2972相邻数字的基数等比:确定进制      所谓基数等比就是后一个数与前一个数有倍数的关系。如 111 = 1 + 1 * 2(1 + 2 * 1); ...

2398
来自专栏C语言及其他语言

【编程经验】关于链表、还有编译器

关注我们 最近有小白来问VC6.0和其他编译器怎么下,小编回了一些,但是也是确实比较多......所以今天就不单单分享知识了,还要分享资源! ...

30110
来自专栏JavaQ

HashMap死循环精简说

在JDK1.8之前的版本中,HashMap的底层实现是数组+链表。当调用HashMap的put方法添加元素时,如果新元素的hash值或key在原Map中不存在,...

1063
来自专栏于晓飞的专栏

Java 容器---实现

然而,之前在开发中使用仅仅是容器的一小部分。这次从源码的角度进行深入的理解,一点总结分享给大家。

1081
来自专栏专注 Java 基础分享

深入理解Java常用类-----时间日期

     除了String这个类在日常的项目中比较常用之外,有关时间和日期的操作也是经常遇到的,本篇就讲详细介绍下Java API中对时间和日期的支持。其实在J...

2588
来自专栏racaljk

[数据结构]C语言二叉树的实现

树和图是数据结构中比较麻烦的东西,里面涉及的概念比较多,也最有用, 就比如一般树广泛应用于人工智能的博弈上,而基于图的广度优先和深度优先搜索也广泛应用于人工智能...

3062
来自专栏算法channel

图解用栈数据结构对树的遍历

本公众号主要推送关于如何构思算法使之应用到我们的工作中。计算机常用算法思想大致来说有,分而治之,动态规划,贪心算法,搜索算法,回溯 ,训练这些思维的一个很好的平...

37311
来自专栏JavaEdge

Java8集合源码解析-Hashtable源码剖析1 概述2 源码解析rehash方法3 总结

2906
来自专栏Android机动车

Java 基础(五)——集合源码解析 Set

前面我们学了 List 集合。我们知道 List 是一个有序的集合,可以根据元素的整数索引访问元素,并且允许重复。

1021

扫码关注云+社区

领取腾讯云代金券