java - 在 BFS 中创建接受用户输入的树

Question

我很困惑如何在遍历 BFS 时维护树顶。我接受这样的输入:

5 // total number of nodes in tree (root node will always be 1)
  // this number also tells the number of lines that'll be coming up
2 3 // left and right child of root, tree be like : 1
                                                   / \
                                                  2   3
4 5 // left and right child of 2 , tree             1
                                                   / \
                                                  2   3
                                                 / \
                                                4   5
-1 -1 // left and right child of 3 , that's null
-1 -1 // left and right child of 4
-1 -1 // left and right child of 5

以上述方式继续，用户在 BFS 中输入左右子节点。但我无法理解如何实现这一目标。

我的看法是:

LinkedList<Node> list = new LinkedList<Node>
list.add(root); //initially push root
while(list.peek()){  //while there is node left in linked list
    curr = list.poll();
    curr.left = new Node(x) // x = whatever is the user input is (using nextInt)
                            // and if it's -1, i'll make left child null
    curr.right = new Node(x) // same goes for this one
    ll.add(curr);

}

最后，我需要根节点的引用，我不知道如何获取它？另外，有没有更好的方法来完成这项任务

Answer 1

希望下面的代码可以帮助您。

“readTree”函数用于读取树。

public static Node readTree(Scanner in) {
    Queue<Node> queue = new LinkedList<Node>();
    Node root = new Node(1);
    queue.add(root);
    while (!queue.isEmpty()) {
        Node node = queue.poll();
        int left = in.nextInt();
        int right = in.nextInt();
        if (-1 != left) {
            node.left = new Node(left);
            queue.add(node.left);
        }
        if (-1 != right) {
            node.right = new Node(right);
            queue.add(node.right);
        }
    }
    return root;
}

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    in.nextInt(); // number of nodes is not used.
    Node result = readTree(in);
}