Next Sec.: バックトラッキング Upper Sec.: 動的データ構造 Prev. Sec.: 線形リスト

木構造リスト（tree structured list）

木構造リスト（tree structured list）


ポインタによって木状に結合されたデータ構造

例：組織の系統図，数式の表現，探索木，LISPのS式，etc.

数式のリスト表現

２分探索木（binary search tree）




2分木の各節点（node）xに対して

• f(x):節点xの値
• S_l(x):xの左部分木
• S_r(x):xの右部分木

とする．すべての節点xに対して次の条件が成り立つとき，この木を２分探索木という．

yをS_l(x)の元、zをS_r(x)の元と仮定した時

f(y) < f(x) < f(z)

ランダムな入力に対する２分探索木の生成

入力例 49 22 35 67 82 10 58 45 ...

メインプログラム

#include <stdio.h>
#include <stdlib.h>

struct node {
        int    data;
        struct node     *left;
        struct node     *right;
};

struct node *searchtree(struct node *p, int x);

void main(void)
{
        struct node *root = NULL;
        int x;

        scanf("%d", &x);
        while (x > 0) {
                root = searchtree(root, x);
                scanf("%d", &x);
        }
}

木探索（登録）プロシージャ

struct node *searchtree(struct node *p, int x)
{
        if (p == NULL) {
                p = (struct node *)malloc(sizeof(struct node));
                p->data = x;
                p->left = NULL;
                p->right = NULL;
        } else if (x < p->data)
                p->left = searchtree(p->left, x);
        else if (x > p->data)
                p->right = searchtree(p->right, x);
        return(p);
}