Classe Node

Leçon 3 sur 16 du cours Arbre AVL - Série Structures de données n°10 de Coddy.

Chaque nœud de l'arbre stocke quatre éléments : sa value, des pointeurs vers un enfant left et right, et sa propre height. Un tout nouveau nœud est une feuille, sa hauteur commence donc à 1 et il n'a pas encore d'enfants.

Le suivi de la hauteur directement sur le nœud (au lieu de la recalculer en parcourant l'arbre à chaque fois) est ce qui permet à chaque opération ultérieure de vérifier l'équilibre en temps constant.

Défi

Débutant

Écrivez une classe Node avec un constructeur qui prend une value et la stocke, définit left et right à null, et définit height à 1.

Essayez vous-même

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