Nodeクラス

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

木のすべてのノードは、4つの情報を保持します。それは、value、left および right の子へのポインタ、そして自身の height です。新しく作成されたノードはリーフ（葉）であるため、その高さは 1 から始まり、まだ子を持ちません。

（毎回木を走査して再計算するのではなく）ノードで直接高さを追跡することで、その後のすべての操作でバランスを定数時間でチェックできるようになります。

チャレンジ

初心者

value を受け取ってそれを保持し、left と right を null に設定し、height を 1 に設定するコンストラクタを持つ Node クラスを作成してください。

自分で試してみよう

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