木構造のノードと構造
ポインターでノードをモデル化します。
「木構造のノードと構造」はCoddyKit上の無料C Academyレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはC Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C Academyコースには全4レッスンが含まれています。
二分木とは
二分木は階層構造の一種で、各ノードが値と、最大2つの子ノードへのリンクを持ちます。子ノードには左の子と右の子があります。
最上位のノードがルートです。子を持たないノードは葉と呼びます。この形状により、二分木は高速な検索、ソート、再帰的な処理に適しています。
ノードのstruct
Cでは、データと2つの自己参照ポインターを格納するstructでノードを表します。
各ポインターは別のNodeを指すか、その側に子がない場合はNULLを指します。
struct Node {
int value;
struct Node *left;
struct Node *right;
};自己参照ポインターを使う理由
ノードは、別の完全なノードを値として含むことができません。それでは無限の記憶領域が必要になるためです。代わりに、子ノードへのポインターを保持します。
ポインターのサイズは固定なので、ヒープ上の他のノードへつなげながら、struct自体のサイズを既知の値に保てます。
struct Node {
int value;
struct Node *left; /* 8 bytes on 64-bit */
struct Node *right; /* 8 bytes on 64-bit */
};便利なtypedef
どこでもstruct Nodeと入力するのは面倒です。typedefを使えば、単にNodeと書けます。
この時点では型がまだ完全に定義されていないため、structの内部ではタグが必要です。
typedef struct Node {
int value;
struct Node *left;
struct Node *right;
} Node;ノードを確保する
ノードはmallocで作成し、ヒープ上に置きます。値を設定し、両方の子ポインターをNULLに初期化します。
メモリを使用する前に、mallocがNULLを返していないことを必ず確認してください。
Node *create_node(int value) {
Node *n = malloc(sizeof(Node));
if (n == NULL) return NULL;
n->value = value;
n->left = NULL;
n->right = NULL;
return n;
}小さな木を手作業で構築する
リンクの仕組みを理解するため、ルートと2つの子からなる3つのノードを手作業でつなぎます。
このプログラムは木を構築して値を表示します。その後、通常は解放します（後で説明します）。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node *left;
struct Node *right;
} Node;
Node *create_node(int v) {
Node *n = malloc(sizeof(Node));
n->value = v; n->left = NULL; n->right = NULL;
return n;
}
int main(void) {
Node *root = create_node(10);
root->left = create_node(5);
root->right = create_node(15);
printf("%d %d %d\n", root->left->value, root->value, root->right->value);
return 0;
}孫ノードへ到達する
アロー演算子を連鎖させることで木をたどれます。root->left->rightは左の子へ移動し、続いてその右の子へ移動します。
ポインターをたどる前に、それがNULLでないことを確認してください。そうしないとプログラムがクラッシュします。
/* root
* \
* right (15)
* \
* right->right (20)
*/
if (root->right != NULL && root->right->right != NULL)
printf("%d\n", root->right->right->value);再帰的にノード数を数える
再帰は木に自然に適しています。ノード数を数える場合、空の部分木は0個、それ以外では現在のノードと両方の部分木のノード数を合計します。
NULLの確認が、再帰を停止するベースケースになります。
int count_nodes(Node *root) {
if (root == NULL) return 0;
return 1 + count_nodes(root->left)
+ count_nodes(root->right);
}高さを測定する
木の高さは、ルートから葉までの最長経路を辺の数で測ったものです。
2つの部分木の高さの大きいほうに1を加えます。空の木の高さを-1とすることで、ノード1つの木の高さは0になります。
int height(Node *root) {
if (root == NULL) return -1;
int l = height(root->left);
int r = height(root->right);
return 1 + (l > r ? l : r);
}葉を識別する
葉とは、子を持たないノードです。つまり、leftとrightの両方がNULLです。
この小さなヘルパーは、多くの走査やカウント処理で役立ちます。
int is_leaf(Node *n) {
return n != NULL && n->left == NULL && n->right == NULL;
}構造を活用する
ここでは小さな木を構築し、再帰的なヘルパーを使ってノード数と高さを報告します。
ヘルパーは固定された形状を前提としていない点に注目してください。再帰が実際のポインターをたどるため、どのような木にも対応できます。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *nn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
int count(Node *r){ return r? 1+count(r->left)+count(r->right):0; }
int height(Node *r){ if(!r) return -1; int l=height(r->left),x=height(r->right); return 1+(l>x?l:x); }
int main(void){
Node *root = nn(10);
root->left = nn(5); root->right = nn(15);
root->left->left = nn(2);
printf("nodes=%d height=%d\n", count(root), height(root));
return 0;
}クイックチェック
ノード構造についての理解度を確認しましょう。
まとめ
二分木のノードは、値と2つの自己参照ポインター（left、right）を保持します。子がない場合はNULLに設定します。
ノードはmallocで確保し、手作業でリンクして、再帰的に処理します。ノード数、 高さ、葉の判定では、NULLの確認が常にベースケースになります。
よくある質問
「木構造のノードと構造」レッスンは無料ですか？
はい。「木構造のノードと構造」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C Academyコースには全4レッスンが含まれています。
「木構造のノードと構造」で何を学びますか？
ポインターでノードをモデル化します。 ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
C Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのC Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「木構造のノードと構造」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このC Academyレッスンでコードを書いて実行できますか？
はい。すべてのC Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。