父节点的二叉搜索树级别顺序 [英] Binary search tree level order with parent node

问题描述

您好我正在尝试以(node element, parent node element)格式打印二进制搜索树的级别顺序.我目前正在使用队列来获取级别顺序，但是我很难获取父节点.是否可以处理队列?如果是这样，我将如何去做?如果不是，哪种最佳方法呢?谢谢！

Hi I am trying to print out level order of a binary search tree in the format (node element, parent node element). I am currently using queues to get the level order but I am having a hard time getting the parent node. Is it possible to do with queues? If so how would I go about doing it? If not what is a more optimal way of doing it? Thank you!

例如，下面的树:

         6
       /   \
      5     7

级别0:(6，空)

级别1:(5，6)(7，6)

Level 1: (5, 6) (7, 6)

推荐答案

因此，不幸的是，没有一种方法可以严格地对一个队列执行此操作，假设您的节点仅具有left，right和value.问题是一旦深度> 0，该级别的节点可能具有不同的父级，并且除非您以某种方式存储它，否则该信息将消失.

So unfortunately there isn't a way of doing this strictly with one queue, assuming your nodes only have a left,right, and value. The problem is once you get to depths > 0, the nodes at that level might have different parents, and that information is gone unless you store it in some fashion.

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

The easy way to do this is to just add a Node parent inside of your Node class. Barring that, you could also make a inner class that holds the mapping of the Node to parent node, or you could use any number of data structures. Below I included how to do this with 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;
        }
    }
}

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

To print the nodes by level I do the following. The next level is determined by adding the first non null nextLevel node. When we have reached that node, we know we are at the start of the next line, and null it out again.

这篇关于父节点的二叉搜索树级别顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！