java - 具有父节点的二叉搜索树级顺序

Question

您好我正在尝试以格式打印出二叉搜索树的级别顺序(node element, parent node element)。我目前正在使用队列来获取级别顺序，但我很难获得父节点。有可能与队列有关吗？如果是这样，我将如何去做？如果不是，什么是更优化的方法？谢谢！

例如下面的树：

         6
       /   \
      5     7

0级：（6，空）

1 级：(5, 6) (7, 6)

Answer 1

所以不幸的是，假设您的节点只有一个左、右和值，没有一种方法可以严格地使用一个队列来执行此操作。问题是，一旦深度 > 0，该级别的节点可能有不同的父节点，除非您以某种方式存储该信息，否则该信息将消失。

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

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

要按级别打印节点，我执行以下操作。通过添加第一个非空 nextLevel 节点来确定下一个级别。当我们到达那个节点时，我们知道我们在下一行的开头，并再次将其清空。