专栏首页算法channel二叉树非递归版的后序遍历算法

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

本公众号主要推送关于对算法的思考以及应用的消息。算法思想说来有,分而治之,搜索,动态规划,回溯,贪心等,结合这些思想再去思考如今很火的大数据,云计算和机器学习,是不是也别有一番风味呢? 在这个征程中,免不了读英文博客,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),作者:alg-flody

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 跨越时空:找回 RNN 消失的梯度

    斯坦福 NLP 的第 9 课后半部分给出了答案:主要应对梯度消失的措施是隐含层中采用更复杂的隐含单元。读者朋友们,你们可以回想下 RNN 的网络结果,隐含层中,...

    double
  • 大白话总结著名的 word2vec

    本文作者:Alicia , 现在美国名校读博士后,从事 AI 研究及教学工作,拥有 10 年以上工作与科研经历。

    double
  • 二叉树非递归版的中序遍历算法

    本公众号主要推送关于对算法的思考以及应用的消息。算法思想说来有,分而治之,搜索,动态规划,回溯,贪心等,结合这些思想再去思考如今很火的大数据,云计算和机器学习,...

    double
  • 网络拓扑结构-网络图的凝聚性特征和R计算

    前述网络基础概述中提到,在数学中,“网络”(networks)通常被称为“图”(graphs),一个图G=(V,E)是一种包含“节点”集合V与“边”集合E的数学...

    用户7585161
  • Data Structure前情提要——二叉树红黑树

    叶子节点就是左右孩子都是空的,但是并不是每一颗树都像上图所示的那样这么规整,有些树树可以只有左孩子没有右孩子的。二叉树的节点一定会大于左节点的值小于右节点的值,...

    西红柿炒鸡蛋
  • 30个示例手把手教你学会Xpath高级用法

    xpath速度比较快,是爬虫在网页定位中的较优选择,但是很多网页前端代码混乱难以定位,而学习定位也较为不易(主要是全面的教程较少),这里列出一点编程过程中可能...

    小小科
  • 数据结构与算法(十二) 红黑树

    •节点是有颜色的Red/Black•根节点必须是Black•叶子节点必须是Black•红黑树的叶子节点会自动将度为0 或者度为1的节点的度自动补充为2,补充的节...

    老沙
  • Akka 指南 之「集群规范」

    Akka 集群(Cluster)提供了一种容错的、分散的、基于点对点(peer-to-peer)的集群成员(membership)服务,不存在单点故障或单点瓶颈...

    CG国斌
  • 前端学数据结构与算法(六):二叉树的四种遍历方式及其应用

    上一章我们从0到1的实现了一颗二叉搜索树,以及理解了二叉搜索树的特性与基本操作,这一章介绍关于二叉树的更多操作,也就是树的遍历。主要包括前序遍历、中序遍历、后序...

    飞跃疯人院
  • 女巫攻击及其防范

    之前的文章在讲拜赞庭容错的时候,我们提到了女巫攻击Sybil Attack。那什么是女巫攻击呢?

    程序那些事

扫码关注云+社区

领取腾讯云代金券