فئة Node

الدرس 3 من 16 في دورة شجرة AVL - سلسلة هياكل البيانات #10 على Coddy.

تخزن كل عقدة في الشجرة أربعة أشياء: value الخاصة بها، ومؤشرات إلى ابن left و right، و height الخاص بها. تعتبر العقدة الجديدة تماماً ورقة (leaf)، لذا يبدأ ارتفاعها عند 1 وليس لديها أبناء بعد.

تتبع الارتفاع مباشرة على العقدة (بدلاً من إعادة حسابه عن طريق المرور عبر الشجرة في كل مرة) هو ما يسمح لكل عملية لاحقة بالتحقق من التوازن في وقت ثابت (constant time).

التحدي

مبتدئ

اكتب فئة Node مع منشئ (constructor) يأخذ value ويقوم بتخزينها، ويضبط left و right على null، ويضبط height على 1.

جرّب بنفسك

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