Klasa węzła

Lekcja 3 z 16 w kursie Drzewo AVL – struktury danych, seria #10 w Coddy.

Każdy węzeł drzewa przechowuje cztery rzeczy: swoją value, wskaźniki do lewego i prawego dziecka — left i right — oraz własną height. Zupełnie nowy węzeł jest liściem, więc jego wysokość początkowa wynosi 1 i nie ma jeszcze żadnych dzieci.

Przechowywanie wysokości bezpośrednio w węźle (zamiast ponownego obliczania jej przez przechodzenie po drzewie za każdym razem) pozwala każdej kolejnej operacji sprawdzać równowagę w stałym czasie.

Wyzwanie

Początkujący

Napisz klasę Node z konstruktorem, który przyjmuje value i je przechowuje, ustawia left i right na null oraz ustawia height na 1.

Spróbuj swoich sił

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