内容简介:各位读者周末愉快呀,今天我想来说说一道很常见的面试题目 —— 关于二叉树前中后序遍历的实现。本文将以递归和非递归方式实现这 3 种遍历方式,代码都比较短,可以放心食用。先简单说明一下这 3 种遍历方式有什么不同 —— 对于每种遍历,树中每个结点都需要经过 3 次(对于叶结点,其左右子树视为空子树),但所以前中后序遍历访问结点的顺序分别是中左右、左中右、左右中。「中」表示当前结点,「左右」表示当前结点的左右子树。
各位读者周末愉快呀,今天我想来说说一道很常见的面试题目 —— 关于二叉树前中后序遍历的实现。本文将以递归和非递归方式实现这 3 种遍历方式,代码都比较短,可以放心食用。
先简单说明一下这 3 种遍历方式有什么不同 —— 对于每种遍历,树中每个结点都需要经过 3 次(对于叶结点,其左右子树视为空子树),但 前序遍历在第一次遇到结点时就立即访问,中序遍历是在第二次遇到结点时访问,后序遍历则是第三次访问。
所以前中后序遍历访问结点的顺序分别是中左右、左中右、左右中。「中」表示当前结点,「左右」表示当前结点的左右子树。
下面让我们一起来看下代码是怎么实现的吧。
递归版
前序遍历
public static void preOrderRecur(Node head) { if (head == null) { return; } System.out.print(head.value + " "); preOrderRecur(head.left); preOrderRecur(head.right); } 复制代码
中序遍历
public static void inOrderRecur(Node head) { if (head == null) { return; } inOrderRecur(head.left); System.out.print(head.value + " "); inOrderRecur(head.right); } 复制代码
后序遍历
public static void posOrderRecur(Node head) { if (head == null) { return; } posOrderRecur(head.left); posOrderRecur(head.right); System.out.print(head.value + " "); } 复制代码
非递归版
前序遍历
public static void preOrderUnRecur(Node head) { if (head != null) { Stack<Node> stack = new Stack<Node>(); stack.add(head); while (!stack.isEmpty()) { head = stack.pop(); System.out.print(head.value + " "); if (head.right != null) { stack.push(head.right); } if (head.left != null) { stack.push(head.left); } } } } 复制代码
中序遍历
public static void inOrderUnRecur(Node head) { if (head != null) { Stack<Node> stack = new Stack<Node>(); while (!stack.isEmpty() || head != null) { if (head != null) { stack.push(head); head = head.left; } else { head = stack.pop(); System.out.print(head.value + " "); head = head.right; } } } } 复制代码
后序遍历
public static void posOrderUnRecur(Node head) { if (head != null) { Stack<Node> s1 = new Stack<Node>(); Stack<Node> s2 = new Stack<Node>(); s1.push(head); while (!s1.isEmpty()) { head = s1.pop(); s2.push(head); if (head.left != null) { s1.push(head.left); } if (head.right != null) { s1.push(head.right); } } while (!s2.isEmpty()) { System.out.print(s2.pop().value + " "); } } } 复制代码
以上就是二叉树的 3 种遍历方式,你学会了吗?
PS:本文原创发布于微信公众号「不只Java」,后台回复「Java」,送你 13 本 Java 经典电子书。公众号专注分享 Java 干货、读书笔记、成长思考。
以上所述就是小编给大家介绍的《二叉树的前中后序遍历(递归和非递归版本)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 数组常见的遍历循环方法、数组的循环遍历的效率对比
- C++拾趣——STL容器的插入、删除、遍历和查找操作性能对比(Windows VirtualStudio)——遍历和删除
- Js遍历数组总结
- 遍历
- 遍历 DOM 注意点
- MySQL 实现树形的遍历
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
构建高可用Linux服务器
余洪春 / 机械工业出版社华章公司 / 2011-11-1 / 79.00元
资深Linux/Unix系统管理专家兼架构师多年一线工作经验结晶,51CTO和ChinaUnix等知名社区联袂推荐。结合实际生产环境,从Linux虚拟化、集群、服务器故障诊断与排除、系统安全性等多角度阐述构建高可用Linux服务器的最佳实践。本书实践性非常强,包含大量企业级的应用案例及相应的解决方案,读者可以直接用这些方案解决在实际工作中遇到的问题。 全书一共10章。第1章以作者的项目实践为......一起来看看 《构建高可用Linux服务器》 这本书的介绍吧!