Уровень порядка обхода в двоичном дереве поиска в 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

Просмотр всего поиска в виде последовательности «раундов», по одному «раунду» для каждого уровня.

В каждом раунде:

- 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

Начните процесс с «следующего раунда»"список заполнен только корневым узлом.

Повторяйте, пока список узлов" следующего раунда "не будет пустым или вы не найдете то, что искали.

Answer 2

Вот как я это сделал.

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 3

Ваш подход выглядит как подход DFS. Этот подход может и не следовать.Попробуйте использовать Очередь здесь, это поможет вам правильно пройти.Потому что он будет следовать подходу BFS, чтобы вы могли проходить уровень за уровнем.Добавьте первый левый узел, затем правый узел и, соответственно, следуйте.