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

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

本公众号主要推送关于对算法的思考以及应用的消息。算法思想说来有,分而治之,搜索,动态规划,回溯,贪心等,结合这些思想再去思考如今很火的大数据,云计算和机器学习,是不是也别有一番风味呢? 在平凡之路上,开发者不免要读英语文献,推送英语能力提升消息。

01

你会学到什么?

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

读完后的收获:

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

02

讨论的问题是什么?

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

03

这个问题相关的概念和理论

  • 遍历

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

  • 二叉树组成

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

  • 中序遍历

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

04

非递归版中序遍历算法

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

我们先看下二叉树的节点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; } }

代码思考

中序遍历,首先遍历左子树,根节点,最后右子树,这里的顺序性,我们借助栈 First In Last Out 的数据结构,算法的思路:

  1. 参数root (TreeNode<T>) 如果是空引用,直接返回;
  2. 初始化栈,并把root节点Push到栈 s
  3. 遍历(条件为栈s内有元素)
  4. 找最左的节点同时,将左子树的左节点依次Push到栈s。这里有两种情况,第一种是一上来就满足while条件,即满足 while(context!=null) ,当退出循环时,context.left必等于null,也就是s栈顶必为null元素;第二种,不满足while条件(可能发生在某次遍历),这个栈内的null元素就是算法对每个叶子节点虚拟出的另一个子右节点null
  5. s.pop,此处出栈元素必为null
  6. s.Count为0,则直接返回。这种情况可能发生在根节点只有左子树,没有右子树的情况,见下方的快照图
  7. 访问栈顶元素TopNode(相对于栈顶元素的后面一个元素NextNode而言,此节点为其左节点)
  8. Pop掉这个节点TopNode
  9. 此时栈顶元素为NextNode,其右节点Push到s,到此完成一次遍历
  10. 重复3~9,直到不满足3的遍历条件时退出。也就说在一次遍历过程中,可能发生一次或多次Push,Pop操作除了最后一次遍历外,其余都是两次Pop。

算法技巧

算法对每个叶子节点虚拟出另一个子右节点,具体对应步骤9。

public IList<T> InorderTraversal<T>(TreeNode<T> root) { IList<T> rtn = new List<T>(); //1 if (root == null) return rtn; //2 var s = new Stack<TreeNode<T>>(); s.Push(root); while (s.Count > 0) //3 { //4 var context = s.Peek(); while (context != null) { s.Push(context.left); context = context.left; } s.Pop();//5 //6 if (s.Count == 0) return rtn; rtn.Add(s.Peek().val); //7 TreeNode<T> curNode = s.Pop(); //8 s.Push(curNode.right);//9 } return rtn; }

快照

如下图所示,中序遍历已经访问完了节点5,此时栈s内的元素为null和3,

下一个要访问的元素是节点3,是如何访问的呢?重复步骤3~9。此时的栈顶为null,不满足步骤4的条件,执行步骤5出栈null元素,不满足步骤6的条件,执行步骤7访问此时的栈顶即节点3,执行步骤8即出栈元素3,执行步骤9将右子节点(虚拟出的null如上图所示)入栈s,结果如下图所示,

到此所有的节点都访问一遍,访问的顺序: 2->4->1->5->3。但是程序还会再遍历一次,因为此时的栈不为空(含有null)。

执行步骤10即执行下一次遍历,此时栈s含有一个元素null,执行步骤4拿到栈顶元素并且不满足while条件,执行步骤5,结果栈内元素变空,满足了步骤6的条件,

if (s.Count == 0)

return rtn;

,直接返回,如下图所示,

05

评价算法

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

06

总结

讨论了二叉树的非递归版中序遍历算法,算法借助栈,巧妙地对每个叶子节点虚拟出一个子右节点,按照左子树,根节点,右子树的遍历次序访问整棵树,时间和空间复杂度都为 O(n)。

本文分享自微信公众号 - 算法channel(alg-channel),作者:jackguo

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

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

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

    double
  • 大白话总结著名的 word2vec

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

    double
  • 二叉树的基础---四种遍历方式的 Java 实现

    大家好,我是多选参数的程序锅,一个正在“研究”操作系统、学数据结构和算法以及 Java 的硬核菜鸡。本篇将带来的是二叉树的相关知识,知识提纲如图所示。

    syy
  • 深入理解二叉树的特点

    在计算机科学中,二叉树(Binary tree)是一个连通的无环图,每个节点最多只有两个分支(即不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”或“...

    我是攻城师
  • 每天一算:二叉树的层次遍历

    五分钟学算法
  • 详解算法之重建二叉树

    从今天开始,公众号陆陆续续开始插写用动画形式展现算法题,如剑指offer、Leedcode里经典面试题型,同时也会更新数据结构与算法基础、网络原理等知识。

    帅地
  • 二叉树的重建

    在http://blog.csdn.net/hacker_zhidian/article/details/60586445这篇文章中我们看了一下二叉树的四种遍历...

    指点
  • 算法 | 广度优先遍历BFS

    BFS算法,也称作广度优先搜索算法。是一种图形搜索演算法。简单的说,BFS是从根节点开始,沿着树的宽度遍历树的节点,如果发现目标,则演算终止。(百度百科)

    算法与编程之美
  • LeetCode | 104.二叉树的最大深度

    这次来写一下 LeetCode 的第 104 题,二叉树的最大深度。

    码农UP2U

扫码关注云+社区

领取腾讯云代金券