В сфере структур данных деревья играют решающую роль в организации и хранении иерархических отношений. Двумя фундаментальными свойствами деревьев являются их высота и глубина. Хотя эти термины часто используются как взаимозаменяемые, они представляют собой разные концепции. В этой статье мы углубимся в различия между высотой и глубиной дерева, рассмотрим различные методы их вычисления и приведем примеры кода на популярных языках программирования.

Понимание высоты и глубины.
Прежде чем мы углубимся в методы, важно понять определения высоты и глубины в деревьях.

Высота. Под высотой дерева понимается длина самого длинного пути от корня до любого листового узла. Другими словами, он измеряет количество ребер на самом длинном нисходящем пути от корня к листу.

Глубина: Глубина дерева представляет собой длину пути от узла до корня. Он измеряет количество ребер от данного узла до корневого узла.

Методы расчета высоты и глубины:

1. Рекурсивный подход:
   • В этом методе мы будем использовать рекурсивную функцию для вычисления высоты и глубины дерева.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
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
def tree_depth(node):
    if node is None:
        return 0
    else:
        return tree_depth(node.parent) + 1

<ол старт="2">

Итеративный подход:

• В этом методе мы будем использовать стек или очередь для перебора дерева и вычисления высоты и глубины.

def tree_height_iterative(root):
    if root is None:
        return 0
    height = 0
    queue = [root]
    while queue:
        level_size = len(queue)
        for _ in range(level_size):
            node = queue.pop(0)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        height += 1
    return height
def tree_depth_iterative(node):
    if node is None:
        return 0
    depth = 0
    while node.parent:
        node = node.parent
        depth += 1
    return depth

3. Использование поиска в глубину (DFS):
   • DFS можно использовать для вычисления высоты и глубины путем обхода дерева в глубину.

def tree_height_dfs(node):
    if node is None:
        return 0
    max_height = 0
    stack = [(node, 1)]
    while stack:
        curr_node, curr_height = stack.pop()
        max_height = max(max_height, curr_height)
        if curr_node.left:
            stack.append((curr_node.left, curr_height + 1))
        if curr_node.right:
            stack.append((curr_node.right, curr_height + 1))
    return max_height
def tree_depth_dfs(node):
    if node is None:
        return 0
    depth = 0
    stack = [node]
    while stack:
        curr_node = stack.pop()
        depth += 1
        if curr_node.parent:
            stack.append(curr_node.parent)
    return depth

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