קבלת הגובה

שיעור 5 מתוך 16 בקורס עץ AVL – סדרת מבני נתונים מס' 10 של Coddy.

הוסף מתודה getHeight ל־AVLTree שקוראת את הגובה השמור של צומת. העניין היחיד הוא המקרה של null: תת־עץ ריק אינו קיים, ולכן לפי המוסכמה הגובה שלו הוא 0, אחד פחות מגובה של עלה אמיתי, שהוא 1.

העברת כל קריאות הגובה דרך המתודה הזו (במקום לקרוא ישירות ל־node.height בכל מקום) פירושה שצריך לכתוב את בדיקת ה־null פעם אחת בלבד.

אתגר

מתחילים

כתבו מתודה getHeight(node) בתוך AVLTree שמחזירה 0 אם node הוא null, אחרת מחזירה את node.height.

נסו בעצמכם

#include <stdio.h>
#include <string.h>
#include "avltree.h"

int main(void) {
    AVLTree* tree = AVLTree_create();
    char line[256];
    while (fgets(line, sizeof(line), stdin) != NULL) {
        line[strcspn(line, "\r\n")] = '\0';
        if (strcmp(line, "null") == 0) {
            printf("%d\n", AVLTree_getHeight(tree, NULL));
        }
        if (strcmp(line, "null") != 0) {
            int h;
            sscanf(line, "%d", &h);
            Node* n = Node_create(0);
            n->height = h;
            printf("%d\n", AVLTree_getHeight(tree, n));
        }
    }
    return 0;
}