专栏名称: OSC开源社区

OSChina 开源中国官方微信账号

二叉树深度遍历的非递归算法分析及 Java 实现

OSC开源社区 · 公众号 · 程序员 · 2017-03-09 08:37

正文

＃点击图片，报名深圳源创会＃

前言

二叉树的前序中序后序三种遍历方法，用递归实现较为容易，在上数据结构的课时，非递归实现会了，但过了一段时间又忘了，每次要写非递归实现的时候都要想好久。这里总结一下，将前序和后序遍历非递归实现方法统一，便于理解记忆！

二叉树DFS非递归实现

DFS 分析

depth first search:先访问子节点，再访问父节点，最后访问第二个子节点。根据根节点相对于左右子节点的访问先后顺序又可细分为以下三种方式（如图）:

● 前序(pre-order)：先根后左再右

● 中序(in-order)：先左后根再右

● 后序(post-order)：先左后右再根

在这里输入图片标题

DFS 非递归实现

前序和后序遍历

前序遍历和后序遍历归为一类,所用思想基本一模一样:

前序遍历的步骤为

● 对root进行异常处理

● 将root压入栈

● while循环遍历,终止条件为栈为空，所有元素均已处理完

● 从栈顶取元素读,取并存入结果

● 将取出元素的右、左节点分别压入栈内，以便下次循环取元素时为本次节点的左,右子节点

运用辅助栈,保存遍历到的节点(用栈后入先出的特性,控制已经遍历到的节点的访问顺序). 以前序深度优先遍历为例,先访问根节点,然后访问左树,左树全部访问完了,再访问右树

后续遍历思想: 左-右-根;可以视为, 根-右-左,然后结果转置即可. 如前面示意图,根右左,访问顺序则为:ACFBED;可以看出,这样访问刚好为后续遍历的转置. 根右左访问与前序(根左右)遍历操作思想一模一样。

前序遍历

● leetcode|Binary Tree Preorder Traversal二叉树前序遍历

https://leetcode.com/problems/binary-tree-preorder-traversal/

●lintcode|Binary Tree Preorder Traversal二叉树前序遍历

http://www.lintcode.com/en/problem/binary-tree-preorder-traversal/

后序遍历

● leetcode|Binary Tree Postorder Traversal 后序遍历

中序遍历

● 中序遍历思路: 中序遍历迭代法思路不同于前序和后序。

● 首先针对对当前节点,一直对其左子树迭代并将非空节点入栈

● 节点指针迭代为空(到树底了)后不再入栈,然后取栈顶元素,存结果;

● 将当前指针用出栈的节点的右子节点替代,然后回到第一步继续迭代,直到当前节点为空且栈为空.

● |leetcodeBinary Tree Inorder Traversal中序遍历

推荐文章

OSC开源社区 · KaiwuDB 2024：发布2.0版本、benchANT时序榜排名第一

4 天前

码农翻身 · 我用1小时AI神器，骗过了整个技术团队

5 天前

OSC开源社区 · 罗永浩AI创业项目J1 Assistant首次亮相：智能助理软件、UI“梦回”锤子手机，“闪念胶囊”的AI版本？

1 周前

OSC开源社区 · LFOSSA感谢信：2024年回顾与2025年展望

6 天前

程序员小灰 · 75k，确实可以封神了！

6 天前

咪蒙 · 你看老板是傻逼，老板看你亦如是

8 年前

半导体行业观察 · 震惊，苹果或因iPhone走向衰落

8 年前

广东公共DV现场 · 一种野菜治一种病！年轻十岁！一定要发出来给大家看看~

7 年前

大宗内参 · 特朗普深陷就职以来最大危机美联储6月加息概率骤降众所周知

7 年前

浙江市场监管矩阵 · 注册热情空前高涨！浙江这个地区每3.5个老板中就有一人持有商标

7 年前