高さの取得

Coddyの「AVL Tree - データ構造シリーズ #10」コースのレッスン 5/16。

AVLTreeに、ノードに格納された高さを読み取るgetHeightメソッドを追加します。唯一の工夫はnullの場合です。空のサブツリーは存在しないため、慣習としてその高さは、実際のリーフの高さである1より1つ小さい0とします。

すべての高さの検索を（いたる所で直接node.heightを読み取るのではなく）この1つのメソッドを経由させることで、nullチェックを一度書くだけで済むようになります。

チャレンジ

初心者

AVLTree に getHeight(node) メソッドを作成してください。このメソッドは、node が null の場合は 0 を返し、それ以外の場合は 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;
}