Высота двоичного дерева

Рассмотрим следующий код:

public int heightOfBinaryTree(Node node)
{
    if (node == null)
    {
        return 0;
    }
    else
    {
        return 1 +
        Math.max(heightOfBinaryTree(node.left),
            heightOfBinaryTree(node.right));
    }
}

Я хочу знать логические причины этого кода. Как люди придумали это? Есть ли у некоторых индуктивные доказательства?

Кроме того, я думал о том, что просто делал BFS с корнем двоичного дерева в качестве аргумента, чтобы получить высоту двоичного дерева. Является ли предыдущий подход лучше, чем мой? Почему?

Ответ 1

if (node == null)
{
    return 0;
}

Дети листовых узлов null. Поэтому это говорит о том, что после того, как мы пройдем мимо листьев, больше нет узлов.

Если мы не проходим мимо листовых узлов, мы должны вычислить высоту, и этот код делает это рекурсивно.

return 1 +

Текущая node добавляет высоту 1 к высоте вычисляемого поддерева.

    Math.max(heightOfBinaryTree(node.left),
        heightOfBinaryTree(node.right));

Мы рекурсивно вычисляем высоту левого поддерева (node.left) и правого поддерева (node.right). Поскольку мы вычисляем максимальную глубину, мы берем максимум этих двух глубин.

Я показал выше, что рекурсивная функция верна. Поэтому вызов функции родительского node будет вычислять глубину всего дерева.

Здесь представлено графическое представление высоты дерева из этого документа. h - высота дерева, hl и hr - это высоты левого и правого поддеревьев соответственно.

Кроме того, я думал о том, чтобы просто BFS с корнем двоичного дерева как аргумент, чтобы получить высоту бинарное дерево. Является ли предыдущий лучше, чем мой? Почему?

Код, который вы предоставили, является формой DFS. Поскольку вам нужно обработать все узлы, чтобы найти высоту дерева, разница между DFS и BFS не будет разницу во времени выполнения, хотя BFS будет использовать память O (N), в то время как DFS будет использовать память O (logN). BFS также немного сложнее кодировать, поскольку для него требуется очередь, в то время как DFS использует "встроенный" рекурсивный стек.

Ответ 2

Логика этого кода:

так как a node будет иметь двух детей, высота дерева будет максимальной высотой дерева, корни которого являются левым дочерним и правым дочерними элементами, и, конечно, +1 для ходьбы к детям.

Как вы можете видеть, приведенное выше описание является рекурсивным, а также код.

BFS также должен делать, но это будет излишним, как реализация, так и пространственная/временная сложность.

Есть слова, рекурсивные функции, хотя их трудно понять, но они очень элегантны для реализации.

Ответ 3

Высота дерева - это длина самого длинного нисходящего пути от него. Эта функция является рекурсивным способом подсчета уровней двоичного дерева. Он просто увеличивает счетчики, когда он спускается по дереву, возвращая максимальный счетчик (счетчик на самом низком node).

Надеюсь, я помог.

Ответ 4

Это рекурсивная функция. Он говорит, что высота дерева равна 1 + высоте его самой высокой ветки.

Является ли BFS первым поиском ширины? Я не уверен, какая разница в эффективности, но мне нравится простота рекурсивной функции.