java中二叉搜索树中的层序遍历

Question

我为我的二叉搜索树做了 4 次不同的遍历。我被困在最后一个是级别顺序遍历，我似乎无法找到如何正确执行它。

主要问题是我不知道如何一次只搜索一个级别，我只能弄清楚如何搜索整个左子树或整个右子树。

private void preOrder(BinaryNode<AnyType> t )

    {

        if(isEmpty()){

            System.out.println("Empty");

        }

        if(t != null) {

            System.out.println(t.element);

            preOrder(t.left);

            preOrder(t.right);

        }

    }

    private void postOrder(BinaryNode<AnyType> t){

        if(isEmpty()){

            System.out.println("Empty");

        }

        if (t != null) {

            postOrder(t.left);

            postOrder(t.right);

            System.out.println(t.element);

        }

    }

    private void inOrder(BinaryNode<AnyType> t)

    {

        if(isEmpty()){

            System.out.println("Empty");

        }

        if (t != null) {

            inOrder(t.left);

            System.out.println(t.element);

            inOrder(t.right);

        }

    }

    private void levelOrder(BinaryNode<AnyType> t, int level)

    {

        if(isEmpty()){

            System.out.println("Empty");

        }

        if(height(t) == 2) {

            System.out.println(t.element);

        }else if(height(t) > 1){

            levelOrder(t.left, level );

            levelOrder(t.right, level );

        }

    }

Answer 1

我就是这样做的。private void levelOrder(BinaryNode root) {&nbsp; &nbsp; &nbsp; &nbsp; if (root == null) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; Queue<BinaryNode> q = new LinkedList<>();&nbsp; &nbsp; &nbsp; &nbsp; // Pushing root node into the queue.&nbsp; &nbsp; &nbsp; &nbsp; q.add(root);&nbsp; &nbsp; &nbsp; &nbsp; // Executing loop till queue becomes&nbsp; &nbsp; &nbsp; &nbsp; // empty&nbsp; &nbsp; &nbsp; &nbsp; while (!q.isEmpty()) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; BinaryNode curr = q.poll();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.print(curr.element + " ");&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // Pushing left child current node&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (curr.left != null) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; q.add(curr.left);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // Pushing right child current node&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (curr.right != null) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; q.add(curr.right);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }

Answer 2

您的方法看起来像 DFS 方法它可能不遵循该方法。尝试在此处使用 Queue 它将帮助您正确遍历。因为它将遵循 BFS 方法，以便您可以逐层遍历。添加第一个左节点，然后添加右节点并按照以下步骤。

Answer 3

将整个搜索视为一系列“轮”，每个级别一个“轮”。在每一轮中：- initialize a "next round" list of nodes to empty- process a prepared list of nodes (the ones that are at that level and thus to be searched in that round) whereby for each node :&nbsp; - do the actual comparison&nbsp; - add all the node's child nodes to the "next round" list使用仅填充根节点的“下一轮”列表开始该过程。重复直到“下一轮”节点列表变为空或者您找到了您要查找的内容。