BST найти высоту рекурсивно
Я пытаюсь найти высоту дерева двоичного поиска в моей программе и продолжаю искать это рекурсивное решение, чтобы найти высоту:
int maxHeight(BinaryTree *p) {
if (!p) return 0;
int left_height = maxHeight(p->left);
int right_height = maxHeight(p->right);
return (left_height > right_height) ? left_height + 1 : right_height + 1;
}
Может кто-нибудь объяснить мне, как это работает? Я не понимаю, как это складывает высоту. Похоже, что он должен просто пройти через каждую сторону дерева и вернуть 0.
Решение
Алгоритм работает следующим образом:
Если дерево, на которое я смотрю, не существует, то длина дерева равна 0.
В противном случае длина дерева — это максимальная высота двух поддеревьев, которые у меня есть плюс 1 (плюс 1 необходим, чтобы включить узел, который вы просматриваете в данный момент).
Например. если у меня есть дерево без ветвей (то есть пень), тогда у меня есть высота, равная единице, потому что у меня есть два поддерева высоты 0, а максимальное из этих высот плюс 1 равно 1.
другой пример:
Если у меня есть дерево:
A - B - C - D
| |
E F
(где а является корнем)
тогда высота не равна 0, так как A не равно нулю
высота = максимальная (высота (слева), высота (справа)) + 1.
высота слева в точке A равна 0, потому что A не имеет левой ветви.
Высота правой ветви — это высота B + 1.
Чтобы определить высоту B, мы рассматриваем B как совершенно новое дерево:
B - C - D
| |
E F
сейчас
высота = максимальная (высота (слева), высота (справа)) + 1.
Чтобы вычислить высоту слева, мы рассматриваем E как совершенно новое дерево:
E
это существует, поэтому его высота не 0
однако его двух ветвей не существует, поэтому его высота равна 1 (каждая ветвь имеет высоту 0)
вернемся к родительскому дереву снова:
B - C - D
| |
E F
мы отрабатывали высоту, и выяснили, что высота левой ветви равна 1.
so height = max (1, высота (справа)) + 1
итак, какая высота справа?
еще раз, мы рассматриваем правильную ветвь как ее собственное дерево:
C - D
|
F
проблема та же, что и раньше
высота = максимальная (высота (слева), высота (справа)) + 1
чтобы вычислить высоту (слева), мы рассмотрим F самостоятельно
F
F имеет высоту 1, потому что он имеет две нулевые ветви (т.е. максимум двух 0 высот плюс 1)
теперь смотрю на право
D
D имеет высоту 1 по той же причине
назад к родителю F и D:
C - D
|
F
Высота С составляет:
max (высота (F), высота (D)) + 1
= максимум (1, 1) + 1
= 1 + 1
= 2
Итак, теперь мы знаем высоту C, мы можем вернуться к родителю:
B - C - D
| |
E F
Напомним, мы вычислили длину левой ветви B как 1, а затем начали вычислять ее высоту правой ветви.
Теперь мы знаем, что правая ветвь имеет высоту 2
Макс (1, 2) составляет 2.
2 + 1 = 3
Следовательно, высота B равна 3.
Теперь мы знаем это, мы наконец вернулись к нашему первоначальному дереву:
A - B - C - D
| |
E F
мы уже отработали высоту левой ветви на 0, а затем начали работать на правой ветви.
Теперь мы знаем, что правильная ветвь имеет высоту 3.
Следовательно,
высота (а) = Макс (высота (ноль), Макс (высота (B))
= Макс (0, 3) + 1
= 3 + 1
= 4
сделанный. Высота А составляет 4.
Другие решения
Функция возвращает 0, только если двоичное дерево равно нулю. Это имеет смысл, потому что если дерево пустое, нет узлов для подсчета, поэтому высота равна 0.
Если оно не равно нулю, функция добавит 1 (высоту текущего узла) к высоте левого или правого дочернего поддерева, в зависимости от того, что больше.
Как он узнает высоту дочерних деревьев? Вызывая себя рекурсивно, передавая левого или правого потомка, чтобы следующая рекурсия начиналась на один уровень вниз в дереве.
Что происходит, когда вы впервые вызываете функцию, проходя в корне дерева? Функция сначала вызывает себя рекурсивно, перемещаясь по крайним левым дочерним элементам, пока не найдет конечный узел. Он вызывает себя еще раз, передавая левый потомок конечного узла, который является нулевым. Этот последний вызов больше не повторяется и просто возвращает 0. Затем функция возвращается к правому дочернему элементу листа, который также возвращает 0. Затем она добавляет 1 для своей собственной высоты и возвращает.
Теперь мы находимся у родителя самого левого листа и, как и прежде, вернемся к правому ребенку (родной брат к листу). Это может не существовать (возвращает 0), быть листом (возвращает 1) или иметь детей (возвращает> 1). Каким бы ни было возвращаемое значение, оно будет сравниваться с крайним левым листом (высота 1), и, в зависимости от того, что больше, будет увеличиваться (всегда добавляя высоту текущего узла) и возвращаться как высота поддерева, укорененного в текущем узел.
Обратите внимание, что рекурсия будет продолжать «разворачиваться», пока она перемещается обратно к корню, но на каждом уровне она сначала будет проходить дальше вниз по правому дочернему поддереву. Это то, что известно как поиск в глубину. В конце концов, все дерево будет посещено, и максимальная высота будет вычислена до самого корня.
Ваш код не подходит для памяти. Например, когда вы запускаете этот метод, height_left а также height_right переменные все равно будут сохранены в памяти. Так что, если вы запустите эту функцию миллиарды раз? Я предлагаю вернуться без переменных, например
return max(maxHeight(p->left), maxHeight(p->right));