本公众号主要推送关于对算法的思考以及应用的消息。算法思想说来有,分而治之,搜索,动态规划,回溯,贪心等,结合这些思想再去思考如今很火的大数据,云计算和机器学习,是不是也别有一番风味呢? 在平凡之路上,开发者不免要读英语文献,推送英语能力提升消息。
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 的数据结构,算法的思路:
算法技巧
算法对每个叶子节点虚拟出另一个子右节点,具体对应步骤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)。
本文分享自 程序员郭震zhenguo 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!