Задачи модуля "Деревья": от высоты до зеркального отражения

Любое бинарное дерево состоит из корня (1 узел) плюс все узлы левого поддерева и правого поддерева. Чему равно количество узлов пустого дерева?

Описание алгоритма:

Используем рекурсию (Прямой обход). Формула элементарна: количество узлов в дереве = 1 (сам корень) + количество узлов в левом поддереве + количество узлов в правом поддереве.

Базовый случай: если дерево пустое (root == NULL), количество узлов равно 0.

#include <stdio.h>

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

int CountNodes(Node* root) {
    // Базовый случай
    if (root == NULL) {
        return 0;
    }
    
    // Рекурсивный шаг
    return 1 + CountNodes(root->left) + CountNodes(root->right);
}

Высота дерева равна максимуму из высот левого и правого поддеревьев, плюс один (за сам корень). Какова высота пустого дерева?

Описание алгоритма:

Высота дерева - это максимальное расстояние от корня до самого удаленного листа. Решается рекурсивно обратным обходом (постфиксным).

1. Сначала узнаем высоту левого поддерева.
2. Затем узнаем высоту правого поддерева.
3. Высота всего дерева = берем максимум из этих двух высот и прибавляем 1 (так как сам корень добавляет 1 уровень).
4. Базовый случай: высота пустого дерева (NULL) равна 0.

#include <stdio.h>

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// Вспомогательная функция максимума
int max(int a, int b) {
    return (a > b) ? a : b;
}

int GetHeight(Node* root) {
    if (root == NULL) {
        return 0;
    }
    
    int left_h = GetHeight(root->left);
    int right_h = GetHeight(root->right);
    
    return 1 + max(left_h, right_h);
}

Если текущий узел - лист, верните 1. В противном случае верните сумму количества листьев левого и правого поддеревьев.

Описание алгоритма:

Лист - это узел, у которого нет ни левого, ни правого сына. Нам нужно пройтись по всему дереву и подсчитать только такие узлы.

1. Если передан NULL, возвращаем 0.
2. Если узел является листом (root->left == NULL && root->right == NULL), возвращаем 1.
3. Иначе мы возвращаем сумму количества листьев из левого поддерева и количества листьев из правого поддерева.

#include <stdio.h>

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

int CountLeaves(Node* root) {
    if (root == NULL) {
        return 0;
    }
    
    // Проверка на лист
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    
    // Считаем листья в поддеревьях
    return CountLeaves(root->left) + CountLeaves(root->right);
}

Сначала проверьте базовые случаи: оба пусты или одно пустое. Если оба не пустые, сравните значения в корне и рекурсивно вызовите проверку для поддеревьев.

Описание алгоритма:

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

Логика проверки:

1. Если оба дерева пустые, они равны (возвращаем true).
2. Если одно пустое, а другое нет - они не равны (возвращаем false).
3. Если оба не пустые, проверяем: равны ли значения их корней? Если да, рекурсивно проверяем на равенство их левые поддеревья И правые поддеревья.

#include <stdio.h>
#include <stdbool.h>

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

bool AreIdentical(Node* tree1, Node* tree2) {
    // 1. Оба дерева пустые
    if (tree1 == NULL && tree2 == NULL) return true;
    
    // 2. Одно из деревьев пустое, а другое нет
    if (tree1 == NULL || tree2 == NULL) return false;
    
    // 3. Сверяем данные и рекурсивно спускаемся вниз
    return (tree1->data == tree2->data) 
        && AreIdentical(tree1->left, tree2->left) 
        && AreIdentical(tree1->right, tree2->right);
}

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

Описание алгоритма:

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

Это классическая задача, которую часто дают на собеседованиях (знаменитый мем "Инвертируй бинарное дерево"). Мы используем обратный обход (ЛПК) или прямой: достаточно поменять местами указатели left и right, а затем рекурсивно вызвать функцию для обоих детей.

#include <stdio.h>

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

void MirrorTree(Node* root) {
    if (root == NULL) {
        return;
    }
    
    // Сначала рекурсивно отражаем поддеревья
    MirrorTree(root->left);
    MirrorTree(root->right);
    
    // Меняем местами левого и правого сына текущего узла
    Node* temp = root->left;
    root->left = root->right;
    root->right = temp;
}