アルゴリズムとデータ構造編【データ構造】 第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* 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);


/* コマンド実行関数 */
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
};


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];
	size_t len;
	enum Cmd_tag cmd;
	int i;

	fgets( buf, sizeof(buf), stdin );

	len = strlen( buf );
	buf[len - 1] = '\0';  /* fgets関数が受け取った改行文字を消す */

	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 );
}

二分木に持たせるデータは、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関数の説明のところで触れたように、結果として都合の良い方法というものはあるので、 一応、どういう順序で節が参照されるのかは理解しておきましょう。

まとめ

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

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


練習問題

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

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


解答ページはこちら


参考リンク

更新履歴

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

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

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

'2014/12/20 サンプルプログラムで、コマンド処理の方法を整理。

'2013/4/17 サンプルプログラム中で、通りがけ順、行きがけ順の実装が間違っていたのを修正。

'2012/7/8 新規作成。



前の章へ

次の章へ

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

Programming Place Plus のトップページへ