`
wen866595
  • 浏览: 269388 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

非递归、固定量额外存储空间 遍历二叉树

阅读更多

原文发表于: 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;
     }
}

 

 

2
3
分享到:
评论

相关推荐

    二叉树前序、中序、后序三种遍历的非递归算法(C语言)

    遍历二叉树有多种方法,其中前序、中序和后序遍历是最常见的三种。通常,这些遍历算法是以递归方式实现的,但递归虽然简洁,却可能带来栈溢出的问题,尤其是在处理大规模数据时。因此,了解和掌握二叉树的非递归遍历...

    用递归中序遍历二叉树

    为了解决这个问题,可以采用非递归的方式,使用栈显式存储中间状态,但这会使得代码更加复杂。 在实际应用中,递归中序遍历广泛应用于各种场景,如数据库索引的构建、编译器中的语法分析树的处理等,特别是在需要...

    数据结构 二叉树三种遍历的非递归算法(背诵版).doc

    本篇文章将深入探讨二叉树三种主要遍历方式(前序、中序、后序)的非递归算法实现,力求让读者能够清晰地理解和掌握这些算法,并在实践中加以应用。 **前序遍历**是二叉树遍历的一种基本形式,其遍历顺序是先访问根...

    二叉树遍历的非递归算法分析与实现

    ### 二叉树遍历的非递归算法分析与实现 #### 一、引言 在数据结构领域中,二叉树作为一种基本的数据组织形式,其应用极为广泛。对于二叉树的操作,其中最重要的就是遍历操作。遍历是指按照特定顺序访问二叉树的...

    二叉树的遍历的算法:递归与非递归

    二叉树遍历是计算机科学中的一个重要概念,主要应用于数据结构和算法领域。二叉树是一种特殊的树形...非递归算法则更注重空间效率,层次遍历使用队列,Morris遍历则不需额外空间。掌握这些方法对提升编程技能大有裨益。

    二叉树的三种非递归遍历

    在递归方法之外,利用栈这种数据结构也可以实现非递归遍历,这种方法在某些情况下更加高效,避免了递归带来的系统栈空间的开销。 **前序遍历**(根-左-右):首先访问根节点,然后遍历左子树,最后遍历右子树。非...

    二叉树的基本操作,包括前序、中序、后序遍历的递归和非递归算法

    本文将深入探讨二叉树的前序、中序、后序遍历的递归和非递归算法。 1. **前序遍历**: - **递归算法**:首先访问根节点,然后递归地对左子树进行前序遍历,最后对右子树进行前序遍历。伪代码如下: ``` function...

    递归和非递归二叉树

    本实验报告关注的是如何在C++环境中通过递归和非递归方法遍历二叉树,以及计算二叉树中叶子节点的数量。 **1. 二叉树的存储方式** 二叉树通常使用二叉链表存储结构进行存储。这种结构包含每个节点的数据域和两个...

    C语言数据结构中序遍历的非递归算法

    非递归中序遍历的一个优点是避免了递归调用带来的额外开销,适用于处理深度较大的树结构。同时,由于控制权始终在主循环中,因此更容易理解和调试。不过,非递归实现可能需要更多的内存空间来存储栈中的节点。在实际...

    二叉树的后序遍历非递归算法.doc

    遍历二叉树是二叉树操作中最基本的操作之一,它按照某种顺序访问二叉树中的每一个节点,确保每个节点仅被访问一次。二叉树的遍历有三种基本的方式:前序遍历、中序遍历和后序遍历。后序遍历由于其特殊的访问顺序,在...

    二叉树的中序遍历

    中序遍历有三种主要的实现方式:递归、栈辅助的非递归(迭代)以及 Morris遍历。每种方法都有其特点和适用场景。 1. **递归**: - **基本思想**:从根节点开始,首先递归地遍历左子树,然后访问根节点,最后递归地...

    二叉树的遍历及线索化

    线索化是为了方便非递归遍历,它通过在二叉链表的指针域中额外存储信息,使得在任意时刻都可以通过线索找到前驱或后继节点。线索化的二叉树有两种类型: 1. **前驱线索化(Predecessor Threading)**,在每个节点的...

    二叉树 线索华二叉树 递归非递归的实现

    - **线索二叉树的应用**:线索化二叉树主要用于非递归的中序遍历和后序遍历,因为这些遍历在非线索化的二叉树中通常需要栈或队列。 总结,二叉树是数据结构的基础,理解其初始化、销毁和遍历方法对于学习其他高级...

    Two-fork-tree-storage.zip_二叉树_遍历算法

    此外,非递归遍历的优点还包括避免了递归带来的额外开销,如函数调用的系统开销和栈空间的消耗。这种方法对于理解和实现二叉树算法具有重要的实践意义,因为它提供了一种更加灵活和资源效率高的解决方案。在实际的...

    二叉树的遍历代码.rar

    在实际应用中,遍历二叉树可以用于查找、排序、复制和打印树等任务。例如,在编译器中,中序遍历常用于语法分析;而在构建平衡树(如AVL树、红黑树)时,遍历则用于维护树的平衡。 压缩包中的“二叉树的遍历.docx”...

    c语言数据结构二叉树的遍历

    后序遍历的非递归实现相对复杂,通常需要额外的信息来记录节点是否被访问过。一种常用的方法是使用两个栈,先用栈1按前序遍历的逆序压入所有节点,然后再用栈2反转这些节点的顺序输出。 #### 七、总结 二叉树的遍历...

    二叉树的建立与遍历

    - **非递归**:空间效率较高,不会因递归深度限制遍历大型树,但实现相对复杂,需要维护额外的数据结构。 了解和熟练掌握二叉树的建立与遍历是成为优秀程序员的基础,这不仅有助于解决实际问题,也有助于深入理解...

    Hanoi塔问题的一种非递归算法

    然而,这种递归方法的缺点在于它需要大量的临时存储空间,特别是在处理大规模问题时。 #### 三、非递归算法的创新设计 为克服递归算法的局限,贺存薪等人提出了一种基于二叉树数据结构的非递归算法。不同于传统...

    数据结构二叉树遍历实验报告.doc

    - **遍历算法**:实现二叉树的中序、前序、后序遍历(包括递归和非递归版本)。 - **子树交换**:实现二叉树子树之间的交换操作。 - **层次遍历**:实现按层遍历算法。 - **中序线索化**:实现二叉树的中序线索化,...

    链式存储二叉树基本操作函数.rar

    5. **计算叶子节点和结点数目**:遍历二叉树,对每个节点进行计数。叶子节点是没有任何子节点的节点。结点总数等于所有节点的数量,包括叶子节点和非叶子节点。 6. **二叉树查找**:从根节点开始,根据节点值的比较...

Global site tag (gtag.js) - Google Analytics