走査
中順、前順、後順走査を学びます。
「走査」はCoddyKit上の無料C Academyレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはC Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C Academyコースには全4レッスンが含まれています。
トラバーサルとは
トラバーサルとは、木のすべてのノードを1回ずつ体系的に訪問する方法です。
典型的な深さ優先の順序には、in-order、pre-order、post-orderの3つがあります。違いは、部分木に対して現在のノードを処理するタイミングだけです。
In-Orderトラバーサル
In-orderでは、左部分木、ノード、右部分木の順に訪問します。
BSTでは値が昇順に出力されるため、探索木に最も役立つトラバーサルです。
void in_order(Node *root) {
if (root == NULL) return;
in_order(root->left);
printf("%d ", root->value);
in_order(root->right);
}Pre-Orderトラバーサル
Pre-orderでは、最初にノードを訪問し、次に左部分木、右部分木の順に訪問します。
ルートが子ノードより先に出力されるため、木のコピーや前置記法の式の生成に便利です。
void pre_order(Node *root) {
if (root == NULL) return;
printf("%d ", root->value);
pre_order(root->left);
pre_order(root->right);
}Post-Orderトラバーサル
Post-orderでは、最初に両方の部分木を訪問し、最後にノードを訪問します。
子ノードを親ノードより先に処理するため、木を解放するときにまさに必要な順序です。これにより、子ノードがなくなった後にノードを使うことがありません。
void post_order(Node *root) {
if (root == NULL) return;
post_order(root->left);
post_order(root->right);
printf("%d ", root->value);
}共通するパターン
3つの深さ優先トラバーサルは、NULLのベースケース、左の子への再帰、右の子への再帰、訪問処理という同じ骨格を共有しています。
訪問処理を置く位置だけで、順序の名前が変わります。
/* visit position decides the order:
* pre : VISIT, left, right
* in : left, VISIT, right
* post : left, right, VISIT
*/In-Orderでソート順に出力
このプログラムは小さなBSTを構築してin-orderトラバーサルを実行し、値がソート順に出力される性質を示します。
挿入順序に関係なく、値は最小から最大の順に出力されます。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
if(!r) return cn(v);
if(v<r->value) r->left=insert(r->left,v);
else if(v>r->value) r->right=insert(r->right,v);
return r;
}
void in_order(Node *r){ if(!r) return; in_order(r->left); printf("%d ", r->value); in_order(r->right); }
int main(void){
Node *root=NULL;
int d[]={10,5,15,3,7,12};
for(int i=0;i<6;i++) root=insert(root,d[i]);
in_order(root);
printf("\n");
return 0;
}3つの順序を比較
ルートが10、左の子が5、右の子が15の木では、出力が異なります。
Pre-orderは10 5 15、in-orderは5 10 15、post-orderは5 15 10になります。ノードの値は同じで、訪問するタイミングだけが異なります。
/* 10
* / \
* 5 15
* pre : 10 5 15
* in : 5 10 15
* post: 5 15 10
*/Level-Orderトラバーサル
幅優先、つまりlevel-orderでは、上から下へ、レベルごとにノードを訪問します。これは自然な再帰処理ではなく、キューを使います。
まずルートをキューに入れ、その後ノードを繰り返し取り出して出力し、子ノードをキューに入れます。
void level_order(Node *root) {
if (!root) return;
Node *queue[100];
int head = 0, tail = 0;
queue[tail++] = root;
while (head < tail) {
Node *n = queue[head++];
printf("%d ", n->value);
if (n->left) queue[tail++] = n->left;
if (n->right) queue[tail++] = n->right;
}
}実際の処理を支えるトラバーサル
トラバーサルは、単に出力するだけでなく、すべてのノードに触れる必要がある処理のテンプレートです。
訪問処理を値の合計、最大値の検索、ノードのコピーなどに置き換えれば、同じ構造で処理できます。
int sum_tree(Node *root) {
if (root == NULL) return 0;
return root->value
+ sum_tree(root->left)
+ sum_tree(root->right);
}トラバーサルのコスト
どのトラバーサルも各ノードを1回ずつ訪問するため、ノード数nに比例する時間で実行されます。
再帰処理で使うスタック領域は木の高さに比例します。木が平衡している場合はlog(n)、最悪の場合はnです。
3つを一度に実行
このプログラムは同じ木に対してpre-order、in-order、post-orderを出力するため、結果を並べて比較できます。
print呼び出しの位置だけが変わることで、結果の並びがどのように変わるかに注目してください。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
void pre(Node *r){ if(!r) return; printf("%d ", r->value); pre(r->left); pre(r->right); }
void ino(Node *r){ if(!r) return; ino(r->left); printf("%d ", r->value); ino(r->right); }
void post(Node *r){ if(!r) return; post(r->left); post(r->right); printf("%d ", r->value); }
int main(void){
Node *root = cn(10);
root->left = cn(5); root->right = cn(15);
pre(root); printf("\n");
ino(root); printf("\n");
post(root); printf("\n");
return 0;
}簡単な確認
目的に合ったトラバーサルを選んでみましょう。
まとめ
深さ優先トラバーサルは同じ再帰構造を共有しており、訪問処理の位置によってpre-order、in-order、post-orderに分かれます。BSTのin-orderではソート順に出力され、解放にはpost-orderが安全です。
Level-orderは幅優先で、キューを使います。どの方法も各ノードを1回ずつ訪問するため、実行時間はO(n)です。
よくある質問
「走査」レッスンは無料ですか？
はい。「走査」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C Academyコースには全4レッスンが含まれています。
「走査」で何を学びますか？
中順、前順、後順走査を学びます。 ブラウザで直接実行するハンズオンコードでC Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
C Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのC Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「走査」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このC Academyレッスンでコードを書いて実行できますか？
はい。すべてのC Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。