Logique de trouver la hauteur de l'arbre par récursivité

J'essaie de trouver la hauteur d'un arbre. Voici du code que j’ai trouvé en ligne. Cependant, je ne comprends pas comment cela fonctionne. Je vous serais reconnaissant de bien vouloir expliquer le fonctionnement de ce programme.

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

struct n {
int data;
struct n *left;
struct n *right;
};

typedef struct n node;

int height_of_tree(node *root) {
if (root == NULL) return -1; // Why doesn"t the function break here?
int leftTree  = height_of_tree(root->left);
int rightTree = height_of_tree(root->right);
if (leftTree > rightTree) return leftTree + 1;
else return rightTree + 1;
}

node *getNewNode(int data) {
node *newNode  = (node *) malloc(sizeof(node));
newNode->data  = data;
newNode->left  = NULL;
newNode->right = NULL;
return newNode;
}

node *insert(node *root, int data) {
if (root == NULL) root = getNewNode(data);
else if (data <= root->data)
root->left  = insert(root->left,  data);
else root->right = insert(root->right, data);
return root;
}

int main() {
node *root = NULL;
root = insert(root, 12);
root = insert(root, 23);
root = insert(root, 122);
root = insert(root, 1);
root = insert(root, 2);
root = insert(root, -3);
root = insert(root, -4);

printf("%dn", root->right->data);
printf("%dn", height_of_tree(root));
}

Pourquoi ne pas le height_of_tree retour de fonction?

Réponses:

1 pour la réponse № 1

Tout d’abord, pour être clair, votre programme consiste à trouver la hauteur de un arbre binaire, dans lequel chaque noeud a au plus 2 enfants (gauche et / ou droite)

Donc, l'idée de base derrière la fonction de récursivité height_of_tree(node *root) est-ce à partir de la racine de l'arbre, nous allons trouver et comparer la height de son noeud gauche et son noeud droit.

Pour trouver la hauteur du nœud gauche (ou du nœud droit), supposons que le nœud gauche et tous ses enfants restent autonomes en tant que sous-arborescence et que le nœud lui-même constitue la racine. Nous commençons à courir height_of_tree de nouveau sur ce type d'arborescence avec le nœud gauche comme nouvelle racine (c'est pourquoi nous l'appelons récursion) La même logique s'applique également au noeud de droite:

// Reuse height_of_tree() to find the heights of the left node and the right node
// leftTree here means left tree"s height
int leftTree  = height_of_tree(root->left);
int rightTree = height_of_tree(root->right);

Ensuite, nous commençons à comparer: Si le noeud gauche "taille> s la hauteur du noeud droit", la racine (ou leurs parents) aura la hauteur du noeud gauche "s + 1. s height, alors la racine aurait le nœud droit "s height + 1:

if (leftTree > rightTree) return leftTree + 1;
else return rightTree + 1;

Enfin, le contrôle conditionnel if (root == NULL) return -1; est de vérifier quand arrêter de descendre et de regarderpour les sous-arbres (parce qu'il n'y a plus de nœuds dessous ou on peut dire nœud == NULL) Nous devons d'abord vérifier ceci avant d'exécuter d'autres lignes de code car if (root == NULL), nous n’avons sûrement pas les prochains enfants gauche / droit.

Quelques exemples:

1) Lorsque l’arbre est littéralement = NULL, alors height_of_tree retournera -1.

node *root = NULL;
printf("%dn", height_of_tree(root)); // Print out -1

2) Quand l’arbre n’a qu’un seul noeud, la racine height_of_tree retournera 0. (Veuillez noter que par définition, un arbre composé uniquement d'un nœud racine a une hauteur de 0)

node *root = NULL;
root = insert(root, 12);
printf("%dn", height_of_tree(root)); // Print out 0

3) Lorsque l’arbre n’a que deux nœuds, c’est-à-dire la racine et un enfant, height_of_tree retournera 1.

node *root = NULL;
root = insert(root, 12); // root with value = 12
root = insert(root, 23); // right child because its value 23 > root"s value 12
printf("%dn", height_of_tree(root)); // Print out 1

Je serai plus élaboré sur ce troisième cas:

• Commençons par la racine de l’arbre, qui est 12.
• Comme la racine n'est pas NULL, nous commençons à trouver la hauteur de son enfant gauche: int leftTree = height_of_tree(root->left);
• Comme l'enfant de gauche est NULL, la fonction height_of_tree(root->left) , une fois exécuté, retournera -1, faisant ainsi int leftTree = -1
• Ensuite, nous commençons à trouver la taille de son bon enfant: int rightTree = height_of_tree(root->right);
• Le noeud de droite devient maintenant un nouvel arbre d’un seul noeud, conformément à l’exemple n ° 2 ci-dessus, nous avons la hauteur = 0 pour un arbre d’un seul noeud, donc int rightTree = 0
• Enfin, en comparant leftTree et rightTree, nous découvrons que le rightTree est plus grand, donc la hauteur de la racine sera l’arbre de droite + 1 (la plus grande taille de son enfant + 1). En conséquence, la hauteur de la racine est = rightTree + 1 = 1

J'espère que cela t'aides!

---