Klasse Node

Lektion 3 von 16 im Kurs AVL-Baum - Datenstrukturen-Serie #10 von Coddy.

Jeder Knoten im Baum speichert vier Dinge: seinen value, Pointer auf ein left und right Kind-Element sowie seine eigene height. Ein brandneuer Knoten ist ein Blatt, daher beginnt seine Höhe bei 1 und er hat noch keine Kinder.

Das Speichern der Höhe direkt im Knoten (anstatt sie jedes Mal durch das Durchlaufen des Baums neu zu berechnen) ermöglicht es jeder späteren Operation, die Balance in konstanter Zeit zu prüfen.

Aufgabe

Anfänger

Schreiben Sie eine Klasse Node mit einem Konstruktor, der einen value entgegennimmt und diesen speichert, left und right auf null setzt und height auf 1 setzt.

Probier es selbst

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