4 ツリー構造

4.1 ツリー構造とは

同じような複数のデータを表す場合，配列やリスト，スタック，キューのようなデータ構造を使うことを学習してきた．これらのデータ構造では，階層をもつデータの集まりを表すことは，困難である．このように階層構造をもつデータを処理するときに威力を発揮するのがツリー構造である．ツリーとは，tree(木)のことである．

ツリー構造にはいろいろ名称があり，それを表1と図 4に示す．なぜ，図6のようなデータ構造をツリー構造と呼ぶか?．それは，この図を反対にしてみるのである．すると，根が一番下にきて，枝や葉が上にあることが分かるであろう．まさに，木である．

**表 1:** ツリー構造の名称
構成要素	内容
ルート(root:根)	最上位のノード
ノード(node:節)	枝が分かれるところ
リーフ(leaf:葉)	子がないノード
ブランチ(branch:枝)	親と子を結ぶ線
親(parent)	上のノード
子(child)	下のノード
兄弟(brother)	同じ親を持つノード

**図 4:** ツリー構造．図中の親子関係はノード`E`を基準にしている．
$\includegraphics[keepaspectratio,scale=0.8]{figure/tree_structure.eps}$

4.2 2分木

木構造のうち，各ノードの子どものノードが最大2つのようなものを2分木と言う．そして，ある規準に従ってその2分木が作られている場合，2分探索木(binary search tree)と呼ばれる．この構造のあるノードの左側と右側はそれぞれの子を頂点とする木構造になる．この子孫に対しても，同じ規準が適用されれるので，再帰による処理が可能となる．

特に有用な2分探索木は，大小関係を表すもので，

左側の子孫は，自分より必ず小さい．
右側に子孫は，自分より必ず大きい．

である．図は，2分探索木になっている．

**図 5:** ツリー構造(2分探索木)
$\includegraphics[keepaspectratio,scale=1.0]{figure/B_tree.eps}$

4.3 ノードを表す構造体

図6が2分木のツリー構造である．一つのノードは，データとその2つの子を表すポインターからなる．このように複数の異なる型のデータから成る情報を表すためには，構造体を用いる．その構造体をリスト5に示す．

このツリー構造を使うためには，型宣言として以下のものが必ず必要である．

ノードを表す構造体: データと子を示すポインターから構成され，ノードを表す．
ルートを表すポインター: ツリー構造のデータをたどるために，ルートを示すポインターが必ず必要である．

リスト5 2分木のノードを表す構造体．教科書のList 6-1(転載について)

   1 typedef struct _tag_tree_node
   2 {
   3     /* このノードが保持する値 */
   4     int value;
   5     /* 自分より小さい値のnode：図では左側のノード */
   6     struct _tag_tree_node *left;
   7     /* 自分より大きい値のnode：図では右側のノード */
   8     struct _tag_tree_node *right;
   9 } tree_node;

ツリーはノードのみならず，ルートを表すポインターが必要である．教科書のList 6-4(p.176)のように，

	tree_node *tree_root=NULL;

とそのポインターを宣言しておく．もちろん，これはノードを表す構造体のよりも後で宣言する必要がある．先に宣言すると，tree_nodeという型がコンパイラーが分からないからである．また，初期値は意味のないポインター(NULL)を入れておく．最初はルートがないため，それを表すポインターは意味が無いためである．

**図 6:** 教科書 List6-1～List 6-4のツリー構造
$\includegraphics[keepaspectratio,scale=0.9]{figure/tree.eps}$

4.4 練習問題

[問1]

図の中で2分探索木になっているものはどれか?

$\includegraphics[keepaspectratio, scale=0.8]{figure/B_Q1.eps}$
(ア)

$\includegraphics[keepaspectratio, scale=0.8]{figure/B_Q2.eps}$
(イ)

$\includegraphics[keepaspectratio, scale=0.8]{figure/B_Q3.eps}$
(ウ)

$\includegraphics[keepaspectratio, scale=0.8]{figure/B_Q4.eps}$
(エ)

[問2]

最初はデータが無く，以下の並びでデータが追加される．2分探索木を作成せよ．

69,26,36,45,89,65,11,12,14,23,44

[問3]

図の2分探索木にデータを追加する．以下の問いに答えよ．

70,73,67,75,77,66と順に追加する．

$\includegraphics[keepaspectratio, scale=0.8]{figure/Q_add_data.eps}$
データを追加する2分木

[問4]

図の2分探索木にデータを削除する．以下の問いに答えよ．

52,46,54と順に削除する．

$\includegraphics[keepaspectratio, scale=0.8]{figure/Q_del_data.eps}$
データを削除する2分木

[問5]

2分木のノードを示す構造体を書け．

[転載について]
このページ中のリスト5のプログラムは，教科書として使用している以下の書籍

書名プログラミングの宝箱　アルゴリズムとデータ構造 ISBN4-7973-2419-8

著作者紀平拓男・春日伸弥

出版社ソフトバンク　パブリッシング株式会社

から転載しました．この転載に関しては，著者と版元に許諾を得ています．

[Previous: 3 再帰呼び出し] [Up: これまでの復習(学年末試験に向けて)] [Next: 5 浮動小数点と数値計算]
[Top:ページの先頭に戻る]

ホームページ: Yamamoto's laboratory
著者: 山本昌志
Yamamoto Masashi
2006-02-27

no counter

書名	プログラミングの宝箱　アルゴリズムとデータ構造 ISBN4-7973-2419-8
著作者	紀平拓男・春日伸弥
出版社	ソフトバンク　パブリッシング株式会社