Logica di trovare l'altezza dell'albero per ricorsione - ricorsione, logica, albero di ricerca binaria

Sto cercando di trovare l'altezza di un albero. Ecco del codice che ho trovato online. Tuttavia, non capisco come funzioni. Le sarei grato se spiegassi come funziona questo programma.

#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));
}

Perché non è il height_of_tree funzione di ritorno?

risposte:

1 per risposta № 1

In primo luogo, per essere chiari, il tuo pezzo di programma è quello di trovare l'altezza di un albero binario, in cui ogni nodo ha al massimo 2 bambini (sinistra e / o destra)

Quindi l'idea di base dietro la funzione di ricorsione height_of_tree(node *root) è che partendo dalla radice dell'albero, lo faremo trova e confronta il height del suo nodo sinistro e nodo destro.

Per trovare l'altezza del nodo sinistro (o nodo destro), supponiamo che il nodo sinistro e tutti i suoi figli rimarranno soli come sotto-albero e il nodo stesso sia la radice. Iniziamo a correre height_of_tree di nuovo su tale sotto-albero con il nodo sinistro come nuova radice (ecco perché lo chiamiamo ricorsione). La stessa logica si applica anche al nodo giusto:

// 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);

Quindi iniziamo a confrontare: Se l'altezza del nodo sinistro> l'altezza del nodo destro, allora la radice (oi loro genitori) avrebbero l'altezza del nodo sinistro + 1. E viceversa, se l'altezza del nodo destro> il nodo sinistro " s altezza, quindi la radice avrebbe il nodo giusto "s height + 1:

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

Infine, il controllo condizionale if (root == NULL) return -1; è controllare quando smettere di scendere e guardareper alberi secondari (perché non ci sono più nodi al di sotto di esso o possiamo dire nodo == NULL). Dobbiamo controllare questo prima di eseguire altre righe di codice perché if (root == NULL), allora sicuramente non avremo i bambini a sinistra / a destra successivi.

Qualche esempio:

1) Quando l'albero è letteralmente = NULL, allora height_of_tree restituirà -1.

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

2) Quando l'albero ha un solo nodo, ovvero la radice, allora height_of_tree restituirà 0. (Si noti che per definizione un albero costituito solo da un nodo radice ha un'altezza di 0)

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

3) Quando l'albero ha solo due nodi, ovvero la radice e un figlio, allora height_of_tree restituirà 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

Sarò più elaborato su questo terzo caso:

• Innanzitutto, inizieremo dalla radice dell'albero, che è 12.
• Poiché la radice non è NULL, iniziamo a trovare l'altezza del figlio sinistro: int leftTree = height_of_tree(root->left);
• Poiché il bambino sinistro è NULL, la funzione height_of_tree(root->left) , una volta eseguito, restituirà -1, creando così int leftTree = -1
• Quindi, iniziamo a trovare l'altezza del figlio giusto: int rightTree = height_of_tree(root->right);
• Il nodo destro ora diventa un nuovo albero di un solo nodo, secondo l'esempio # 2 sopra, abbiamo l'altezza = 0 per un albero di un solo nodo, quindi int rightTree = 0
• Infine, confrontando leftTree vs rightTree, scopriamo che rightTree è più alto, quindi l'altezza della radice sarà rightTree + 1 (l 'altezza del suo figlio più alto + 1). Di conseguenza, l'altezza della radice è = rightTree + 1 = 1

Spero che questo ti aiuti!

---