具有父节点的二进制搜索树级顺序

Question

您好，我正在尝试以（节点元素，父节点元素）的格式打印二进制搜索树的级别顺序。我目前正在使用队列来获取级别顺序，但很难获取父节点。可以处理队列吗？如果是这样的话，我该怎么做呢？如果不是的话，什么是更理想的方法？非常感谢。

例如，使用以下树：

         6
       /   \
      5     7

级别0:（6，空）

一级：（5,6）（7,6）

Answer 1

因此，不幸的是，假设节点只有左、右和值，没有一种方法可以严格地使用一个队列来实现这一点。问题是一旦你进入深度

实现这一点的简单方法是在节点类中添加一个节点父节点。除此之外，还可以创建一个内部类来保存节点到父节点的映射，或者可以使用任意数量的数据结构。下面我介绍了如何使用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节点来确定的。当我们到达那个节点时，我们知道我们在下一行的开头，并再次将其清空。