Classe Nodo

Lezione 3 di 16 del corso Albero AVL - Serie sulle strutture dati #10 di Coddy.

Ogni nodo dell’albero memorizza quattro elementi: il suo value, i puntatori a un figlio left e a un figlio right, e la propria height. Un nodo appena creato è una foglia, quindi la sua altezza iniziale è 1 e non ha ancora figli.

Tenere traccia dell’altezza direttamente nel nodo (anziché ricalcolarla percorrendo l’albero ogni volta) permette a ogni operazione successiva di verificare il bilanciamento in tempo costante.

Sfida

Principiante

Scrivi una classe Node con un costruttore che accetta un value e lo memorizza, imposta left e right su null e imposta height su 1.

Provalo tu

#include <stdio.h>
#include "node.h"

int main(void) {
    char line[256];
    while (fgets(line, sizeof(line), stdin) != NULL) {
        int v;
        if (sscanf(line, "%d", &v) != 1) {
            continue;
        }
        Node* n = Node_create(v);
        if (n->left == NULL && n->right == NULL) {
            printf("%d %d null null\n", n->value, n->height);
        } else if (n->left == NULL) {
            printf("%d %d null %d\n", n->value, n->height, n->right->value);
        } else if (n->right == NULL) {
            printf("%d %d %d null\n", n->value, n->height, n->left->value);
        } else {
            printf("%d %d %d %d\n", n->value, n->height, n->left->value, n->right->value);
        }
    }
    return 0;
}