Подсчет количества узлов в полном двоичном дереве

Полное бинарное дерево определяется как дерево, в котором все уровни, за исключением, возможно, последнего, полностью заполнены, а все узлы последнего уровня расположены как можно левее. Количество узлов на последнем уровне может варьироваться от 1 до максимум 2, возведенных в степень h, где h представляет собой высоту дерева.

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

#include <stdio.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

int getHeight(struct TreeNode* node) {
    int height = 0;
    while (node) {
        height++;
        node = node->left;
    }
    return height;
}

int countNodes(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }

    // Calculate the height of the left and right subtrees
    int left_height = getHeight(root->left);
    int right_height = getHeight(root->right);

    // If the height of the left and right subtrees is the same, it means the tree is complete
    if (left_height == right_height) {
        // The total number of nodes in a complete binary tree with height h is 2^h - 1
        return (1 << left_height) - 1;
    } else {
        // If the height of the left and right subtrees is not the same, recursively count the nodes
        // in the left and right subtrees and add 1 for the root node
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
}

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

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