Высота двоичного дерева - как этот алгоритм работает в Python?

Question

Я наткнулся на этот алгоритм, чтобы найти высоту двоичного дерева.Кто-нибудь может объяснить, как это работает?В частности, я запутался в рекурсивных вызовах внутри функции max.Что такое максимальное сравнение на каждой итерации и как можно добавить результат к 1, не вызывая ошибки TypeError?Спасибо!

def get_height(root):
if root is None: 
    return 0
return 1 + max(get_height(root.left), get_height(root.right))

Answer 1

Добавление строки в код поможет выяснить, что происходит.
Здесь класс, представляющий дерево.

class Tree:
    def __init__(self,id,left=None,right=None):
        self.id = id
        self.left = left
        self.right = right

И функция для поиска высоты.

def get_height(root):
    if root is None: 
        return 0

    my_height = 1 + max(get_height(root.left), get_height(root.right))
    print("id :{} height: {}".format(root.id,my_height))
    return my_height

t = Tree(1,Tree(2,Tree(4),Tree(5)),Tree(3))

т можно увидеть следующим образом.

     1
    / \
   2   3
  / \   
 4   5 

При вызове get_height(t) это вывод:

id :4 height: 1
id :5 height: 1
id :2 height: 2
id :3 height: 1
id :1 height: 3

Вызовы начинаются с корня до тех пор, пока после достижения конечного узла функция будет вызываться с None.
Предположим, что он достиг листа (например, Узел 4). Результаты для get_height () на узле 4 будут 1 + max(get_height(None),get_height(None)) = 1 + max(0,0) =1.
Таким образом, узел 4 возвращает 1. Абонент (родитель узла 4, то есть узла 2) получит 1 от Node 4 и 1 от Node 5.
Таким образом, он заключит, что его высота равна 1+max(1,1)=2, и вернет это значение родительскому узлу.
Таким же образом, узел 1 (корень) получит 2 от Node 2 и 1 от Node 3 и вычислит его высоту как 1+max(1,2)=3.
Высота дерева равна 3, а корень равен высоте 3.

Answer 2

В частности, я запутался в рекурсивных вызовах внутри функции max. Что такое максимальное сравнение на каждой итерации и как можно добавить результат к 1, не вызывая ошибки TypeError?

Вы вызываете функцию дважды и передаете возвращаемые значения этих двух вызовов функции до макс. Итак, max сравнивает все, что возвращает эта функция.

Если это не ясно, давайте разберем эту строку:

left_height = get_height(root.left)
right_height = get_height(root.right)
max_height = max(left_height, right_height)
return 1 + max_height

Поскольку функция, которую мы вызываем, всегда возвращает целое число, max сравнивает два целых числа, что дает вам большее из двух целых чисел. К чему мы, очевидно, можем добавить 1 к.

Другими словами, высота дерева на 1 больше высоты того поддерева, которое выше.

---

Вы можете подумать, что я обманул там. Как я могу доказать, что функция всегда возвращает целое число, когда я должен был предположить, что это доказать?

Ключ в том, что рекурсия является индуктивной. Если вы не очень хорошо знаете математику, вы можете сказать следующее:

• Если базовый регистр всегда возвращает целое число,
• и рекурсия всегда вызывает меньший регистр
• и если мы всегда возвращаем целое число, пока все меньшие регистры возвращают целое число
• тогда мы всегда возвращаем целое число.

Первая часть проста: если ее нет, мы возвращаем 0.

Вторая часть происходит от определения дерева: левая ветвь дерева и правая ветвь дерева всегда являются меньшими поддеревьями дерева. (Это не будет верно для циклического графа, где root.left может быть root или его прародителем.)

Третья часть - это объяснение первой половины ответа.

И мы закончили.