与父节点的二进制搜索树级别顺序

Question

嗨我试图打印出(node element, parent node element)格式的二进制搜索树的级别顺序。我目前使用队列来获得级别的顺序，但我很难得到父节点。是否有可能做队列？如果是的话，我会怎么做呢？如果不是什么是更好的做法呢？谢谢！

例如用下面的树：

  6 
    / \ 
     5  7 

级别0：（6，NULL）

级别1：（5,6）（7,6）

Answer 1

因此，不幸的有并不是严格使用一个队列的方式，假设您的节点只有左，右和值。问题是一旦深度> 0，那个级别的节点可能会有不同的父母，并且除非以某种方式存储它，否则该信息将消失。

这样做的简单方法是在Node类中添加一个Node父节点。除此之外，您还可以创建一个内部类来保存节点到父节点的映射，或者可以使用任意数量的数据结构。下面我包括了如何用hashmaps做到这一点。

public void printLevelOrder(){ 
    Queue<Node> q = new LinkedList<Node>(); 
    Map<Node, Node> parents = new HashMap<Node,Node>(); 
    Node nextLevel = null; 
    q.add(this); 
    int lvl = 0; 

    while (!q.isEmpty()){ 
     Node n = q.remove(); 
     if (n == nextLevel || nextLevel == null){ 
      System.out.print("\nlvl " + lvl++ +" "); 
      nextLevel = null; 
     } 
     System.out.print("("+n.value +","+parents.remove(n)+")"); 
     if (n.left != null){ 
      q.add(n.left); 
      parents.put(n.left, n); 
      if (nextLevel == null) 
       nextLevel = n.left; 
     } 
     if (n.right != null){ 
      q.add(n.right); 
      parents.put(n.right, n); 
      if (nextLevel == null) 
       nextLevel = n.right; 
     } 
    } 
} 

要按级别打印节点，我执行以下操作。下一个级别通过添加第一个非null nextLevel节点来确定。当我们到达该节点时，我们知道我们正处于下一行的开始处，并且再次将它清空。