Можно ли распечатать каждый уровень двоичного дерева на отдельной строке, используя обход в глубину? - PullRequest
Новая
       36

Можно ли распечатать каждый уровень двоичного дерева на отдельной строке, используя обход в глубину?

0 голосов
/ 27 мая 2018

Я знаком с использованием очереди для печати каждого уровня в отдельной строке за O(n) время.Я хочу знать, есть ли способ сделать это, используя предварительный заказ, обратный порядок или обратный порядок.У меня есть следующий код, но я не знаю, что делать с параметром depth.Единственная идея, которая у меня есть, - использовать массив связанных списков для хранения всех узлов при обходе дерева, занимая O(n) дополнительного пространства.Есть ли лучший способ сделать это? 

class Node {
 int key;
 Node left;
 Node right;

 Node(int value) {
    key = value;
    left = null;
    right = null;
 }
}

public class bst {

 private Node root;

 bst() {
    root = null;
 }

 private void printTreeRec(Node root, int depth) {
    if(root != null) {
        System.out.println(root.key);
        printTreeRec(root.left, depth + 1);
        printTreeRec(root.right, depth + 1);
    }
 }

 void printTree() {
    printTreeRec(root, 0);
 }

 public static void main(String[] Args) {
    bst tree = new bst();

    tree.insert(25);
    tree.insert(15);
    tree.insert(35);
    tree.insert(7);
    tree.insert(18);
    tree.insert(33);
    tree.insert(36);

    tree.printTree();
 }
}

Ответы [ 2 ]

0 голосов
/ 27 мая 2018

Вы можете сослаться на обсуждение здесь: Решение Java DFS .Разместите код ниже для удобства. 

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        levelHelper(res, root, 0);
        return res;
    }

public void levelHelper(List<List<Integer>> res, TreeNode root, int height) {
    if (root == null) return;
    if (height >= res.size()) {
        res.add(new LinkedList<Integer>());
    }
    res.get(height).add(root.val);
    levelHelper(res, root.left, height+1);
    levelHelper(res, root.right, height+1);
}
0 голосов
/ 27 мая 2018

Это действительно невозможно с упомянутыми подходами, потому что они идут depth-first, то есть они всегда идут в направлении, пока не достигнут конца ветви.

Или, по крайней мере, не при прямой печати выводана консоли при выполнении алгоритма.

Это не строгое доказательство, но оно должно описать проблему:

Предзаказ 

    System.out.println(root.key);
    printTreeRec(root.left, depth + 1);
    printTreeRec(root.right, depth + 1);

В конкретном узле, который вы печатаететекущий узел первым.Затем вы идете налево и печатаете этот узел и так далее.Поскольку вы уже опустили консоль и не можете вернуться назад, этот подход не будет работать

Inorder 

    printTreeRec(root.left, depth + 1);
    System.out.println(root.key);
    printTreeRec(root.right, depth + 1);

В этом случае вы начинаетев корне, и вы идете налево.Еще осталось, пока не осталось дочерних узлов.И тогда вы печатаете.Но теперь вы пойдете вверх по дереву, и что вы будете делать с фокусом на консоли?Еще раз вы должны двигаться вперед.Также невозможно в этом случае.

Postorder 

    printTreeRec(root.left, depth + 1);
    printTreeRec(root.right, depth + 1);
    System.out.println(root.key);

В этом случае вы начинаете с корня и идете налево.Пока не сможешь.Когда ты не можешь, ты начинаешь идти прямо.Идите прямо, пока не сможете.Тогда начните печатать.Но теперь, как и выше, вы поднимитесь вверх по дереву, и что вы будете делать с фокусом на консоли?Еще раз вы должны двигаться вперед.Снова невозможно.

Как мы можем заставить его работать?

Мы должны обмануть и передать переменную уровня, чтобы узнать уровень, на котором мы находимся в данный момент.,Заполните структуру данных, например карту, которая будет содержать значения узлов на уровень, и после завершения вычисления алгоритма выведите результат, один уровень на строку, используя карту.

...