🌳 Как найти высоту дерева в Python: простой способ

Как найти высоту дерева в Python?

Высота дерева - это максимальная глубина (длина самого длинного пути от корневого узла до листьев). Для нахождения высоты дерева в Python, мы можем использовать рекурсивный подход.

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        
def find_tree_height(node):
    if node is None:
        return 0
    else:
        left_height = find_tree_height(node.left)
        right_height = find_tree_height(node.right)
        
        # Возвращаем максимальную высоту из поддеревьев
        return max(left_height, right_height) + 1

# Пример использования
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print("Высота дерева:", find_tree_height(root))

В этом примере мы создаем класс Node для представления узлов дерева. Затем мы определяем функцию find_tree_height, которая рекурсивно находит высоту дерева.

Мы начинаем с проверки, является ли узел равным None. Если это так, мы возвращаем 0, так как высота пустого дерева равна 0. В противном случае, мы рекурсивно вызываем find_tree_height для левого и правого поддеревьев и находим их высоты.

Затем мы возвращаем максимальную высоту из левого и правого поддеревьев, увеличенную на 1. Выполнив эту операцию для корневого узла, мы получим высоту всего дерева.

В примере мы создаем дерево с корневым узлом (1) и его дочерними узлами (2) и (3). Узел (2) имеет своих детей - узлы (4) и (5). Мы выводим высоту дерева, используя функцию find_tree_height, и получаем результат.

Как найти высоту дерева в Python

Деревья - это структуры данных, которые играют важную роль в программировании и алгоритмах. Они используются для представления иерархических связей между объектами. Когда мы говорим о высоте дерева, мы имеем в виду расстояние от корня (вершины дерева) до самого удаленного листа (конечной вершины).

В этой статье мы рассмотрим различные способы нахождения высоты дерева в Python.

Метод рекурсии

Один из самых популярных способов найти высоту дерева - использовать рекурсию. Рекурсивный подход основан на том, чтобы применить ту же функцию к каждому поддереву, пока не достигнем листа. Затем мы возвращаем максимальную высоту из всех поддеревьев.

def tree_height(node):
    if node is None:
        return 0
    else:
        left_height = tree_height(node.left)
        right_height = tree_height(node.right)
        return max(left_height, right_height) + 1
    

В этом примере мы объявляем функцию tree_height, которая принимает узел дерева в качестве параметра. Если узел является пустым значением, мы возвращаем 0. В противном случае, мы рекурсивно вызываем функцию tree_height для левого и правого поддерева и возвращаем максимальную высоту из двух поддеревьев плюс 1.

Метод обхода в глубину

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

def tree_height(node):
    stack = [(node, 0)]
    max_height = 0
    while stack:
        node, height = stack.pop()
        if node is not None:
            max_height = max(max_height, height)
            stack.append((node.left, height+1))
            stack.append((node.right, height+1))
    return max_height
    

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

Метод обхода в ширину

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

from collections import deque

def tree_height(node):
    if node is None:
        return 0
    queue = deque([(node, 0)])
    while queue:
        node, height = queue.popleft()
        if node is not None:
            if node.left is not None:
                queue.append((node.left, height+1))
            if node.right is not None:
                queue.append((node.right, height+1))
    return height
    

В этом примере мы использовали deque из модуля collections для реализации очереди. Мы начинаем с корневого узла и его начальной высоты 0. Затем мы последовательно извлекаем узлы из очереди и добавляем их потомков с новой высотой в очередь. В конце возвращаем высоту.

Заключение

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