Hauteur d'un arbre binaire en C/C++

La hauteur d'un arbre binaire est définie comme la profondeur maximale de n'importe quel nœud feuille à partir du nœud racine. C'est-à-dire, c'est la longueur du chemin le plus long du nœud racine à n'importe quel nœud feuille.

Considérons l'arbre binaire ci-dessous.

Puisque les nœuds feuilles correspondant à la profondeur maximale sont 40 et 50, pour trouver la hauteur, il suffit de trouver le nombre d'arêtes du nœud racine à l'un de ces deux nœuds, ce qui est 3.

Maintenant que nous savons ce que signifie la hauteur d'un arbre binaire, nous allons maintenant construire un algorithme pour trouver la hauteur de n'importe quel arbre binaire.

Logique pour trouver la hauteur d'un arbre binaire en C++

Décidons maintenant de la logique pour trouver la hauteur et écrivons d'abord notre pseudo-code.

Nous allons utiliser la récursion sur l'arbre pour trouver la hauteur. (Référez-vous à l'article de Wikipédia pour les concepts)

Comme la hauteur de l'arbre est définie comme le plus grand chemin de la racine à une feuille, nous pouvons calculer récursivement la hauteur des sous-arbres gauche et droit.

Nous pouvons maintenant appliquer la définition de la hauteur sur les sous-arbres.

Nous observons que c'est le maximum entre les sous-arbres gauche et droit, puis nous ajoutons un.

Puisque la hauteur de l'arbre est la hauteur maximale du sous-arbre + 1, nous continuons ainsi jusqu'à ce que le sous-arbre devienne NULL, et sa hauteur soit 0.

À ce stade, notre fonction se terminera enfin, et

Écrivons la fonction tree_height() qui calcule la hauteur.

// Find height of a tree, defined by the root node
int tree_height(Node* root) {
    if (root == NULL) 
        return 0;
    else {
        // Find the height of left, right subtrees
        left_height = tree_height(root->left);
        right_height = tree_height(root->right);
         
        // Find max(subtree_height) + 1 to get the height of the tree
        return max(left_height, right_height) + 1;
}

La ligne n°3 évalue la condition de terminaison, lorsque la taille du sous-arbre est 0, ou lorsque le nœud racine est NULL.

Les lignes 7 et 8 trouvent récursivement la hauteur des sous-arbres gauche et droit.

Et enfin, la ligne 11 renvoie le maximum des deux, renvoyant la hauteur de l'arbre.

Implémentation en C/C++

Ce qui suit est un programme complet montrant comment l'arbre binaire est construit, puis montre la logique pour trouver la hauteur dans tree_height().

#include <stdio.h>
#include <stdlib.h>

typedef struct Node Node;

// Define the Tree Node here
struct Node {
    int value;
    // Pointers to the left and right children
    Node* left, *right;
};


Node* init_tree(int data) {
    // Creates the tree and returns the
    // root node
    Node* root = (Node*) malloc (sizeof(Node));
    root->left = root->right = NULL;
    root->value = data;
    return root;
}

Node* create_node(int data) {
    // Creates a new node
    Node* node = (Node*) malloc (sizeof(Node));
    node->value = data;
    node->left = node->right = NULL;
    return node;
}

void free_tree(Node* root) {
    // Deallocates memory corresponding
    // to every node in the tree.
    Node* temp = root;
    if (!temp)
        return;
    free_tree(temp->left);
    free_tree(temp->right);
    if (!temp->left && !temp->right) {
        free(temp);
        return;
    }
}

int tree_height(Node* root) {
    // Get the height of the tree
    if (!root)
        return 0;
    else {
        // Find the height of both subtrees
        // and use the larger one
        int left_height = tree_height(root->left);
        int right_height = tree_height(root->right);
        if (left_height >= right_height)
            return left_height + 1;
        else
            return right_height + 1;
    }
}

int main() {
    // Program to demonstrate finding the height of a Binary Tree

    // Create the root node having a value of 10
    Node* root = init_tree(10);
    
    // Insert nodes onto the tree
    root->left = create_node(20);
    root->right = create_node(30);
    root->left->left = create_node(40);
    root->left->right = create_node(50);

    // Find the height of the tree
    int height = tree_height(root);
    printf("Height of the Binary Tree: %d\n", height);

    // Free the tree!
    free_tree(root);
    return 0;
}