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

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

写出一个O(n)时间的非递归过程,输出给定的含n个节点的二叉树中每个结点的关键字,要求只能使用除树本身以外固定量的额外存储空间,而且在过程中不能修改该树,哪怕只是暂时的。

树的遍历方式分类

从树的深度分类

树的遍历可以分为广度优先和深度优先两种形式。

  • 广度优先,就是先输出父结点,再输出子结点。一般借助于(FIFO)队列。
  • 深度优先,就是先输出子结点,再输出父结点。一般需要借助(LIFO)栈结构,如果不使用栈数据结构,一般就需要借用运行时的方法调用栈。

从树的节点的先后顺序分类

树的遍历可以分为先根遍历、中序遍历、后序遍历。前中后是以父节点在遍历中的顺序为根据的。

  • 先根遍历:先遍历根,再遍历左子树,最后遍历右子树。
  • 中序遍历:先遍历左子树,再遍历根,最后遍历右子树。
  • 后序遍历:先遍历左子树,再遍历右子树,最后遍历根。

分析

由于只能使用固定量的额外存储空间,所以,没法构建队列或栈来进行遍历 或 用变量标记哪些结点是已输出的。由于不能修改树,也没法在树上做标记。所以,结点是否已输出只能在遍历过程中判断,也就需要遍历的算法能够区分出已输出和未输出的。

如果采用广度优先的方式,先输出父结点后,由于没有足够的空间来存储对子树的引用,树可以说是变为两棵独立的树,这个方式应该是不可行的。

如果采用深度优先的方式,以中序遍历为例,总是按左子树、父结点、右子树的顺序遍历,那么当右子树遍历完后,说明父结点及其所有子树都遍历完成了,可以这样往上处理父结点的父结点。而判断右子树是否遍历完成可以通过:当前遍历完成的结点是否是父结点的右结点来完成。这种方法是可行的。

当结点p及其子树都遍历完成后,需要向上查找第一个未遍历的右子树(parent = p.parent):

  • p == parent.rChild,当前遍历是子树是右子树,需要继续往上查找;
  • 否则,p是parent的左孩子,先输出parent;如果parent有右孩子,需要进行遍历;如果parent没有右孩子,需要继续往上查找。

实现

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;
     }
}

 

 

 


欢迎关注我的微信公众号: coderbee笔记,可以更及时回复你的讨论。

非递归、固定量额外存储空间 遍历二叉树》上有3个想法

  1. 博主你好,我想请教下这个问题的复杂度是O(n)的证明。
    我觉得是否可以这样证明,考虑二叉树上的每条边。在查找未完成遍历的父亲时,每条边至多自底向上经过一次,当经过一条边时,说明该边下的子树已经完成遍历。故向上查找父节点的复杂度也是O(n)。

    • 重点不是复杂度的证明,而是非递归实现,有限的临时变量。
      n个节点,每个遍历一次,而且没有重复访问,就是O(n)了

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据