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) {

        if (root == null) {

            return;

        }

        Queue<BinaryNode> q = new LinkedList<>();

        // Pushing root node into the queue.

        q.add(root);

        // Executing loop till queue becomes

        // empty

        while (!q.isEmpty()) {

            BinaryNode curr = q.poll();

            System.out.print(curr.element + " ");

            // Pushing left child current node

                if (curr.left != null) {

                    q.add(curr.left);

                }

                // Pushing right child current node

                if (curr.right != null) {

                    q.add(curr.right);

                }

            }

    }

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 :

  - do the actual comparison

  - add all the node's child nodes to the "next round" list

使用仅填充根节点的“下一轮”列表开始该过程。

重复直到“下一轮”节点列表变为空或者您找到了您要查找的内容。