Определение высоты дерева — распространенная проблема в информатике и программировании. Высота дерева относится к максимальному количеству ребер между корневым узлом и листовым узлом. В этой статье блога мы рассмотрим несколько методов расчета высоты дерева, а также приведем примеры кода на Python.

Метод 1: рекурсивный подход
Один из самых простых методов определения высоты дерева — использование рекурсивного подхода. Мы можем определить рекурсивную функцию, которая обходит дерево и вычисляет высоту, рекурсивно находя высоту левого и правого поддеревьев.

# Node class definition
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
# Recursive function to calculate the height of the tree
def calculate_tree_height(node):
    if node is None:
        return 0
    left_height = calculate_tree_height(node.left)
    right_height = calculate_tree_height(node.right)
    return max(left_height, right_height) + 1
# Example usage
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("The height of the tree is:", calculate_tree_height(root))

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

from collections import deque
# Node class definition (same as above)
# Iterative function to calculate the height of the tree
def calculate_tree_height(node):
    if node is None:
        return 0
    queue = deque()
    queue.append(node)
    height = 0
    while queue:
        level_size = len(queue)
        for _ in range(level_size):
            current_node = queue.popleft()
            if current_node.left:
                queue.append(current_node.left)
            if current_node.right:
                queue.append(current_node.right)
        height += 1
    return height
# Example usage (same as above)
print("The height of the tree is:", calculate_tree_height(root))

Метод 3: использование поиска в глубину (DFS)
Поиск в глубину — это еще один метод расчета высоты дерева. Мы можем выполнить обход дерева в глубину и отслеживать максимальную глубину, достигнутую во время обхода.

# Node class definition (same as above)
# Depth-First Search function to calculate the height of the tree
def calculate_tree_height(node):
    if node is None:
        return 0
    stack = [(node, 1)]
    height = 0
    while stack:
        current_node, current_depth = stack.pop()
        if current_depth > height:
            height = current_depth
        if current_node.left:
            stack.append((current_node.left, current_depth + 1))
        if current_node.right:
            stack.append((current_node.right, current_depth + 1))
    return height
# Example usage (same as above)
print("The height of the tree is:", calculate_tree_height(root))