アルゴリズムとデータ構造編【データ構造】 第7章 二分木

先頭へ戻る

この章の概要

この章の概要です。


木構造

ここでは、木構造(ツリー)というデータ構造を紹介します。連結リスト(第3章)と同様に、非常に重要なデータ構造と言えます。

まず、木構造の概念図を見てください。

木構造

この概念図において、○の部分を節(ノード)と呼びます。各節が線で結ばれていることが分かると思いますが、この線の部分をと呼びます。この概念図で、上下を逆さまにしてみれば、木のような形をしていることが分かると思います。これが木構造と呼ばれる由来です。

ここで、ある節から見て、その1つ下にある節のことをと呼び、逆に1つ上の節をと呼びます。

この辺りの用語は、家系図を見るように考えればいい訳です。兄弟、従弟、先祖、子孫などの用語もあります。ちなみに「兄弟」は brother ではなく sibling の方です。

一番上にある節のことを根(ルート)と呼び、一番下にある節のことをと呼びます。根は、常に1つしかありませんが、葉は複数あるかもしれません。なお、葉のことを外部ノード、葉以外の節を内部ノードと呼ぶことがあります。

また、木には高さ(深さ)という概念があります。これは、根から一番遠い葉までに通過する枝の個数によって表現されます。

1つの節が、2つ以下の子を持つような木構造を二分木(バイナリツリー)と呼び、この章のテーマになっています。最初の概念図では、根の下に子が3つあるので、これは二分木ではありません。

1つの節が、3つ以上の子を持つ木構造も考えられます。これは、多分木と呼ばれています。

1つの節が、1つしか子を持たない場合、これはもはや木構造とは呼べないような形になります。なぜなら、そのような構造は連結リストそのものであるためです。木構造に要素を追加していくとき、節を置く位置を誤ると、このような状態になってしまうことがあります。大抵の場合、これは性能を悪化させる結果になるので、避けなければならないことです。

二分木

二分木とは、葉以外のすべての節が、2つ以下の子を持つような木構造のことです。 もし、必ず2つの子を持つようならば、全二分木と呼ばれます。さらに、どの葉も同じ深さにある場合は、完全二分木と呼ばれます。

概念図は次のようになります。

二分木

この概念図は、葉以外のすべての節が子を必ず2つずつ持っており、どの葉も同じ深さにあるので、完全二分木になっていると言えます。

C言語のプログラムとしては、二分木を次のように表現します。

struct Node_tag {
    int                   value;
    struct Node_tag*      left;
    struct Node_tag*      right;
};

この構造体の変数1つが、1つの節を表します。つまり、節の数だけ変数が作られ、すべてを合わせて1つの木構造を表現します。

この構造体の中で、value というメンバは、この節に置かれた具体的なデータを表すもので、もちろん int型である必要はなく、任意のデータを任意の数だけ置けます。

left と right というメンバは、先ほどの概念図において、自分自身の1つ下にある2つの節への枝を表しています。C言語なのでポインタ変数を使えば枝を表現できます。

余談ですが、この構造体をよく観察すると、双方向連結リスト(第4章)の構造体とまったく同じ形をしていることが分かります。違いは、next と prev という名前のポインタが、left と right に変わっただけです。つまり、データの形が一緒でも、それをどう扱うかによって、実現される内容はまったく異なってくるということです。

この構造体を見ると分かるように、親に向かうポインタ変数を持っていません。もちろん、ポインタ変数を1つ付け加えれば、親をたどれますが、その必要性がないのなら不要です。木構造は、根からその子をたどることを繰り返して、目的の節へ行き着くというように利用されることが多く、親をたどる必要性がない場合もよくあります。

再帰的な性質

次の図は、二分木の概念図に、赤い枠を加えたものです。

二分木

二分木を形作る一部分を囲った訳ですが、この囲まれた部分だけを単独で観察してみても、その部分もやはり二分木になっていることが分かります。このように、木構造はその一部分だけを取り出してみても、やはり木構造の形をしているという特徴があります。これを部分木と呼びます。

この概念図の場合、全体としての根の右側にある部分木を囲っていますが、この場合、根に対して右部分木と呼びます。左側にあれば左部分木と呼ばれます。

もっと大きな木構造であれば、部分木の中にさらに部分木が、その中にさらに部分木があるという構造になります。このように、自分自身の一部が、自分自身と同じ形状をしているような構造は、再帰的な構造と呼ばれます。

データ構造が再帰的になっているのであれば、プログラムも再帰処理を活用しやすくなります。次の項で、すべての節を調べつくす処理を取り上げますが、ここでは再帰処理を利用しています。


走査

二分木に含まれるすべての節を調べたいとします。このような処理を、走査(トラバース)と呼びます。ここで重要な点は、「すべてをもらさず」「同じものを重複せず」に調べつくすことです。

二分木に対する走査の方法には、大きく分けると、深さ優先探索幅優先探索の2つがあります。前者はさらに、行きがけ順探索通りがけ順探索帰りがけ順探索に分類できます。これらは、調べる節の順序が異なります。

深さ優先探索では、根から始めて、葉に行き着くまで子をたどっていきます。葉まで行き着いたら、その親に戻り、別の子の方を調べに行き、やはり葉までたどります。これを繰り返せば、いずれすべての節を調べられます。

ここで、行きがけ順探索、通りがけ順探索、帰りがけ順探索の違いは、根とその2つの子をどんな順序で調べるかです。

行きがけ順探索では、根→左の部分木→右の部分木の順で調べます

通りがけ順探索では、左の部分木→根→右の部分木の順で調べます

帰りがけ順探索では、左の部分木→右の部分木→根の順で調べます

幅優先探索の方は、まず根を調べ、次に1つ深い階層の左部分木、右部分木を調べます。1つの階層の節をすべて網羅してから、次の階層へ降りることを繰り返します

実際に、それぞれの走査を実装してみましょう。

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

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))


/* コマンド */
enum Cmd_tag {
    CMD_PRE_ORDER,
    CMD_IN_ORDER,
    CMD_POST_ORDER,
    CMD_EXIT,

    CMD_NUM
};

/* コマンド文字列の種類 */
enum CmdStr_tag {
    CMD_STR_SHORT,
    CMD_STR_LONG,

    CMD_STR_NUM
};

/* コマンドの戻り値 */
enum CmdRetValue_tag {
    CMD_RET_VALUE_CONTINUE,
    CMD_RET_VALUE_EXIT,
};

/* コマンド文字列 */
static const char* const CMD_STR[CMD_NUM][CMD_STR_NUM] = {
    { "r", "pre" },
    { "i", "in" },
    { "p", "post" },
    { "e", "exit" }
};


/* 二分木 */
struct Node_tag {
    int                   value;
    struct Node_tag*      left;
    struct Node_tag*      right;
};
typedef struct Node_tag* BinaryTree;


static BinaryTree create_binary_tree(void);
static void delete_binary_tree(BinaryTree tree);
static void print_explain(void);
static void print_blank_lines(void);
static enum CmdRetValue_tag get_cmd(void);
static enum CmdRetValue_tag cmd_pre_order(void);
static enum CmdRetValue_tag cmd_in_order(void);
static enum CmdRetValue_tag cmd_post_order(void);
static enum CmdRetValue_tag cmd_exit(void);
static void pre_order(BinaryTree tree);
static void in_order(BinaryTree tree);
static void post_order(BinaryTree tree);
static void get_line(char* buf, size_t size);


/* コマンド実行関数 */
typedef enum CmdRetValue_tag (*cmd_func)(void);
static const cmd_func CMD_FUNC[CMD_NUM] = {
    cmd_pre_order,
    cmd_in_order,
    cmd_post_order,
    cmd_exit
};


static BinaryTree gTree;


int main(void)
{
    gTree = create_binary_tree();

    while( 1 ){
        print_explain();

        if( get_cmd() == CMD_RET_VALUE_EXIT ){
            break;
        }

        print_blank_lines();
    }

    delete_binary_tree( gTree );

    return 0;
}

/*
    二分木を作成

    ここでは、
             0
            / \
           1   6
          / \
         2   3
            / \
           4   5

    という形の二分木を作っている。
*/
BinaryTree create_binary_tree(void)
{
    int i;
    BinaryTree node[7];

    for( i = 0; i < SIZE_OF_ARRAY(node); ++i ){
        node[i] = malloc( sizeof(struct Node_tag) );
        node[i]->value = i;
    }

    node[0]->left = node[1];
    node[0]->right = node[6];

    node[1]->left = node[2];
    node[1]->right = node[3];

    node[2]->left = NULL;
    node[2]->right = NULL;

    node[3]->left = node[4];
    node[3]->right = node[5];

    node[4]->left = NULL;
    node[4]->right = NULL;

    node[5]->left = NULL;
    node[5]->right = NULL;

    node[6]->left = NULL;
    node[6]->right = NULL;

    return node[0];
}

/*
    二分木を削除
*/
void delete_binary_tree(BinaryTree tree)
{
    if( tree == NULL ){
        return;
    }

    delete_binary_tree( tree->left );
    delete_binary_tree( tree->right );
    free( tree );
}

/*
    説明文を出力
*/
void print_explain(void)
{
    puts( "コマンドを入力してください。" );
    printf( " 行きがけ順探索: %s (%s)\n", CMD_STR[CMD_PRE_ORDER][CMD_STR_SHORT], CMD_STR[CMD_PRE_ORDER][CMD_STR_LONG] );
    printf( " 通りがけ順探索: %s (%s)\n", CMD_STR[CMD_IN_ORDER][CMD_STR_SHORT], CMD_STR[CMD_IN_ORDER][CMD_STR_LONG] );
    printf( " 帰りがけ順探索: %s (%s)\n", CMD_STR[CMD_POST_ORDER][CMD_STR_SHORT], CMD_STR[CMD_POST_ORDER][CMD_STR_LONG] );
    printf( " 終了する: %s(%s)\n", CMD_STR[CMD_EXIT][CMD_STR_SHORT], CMD_STR[CMD_EXIT][CMD_STR_LONG] );
    puts( "" );
}

/*
    空白行を出力
*/
void print_blank_lines(void)
{
    puts( "" );
    puts( "" );
}

/*
    コマンドを受け付ける
*/
enum CmdRetValue_tag get_cmd(void)
{
    char buf[20];
    enum Cmd_tag cmd;
    int i;

    get_line( buf, sizeof(buf) );

    cmd = CMD_NUM;
    for( i = 0; i < CMD_NUM; ++i ){
        if( strcmp( buf, CMD_STR[i][CMD_STR_SHORT] ) == 0
         || strcmp( buf, CMD_STR[i][CMD_STR_LONG] ) == 0
        ){
            cmd = i;
            break;
        }
    }

    if( 0 <= cmd && cmd < CMD_NUM ){
        return CMD_FUNC[i]();
    }
    else{
        puts( "そのコマンドは存在しません。" );
    }

    return CMD_RET_VALUE_CONTINUE;
}

/*
    preコマンドの実行
*/
enum CmdRetValue_tag cmd_pre_order(void)
{
    puts( "行きがけ順探索で、節の値を書き出します。" );
    pre_order( gTree );

    return CMD_RET_VALUE_CONTINUE;
}

/*
    inコマンドの実行
*/
enum CmdRetValue_tag cmd_in_order(void)
{
    puts( "通りがけ順探索で、節の値を書き出します。" );
    in_order( gTree );

    return CMD_RET_VALUE_CONTINUE;
}

/*
    postコマンドの実行
*/
enum CmdRetValue_tag cmd_post_order(void)
{
    puts( "帰りがけ順探索で、節の値を書き出します。" );
    post_order( gTree );

    return CMD_RET_VALUE_CONTINUE;
}

/*
    exitコマンドの実行
*/
enum CmdRetValue_tag cmd_exit(void)
{
    puts( "終了します。" );

    return CMD_RET_VALUE_EXIT;
}

/*
    行きがけ順探索でトラバース
*/
void pre_order(BinaryTree tree)
{
    if( tree == NULL ){
        return;
    }

    printf( "%d\n", tree->value );
    pre_order( tree->left );
    pre_order( tree->right );
}

/*
    通りがけ順探索でトラバース
*/
void in_order(BinaryTree tree)
{
    if( tree == NULL ){
        return;
    }

    in_order( tree->left );
    printf( "%d\n", tree->value );
    in_order( tree->right );
}

/*
    帰りがけ順探索でトラバース
*/
void post_order(BinaryTree tree)
{
    if( tree == NULL ){
        return;
    }

    post_order( tree->left );
    post_order( tree->right );
    printf( "%d\n", tree->value );
}

/*
    標準入力から1行分受け取る

    受け取った文字列の末尾には '\0' が付加される。
    そのため、実際に受け取れる最大文字数は size - 1 文字。

    引数:
        buf:    受け取りバッファ
        size:   buf の要素数
    戻り値:
        buf が返される
*/
void get_line(char* buf, size_t size)
{
    fgets(buf, size, stdin);

    /* 末尾に改行文字があれば削除する */
    char* p = strchr(buf, '\n');
    if (p != NULL) {
        *p = '\0';
    }
}

二分木に持たせるデータは、create_binary_tree関数の中で固定的に作っています。図にすると、次のような形になっています。

二分木

この二分木に対して、行きがけ順探索を行うと、

行きがけ順探索で、節の値を書き出します。
0
1
2
3
4
5
6

通りがけ順探索を行うと、

通りがけ順探索で、節の値を書き出します。
2
1
4
3
5
0
6

帰りがけ順探索を行うと、

帰りがけ順探索で、節の値を書き出します。
2
4
5
3
1
6
0

というように出力されます。

それぞれの走査は、行きがけ順探索は pre_order関数、通りがけ順探索は in_order関数、帰りがけ順探索は post_order関数の中で行っています。これらの実装を見ると分かるように、すべて再帰処理(C言語編第53章参照)が行われています。

再帰的な性質」のところで説明したように、木構造は再帰的な構造をしており、再帰処理を活用すれば、短いコードで大きな仕事を行えます。これらの走査関数がいずれも、非常に短いコードで実装されていることが分かると思います。

最後に、delete_binary_tree関数も確認しておきましょう。create_binary_tree関数の中で二分木を作るとき、各節を malloc関数で確保したメモリに作っているので、削除するときには free関数を呼ぶ必要があります。問題はそれを呼ぶ順番です。

子よりも先に親を解放してしまうと、親が持っていた left と right へのアクセスは不正なものになってしまうので、必ず先に子を解放しなければなりません。そのためには、帰りがけ順探索と同じ順序で処理を行うのが適切です。帰りがけ順探索ならば、「左の子→右の子→親」の順番でアクセスされるからです。

これらの走査方法は、どれが優れているということはありませんが、delete_binary_tree関数の説明のところで触れたように、結果として都合の良い方法というものはあるので、一応、どういう順序で節が参照されるのかは理解しておきましょう。

まとめ

この章では、木構造の概要を学び、代表例として二分木を取り上げました。しかし、これだけでは具体的に、どのような処理に利用すればいいのか分からないでしょう。

二分木にはいくつか代表的な応用があり、その中でも最も代表的な二分探索木次章で解説します。二分木は、こういった応用的な事例を理解すると、その価値が分かります。


練習問題

問題① 二分木の高さを返す関数を作成してください。

問題② 幅優先探索による走査を行う関数を実装してください。


解答ページはこちら


参考リンク



更新履歴

'2018/2/22 要素数を意味している「サイズ」について、「要素数」に表記を改めた。

'2018/2/12 サンプルプログラムの改善(fgets が受け取った改行文字の削除の方法を修正。const、static の付加)

'2017/11/13 サンプルプログラムで、存在しないコマンドが入力されたときに、未初期化の変数を参照していたのを修正。

'2015/12/27 SIZE_OF_ARRAYマクロの定義を修正。

'2015/2/21 サンプルプログラムで、ファイルスコープでよい関数に static を付加。

≪さらに古い更新履歴を展開する≫



前の章へ (第6章 キュー)

次の章へ (第8章 二分探索木)

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ


はてなブックマーク Pocket に保存 Twitter でツイート Twitter をフォロー
Facebook でシェア Google+ で共有 LINE で送る rss1.0 取得ボタン RSS
管理者情報 プライバシーポリシー