自己参照構造体を使った二分木による単語の並べ替えと出現数を計算するプログラムを書いたのは R. Haight であり，C のコンパイラを最初に作成した Dennis M. Ritchie によるマニュアル C Reference Manual (1975) に掲載された C のプログラム例です。
「二分木（binary tree）」とは，連結リストにおいて「データ」と呼んだものを「ノード」と読み直し，各ノードが２つのポインタをもち，一つが左，もう一つが右を意味する形でデータが繋がったものです。ここでは，二分木を使ったソート（並べ替え）を見ます。
次の数字を降順に並び替える場合を考えましょう。
78, 85, 79, 98, 87, 90, 95, 99, 97, 92
先ず，出発点のノードに 0 と打ちます。そのアドレス番号が 0x442b0 であったとしましょう。枝を２つ這わせ各ノードに NULLポインタを入れます。そこで，78 を読み込み，ノード 0 から出発します。78 は 0 より大きいので，左の枝に分岐し，NULLポインタに至ったノードに 78 と打ち，そこから２つの枝を這わせ各ノードに NULLポインタを入れます。ノード 78 のアドレスが角括弧内の数値で書いてあります。
[0x442b0] 0 .---------. [0x0]
|
|
|
[0x442c0] 78 .---------. [0x0]
|
|
|
[0x0] .
２つ目の 85 ですが，0 より大きいので左，78 より大きいので左です。すると，NULLポインタに至るので，そのノードに 85 と入れ，そこから２つの枝を這わせ各ノードに NULLポインタを入れます。NULLポインタでないときは，ノード番号と比較し，それより大きい場合には左，小さい場合には右へ進み，NULLポインタならばノードに数値を入れ，そこから NULLポインタを２つ打つという訳です。このようにして行くと，次のような木が出来上がります。
[0x442b0] 0 .---------. [0x0]
|
|
|
[0x442c0] 78 .---------. [0x0]
|
|
| 79 [0x442e0]
[0x442d0] 85 .---------.---------. [0x0]
| |
| |
| |
| [0x0] .
| 87 [0x44300]
[0x442f0] 98 .-----------------.---------. [0x0]
| |
| |
| |
| [0x44310] 90 .---------. [0x0]
| |
| |
| | 92 [0x44350]
| [0x44320] 95 .---------------.---------. [0x0]
| | |
| | |
| | |
| | . [0x0]
| |
| [0x44340] 97 .---------. [0x0]
| |
| |
| |
| . [0x0]
[0x44330] 99 .---------. [0x0]
|
|
|
[0x0] .
出来上がった木を左奥から読み上げると，数値が降順に並びます。
/* Example 18.5 */
#include <stdlib.h>
#include <stdio.h>
struct tnode {
int n;
struct tnode *left, *right;
};
struct tnode *createNode (int);
struct tnode *insertNode (struct tnode *, int);
void printTree (struct tnode *);
int main(void)
{
int i;
int x[10] = {78, 85, 79, 98, 87, 90, 95, 99, 97, 92};
struct tnode *top;
top = createNode(0);
for (i = 0; i < 10; i++)
top = insertNode(top, x[i]);
printTree(top);
exit(0);
}
struct tnode *createNode (int num)
{
struct tnode *node;
if ((node = malloc(sizeof(struct tnode))) == NULL) {
fprintf(stderr, "malloc\n");
exit(1);
}
node -> n = num;
node -> left = NULL;
node -> right = NULL;
return node;
}
struct tnode *insertNode (struct tnode *node, int num)
{
if (!node) {
node = createNode(num);
return node;
}
if (num > node -> n)
node -> left = insertNode(node -> left, num);
if (num < node -> n)
node -> right = insertNode(node -> right, num);
return node;
}
void printTree (struct tnode *node)
{
struct tnode *tmp;
tmp = node;
while (tmp) {
printTree(tmp -> left);
printf("n = %d\t[%p] -> [%p, %p]\n",
tmp -> n, tmp, tmp -> left, tmp -> right);
tmp = tmp -> right;
}
}
実行結果です。角括弧内はアドレスです。
n = 99 [0x44330] -> [0x0, 0x0] n = 98 [0x442f0] -> [0x44330, 0x44300] n = 97 [0x44340] -> [0x0, 0x0] n = 95 [0x44320] -> [0x44340, 0x44350] n = 92 [0x44350] -> [0x0, 0x0] n = 90 [0x44310] -> [0x44320, 0x0] n = 87 [0x44300] -> [0x44310, 0x0] n = 85 [0x442d0] -> [0x442f0, 0x442e0] n = 79 [0x442e0] -> [0x0, 0x0] n = 78 [0x442c0] -> [0x442d0, 0x0] n = 0 [0x442b0] -> [0x442c0, 0x0]
