노드 클래스

Coddy의 AVL 트리 - 자료구조 시리즈 #10 코스 레슨 — 16개 중 3번째.

트리의 모든 노드는 네 가지를 저장합니다: 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;
}