原文发表于: http://coderbee.net/index.php/algorithm/20130618/231
题
写出一个O(n)时间的非递归过程,输出给定的含n个节点的二叉树中每个结点的关键字,要求只能使用除树本身以外固定量的额外存储空间,而且在过程中不能修改该树,哪怕只是暂时的。
题目来自《算法导论》的一道习题。
树的遍历方式分类
从树的深度分类
树的遍历可以分为广度优先和深度优先两种形式。
- 广度优先,就是先输出父结点,再输出子结点。一般借助于(FIFO)队列。
- 深度优先,就是先输出子结点,再输出父结点。一般需要借助(LIFO)栈结构,如果不使用栈数据结构,一般就需要借用运行时的方法调用栈。
从树的节点的先后顺序分类
树的遍历可以分为先根遍历、中序遍历、后序遍历。前中后是以父节点在遍历中的顺序为根据的。
- 先根遍历:先遍历根,再遍历左子树,最后遍历右子树。
- 中序遍历:先遍历左子树,再遍历根,最后遍历右子树。
- 后序遍历:先遍历左子树,再遍历右子树,最后遍历根。
分析
由于只能使用固定量的额外存储空间,所以,没法构建队列或栈来进行遍历 或 用变量标记哪些结点是已输出的。由于不能修改树,也没法在树上做标记。所以,结点是否已输出只能在遍历过程中判断,也就需要遍历的算法能够区分出已输出和未输出的。
如果采用广度优先的方式,先输出父结点后,由于没有足够的空间来存储对子树的引用,树可以说是变为两棵独立的树,这个方式应该是不可行的。
如果采用深度优先的方式,以中序遍历为例,总是按左子树、父结点、右子树的顺序遍历,那么当右子树遍历完后,说明父结点及其所有子树都遍历完成了,可以这样往上处理父结点的父结点。而判断右子树是否遍历完成可以通过:当前遍历完成的结点是否是父结点的右结点来完成。这种方法是可行的。
当结点p及其子树都遍历完成后,需要向上查找第一个未遍历的右子树(parent = p.parent
):
-
p == parent.rChild
,当前遍历是子树是右子树,需要继续往上查找; - 否则,p是parent的左孩子,先输出parent;如果parent有右孩子,需要进行遍历;如果parent没有右孩子,需要继续往上查找。
实现
核心是 midOrderIterate 函数。
class Node { Node parent; Node lChild; Node rChild; int key; public Node(int key) { this.key = key; } } public class BinaryTree { public static Node build(int[] keys) { Node root = null; for (int key : keys) { Node node = new Node(key); if (root == null) { root = node; } else { insertNode(root, node); } } return root; } public static void insertNode(Node parent, Node node) { if (node.key < parent.key) { if (parent.lChild == null) { parent.lChild = node; node.parent = parent; } else { insertNode(parent.lChild, node); } } else { if (parent.rChild == null) { parent.rChild = node; node.parent = parent; } else { insertNode(parent.rChild, node); } } } public static List<Integer> midOrderIterate(Node root) { List<Integer> list = new LinkedList<Integer>(); if (root == null) { return list; } Node p = root; Node parent = null; outer: while (true) { if (p.lChild != null) { p = p.lChild; // 先处理左子树。 } else if (p.rChild != null) { // 没有左子树,但有右子树,先处理了自身节点,再处理右子树 list.add(p.key); p = p.rChild; } else { list.add(p.key); // 叶子节点 while (true) { // 处理叶子节点后需要往上查找,查找第一个右结点未处理的结点。 parent = p.parent; if (parent == null) { // 根结点 break outer; } if (parent.rChild == p) { // 当前结点是父结点的右结点,说明父结点及以下的整棵子树已处理,继续往上查找。 p = parent; } else { // 当前结点是父结点的左结点 list.add(parent.key); // 先处理了父结点 if(parent.rChild != null) { // parent有右孩子,则parent.rChild肯定是未遍历的。 p = parent.rChild; break; } else { // 父结点没有右子树,说明父结点及以下的整棵子树已处理,继续往上查找。 p = parent; } } } } } return list; } public static void main(String[] args) { int[][] keys = new int[][] { new int[] { 4 }, new int[] { 4, 5, 6, 7, 8, 9, }, new int[] { 8, 7, 6, 5, 4, 3 }, new int[] { 8, 4, 9, 2, 5, 10, 1, 3, 6, 7 }, new int[] { 8, 4, 13, 2, 5, 12, 14, 1, 3, 6, 11, 10, 9 }, new int[] { 8, 7, 15, 12, 17, 16 }, }; for (int[] key : keys) { Node root = BinaryTree.build(key); Arrays.sort(key); array = testMidOrderIterate(root); eq = isEq(array, key); System.out.println("testMidOrderIterate() isOk: " + eq); } } public static Integer[] testMidOrderIterate(Node root) { List<Integer> list = BinaryTree.midOrderIterate(root); return list.toArray(new Integer[] {}); } public static Integer[] testIterate(Node root) { List<Integer> list = BinaryTree.iterate(root); Collections.sort(list); return list.toArray(new Integer[] {}); } public static boolean isEq(Integer[] array, int[] key) { if (array.length == key.length) { for (int i = 0; i < array.length; i++) { if (array[i].intValue() != key[i]) { return false; } } } else { return false; } return true; } }
相关推荐
遍历二叉树有多种方法,其中前序、中序和后序遍历是最常见的三种。通常,这些遍历算法是以递归方式实现的,但递归虽然简洁,却可能带来栈溢出的问题,尤其是在处理大规模数据时。因此,了解和掌握二叉树的非递归遍历...
为了解决这个问题,可以采用非递归的方式,使用栈显式存储中间状态,但这会使得代码更加复杂。 在实际应用中,递归中序遍历广泛应用于各种场景,如数据库索引的构建、编译器中的语法分析树的处理等,特别是在需要...
本篇文章将深入探讨二叉树三种主要遍历方式(前序、中序、后序)的非递归算法实现,力求让读者能够清晰地理解和掌握这些算法,并在实践中加以应用。 **前序遍历**是二叉树遍历的一种基本形式,其遍历顺序是先访问根...
### 二叉树遍历的非递归算法分析与实现 #### 一、引言 在数据结构领域中,二叉树作为一种基本的数据组织形式,其应用极为广泛。对于二叉树的操作,其中最重要的就是遍历操作。遍历是指按照特定顺序访问二叉树的...
二叉树遍历是计算机科学中的一个重要概念,主要应用于数据结构和算法领域。二叉树是一种特殊的树形...非递归算法则更注重空间效率,层次遍历使用队列,Morris遍历则不需额外空间。掌握这些方法对提升编程技能大有裨益。
在递归方法之外,利用栈这种数据结构也可以实现非递归遍历,这种方法在某些情况下更加高效,避免了递归带来的系统栈空间的开销。 **前序遍历**(根-左-右):首先访问根节点,然后遍历左子树,最后遍历右子树。非...
本文将深入探讨二叉树的前序、中序、后序遍历的递归和非递归算法。 1. **前序遍历**: - **递归算法**:首先访问根节点,然后递归地对左子树进行前序遍历,最后对右子树进行前序遍历。伪代码如下: ``` function...
本实验报告关注的是如何在C++环境中通过递归和非递归方法遍历二叉树,以及计算二叉树中叶子节点的数量。 **1. 二叉树的存储方式** 二叉树通常使用二叉链表存储结构进行存储。这种结构包含每个节点的数据域和两个...
非递归中序遍历的一个优点是避免了递归调用带来的额外开销,适用于处理深度较大的树结构。同时,由于控制权始终在主循环中,因此更容易理解和调试。不过,非递归实现可能需要更多的内存空间来存储栈中的节点。在实际...
遍历二叉树是二叉树操作中最基本的操作之一,它按照某种顺序访问二叉树中的每一个节点,确保每个节点仅被访问一次。二叉树的遍历有三种基本的方式:前序遍历、中序遍历和后序遍历。后序遍历由于其特殊的访问顺序,在...
中序遍历有三种主要的实现方式:递归、栈辅助的非递归(迭代)以及 Morris遍历。每种方法都有其特点和适用场景。 1. **递归**: - **基本思想**:从根节点开始,首先递归地遍历左子树,然后访问根节点,最后递归地...
线索化是为了方便非递归遍历,它通过在二叉链表的指针域中额外存储信息,使得在任意时刻都可以通过线索找到前驱或后继节点。线索化的二叉树有两种类型: 1. **前驱线索化(Predecessor Threading)**,在每个节点的...
- **线索二叉树的应用**:线索化二叉树主要用于非递归的中序遍历和后序遍历,因为这些遍历在非线索化的二叉树中通常需要栈或队列。 总结,二叉树是数据结构的基础,理解其初始化、销毁和遍历方法对于学习其他高级...
此外,非递归遍历的优点还包括避免了递归带来的额外开销,如函数调用的系统开销和栈空间的消耗。这种方法对于理解和实现二叉树算法具有重要的实践意义,因为它提供了一种更加灵活和资源效率高的解决方案。在实际的...
在实际应用中,遍历二叉树可以用于查找、排序、复制和打印树等任务。例如,在编译器中,中序遍历常用于语法分析;而在构建平衡树(如AVL树、红黑树)时,遍历则用于维护树的平衡。 压缩包中的“二叉树的遍历.docx”...
后序遍历的非递归实现相对复杂,通常需要额外的信息来记录节点是否被访问过。一种常用的方法是使用两个栈,先用栈1按前序遍历的逆序压入所有节点,然后再用栈2反转这些节点的顺序输出。 #### 七、总结 二叉树的遍历...
- **非递归**:空间效率较高,不会因递归深度限制遍历大型树,但实现相对复杂,需要维护额外的数据结构。 了解和熟练掌握二叉树的建立与遍历是成为优秀程序员的基础,这不仅有助于解决实际问题,也有助于深入理解...
然而,这种递归方法的缺点在于它需要大量的临时存储空间,特别是在处理大规模问题时。 #### 三、非递归算法的创新设计 为克服递归算法的局限,贺存薪等人提出了一种基于二叉树数据结构的非递归算法。不同于传统...
- **遍历算法**:实现二叉树的中序、前序、后序遍历(包括递归和非递归版本)。 - **子树交换**:实现二叉树子树之间的交换操作。 - **层次遍历**:实现按层遍历算法。 - **中序线索化**:实现二叉树的中序线索化,...
5. **计算叶子节点和结点数目**:遍历二叉树,对每个节点进行计数。叶子节点是没有任何子节点的节点。结点总数等于所有节点的数量,包括叶子节点和非叶子节点。 6. **二叉树查找**:从根节点开始,根据节点值的比较...