2.1 ツリー構造

2 C言語でのツリー構造

2.1 ツリー構造

C言語でツリー構造を実装する方法を教科書 [1]のList 6-1(p.169)～ List 6-4(p.176-180)のプログラムをつかって説明する(転載について)．このプログラムのツリー構造は，図2のようになっている．このデータ構造をC言語で取り扱うことにする．そのためには，以下のようなことが必要である．

ノードを表す構造体の定義
ノードの追加(ノードの作成を含む)
ノードのサーチ(探索)
ノードの削除(メモリーの解放を含む)

これらのことを，説明する．

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

2.1.1 ノードを表す構造体

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

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

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

リスト1 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)を入れておく．最初はルートがないため，それを表すポインターは意味が無いためである．

2.1.2 ノードの作成

データである整数値を引数に取るノード生成の関数は，リスト 2の通りである．この関数の動作は，以下の通りである．

malloc関数でノードを表す構造体(型はtree_node)ひとつ分のメモリーを確保する．そして，確保されたメモリーの先頭アドレスをtree_newというポインターに代入している．
メモリーの確保に失敗すると，tree_newはNULLポインターとなる．確保に失敗した場合は，exit関数によりプログラムを終了する．
メモリーの確保に成功したならば，ノードを表す構造体のメンバーに初期値を与える．
- 左側の子を示すポインターleftには，NULLポインターを代入する．これは，まだ子が未定なのでこのポインターは意味がないと言うことを明記している．
- 右側の子を示すポインターleftも，NULLポインターを代入する．
- メンバーvalueには，ノードの値numを代入する．

リスト2 2分木のノードの作成．教科書List 6-2の一部(転載について)

   1 tree_node* create_new_node(int num)
   2 {
   3     tree_node *tree_new;
   4 
   5     /* 新しいnodeを作成して，初期化する */
   6     tree_new=(tree_node*)malloc(sizeof(tree_node));
   7     if(tree_new==NULL)
   8         exit(EXIT_FAILURE);
   9     tree_new->left=NULL;
  10     tree_new->right=NULL;
  11     tree_new->value=num;
  12 
  13     return tree_new;
  14 }

2.1.3 ノードの追加

ノードを追加する関数は，リスト3の通りである．この関数の引数は2つで，

追加する整数データ(num)
追加するノードの親を表すポインター(*node)．最初に関数を呼び出すときには，ルートのポインターを与える(教科書 List 6-4のp.180参照)．

である．戻り値は無い(void)．

リスト3の動作は，以下の通りである．

ポインターnodeが何も示していない(NULL)ならば，新たにノードを作成(creat_new_node(num))して，メモリーの先頭アドレスをルートを示すポインター(tree_root)に代入する(4-8行)．これが実行されるのは， nodeがルートを示すポインター(tree_root)の場合に限る．次に示す再帰呼び出しで呼び出された場合にはnodeはNULLにならない．
nodeがNULLとならない場合，ノードの値(node->value)と追加する値(num)の大小関係により，2つの場合に分けられる．
- ノードの値(node->value) 追加する値(num) 要するにノードの左側の子になる可能性がある場合である(12-18行)．
  - もし左側の子があれば(node->left!=NULL)，左側の子を親として再帰呼び出しをする．
  - 子が無ければ(else)，新たにノードを作成して，それを左側の子にする．
- さもなければ(else) 要するにノードの右側の子になる可能性がある場合である(21-27行)．
  - もし右側の子があれば(node->right!=NULL)，右側の子を親として再帰呼び出しをする．
  - 子が無ければ(else)，新たにノードを作成して，それを右側の子にする．

リスト3 2分木のノードの追加．教科書List 6-2の一部(転載について)

   1 void insert_tree(int num,tree_node *node)
   2 {
   3     /* 1つも挿入されていない場合 */
   4     if(node==NULL)
   5     {
   6         tree_root=create_new_node(num);
   7         return;
   8     }
   9 
  10     /* numが現在のnodeの値よりも小さい場合 */
  11     if(node->value>num)
  12     {
  13         if(node->left!=NULL)
  14             insert_tree(num,node->left);
  15         else
  16             /* 左側に追加する */
  17             node->left=create_new_node(num);
  18     }
  19     else
  20     /* numが現在のnodeの値以上の場合 */
  21     {
  22         if(node->right!=NULL)
  23             insert_tree(num,node->right);
  24         else
  25             /* 右側に追加する */
  26             node->right=create_new_node(num);
  27     }
  28 
  29     return;
  30 }

2.1.4 ノードのサーチ

ノードを探索する関数は，リスト4の通りである．この関数の引数は2つで，

探索するノードを表すポインター(*node)．最初に関数を呼び出すときには，ルートのポインターを与える(教科書 List 6-4のp.180参照)．
追加する整数データ(val)

である．戻り値は，探索で整数データ(val)と一致するノードがあった場合，そのノードのポインター(node)を返す．見つからなかった場合は，NULLポインターを返す．

リスト4の動作は，以下の通りである．要するにルートから，大小関係を調べて，ツリーをたどって探索をしているのである．

ノードの値(node->value) 探索する値(num) 要するにノードの左側の子と一致する可能性がある場合である(6-10行)．
- もし左側の子が無ければ(node->left==NULL)，一致するデータは無いので，NULLポインターを返して，探索は終了．
- 左側に子があれば，それを探索するノードとし，再帰呼び出しする．．
ノードの値(node->value) 探索する値(num) 要するにノードの右側の子と一致する可能性がある場合である(13-17行)．
- もし左側の子が無ければ(node->right==NULL)，一致するデータは無いので，NULLポインターを返して，探索は終了．
- 右側に子があれば，それを探索するノードとし，再帰呼び出しをする．
上の2つに当てはまらなければ，それは ノードの値(node->value) = 探索する値(num) の場合である．探索のデータが見つかったので，ノードのポインターを返す．

リスト4 2分木のサーチ．教科書List 6-3(転載について)

   1 tree_node* find_value(tree_node* node,int val)
   2 /* 発見したtree_nodeのポインタを返す。ない場合はNULL */
   3 {
   4     /* 自分より小さい値ならば，左側 */
   5     if(node->value>val)
   6     {
   7         if(node->left==NULL)  /* もし左側になければ，valはない */
   8             return NULL;
   9         return find_value(node->left,val);
  10     }
  11     /* 自分より大きい値ならば，右側 */
  12     if(node->value<val)
  13     {
  14         if(node->right==NULL)
  15             return NULL;      /* もし右側になければ，valはない */
  16         return find_value(node->right,val);
  17     }
  18 
  19     /* 見つかれば，見つかった値を返す */
  20     return node;
  21 }

2.1.5 ノードの削除

ノードを削除する関数は，リスト5の通りである．この関数の引数は1つで，削除するデータ(val)である．戻り値は整数で，削除成功ならば 1 を，削除すべきデータが無いならば 0 を返す．

この関数の動作に先立って，使われている変数の役割を示しておく．

node: 削除するべきか否か，調査しているノードを示すポインター．初期値は，ルート(tree_root)．
parent_node: 調査しているノードの親ノードを示すポインター．初期値は NULL ポインター．
left_biggest: 削除すべきノードの左側の子孫で最大の値をもつノードを示すポインター
direction: 削除すべきノードが左側の子(-1)か右側の子(1)かを示す整数．初期値は 0 である．

リスト4の動作は，以下の通りである．

削除すべきノードのサーチ(12-28行)
- 削除すべきノードが見つかったならば，そのノードをポインターnodeで示す．削除すべきノードの親ノードはポインターparent_nodeで示す． nodeが左の子の場合 direction=-1 で，右側の子の場合 direction=1 である．
- 削除すべきノードがない場合，node は NULL ポインターとして，呼び出し元へ 0 を返す．
削除すべきノードを削除
- 削除すべきノードの両方に子が無い，あるいは片方に子が無い場合．30行で判断し，31-56行で処理している．ここで，注意すべきは， direction=0の時である．これは，削除すべきノードがルートであることを示している．
- 削除すべきノードの両方に子がある場合．58-80行で処理している．
  - 左側の子孫の最大値を探索する(65-70行)．
  - 削除すべきノードの値を，左側の子孫の最大値を代入している(74 行)．左側の子孫の最大値を持つノードの親ノードのポインターを付け替えている(75-78行)．

リスト5 2分木の削除．教科書List6-4の一部(転載について)

   1 int delete_tree(int val)
   2 /* valを削除する。成功すれば1，失敗すれば0を返す */
   3 {
   4     tree_node *node,*parent_node;
   5     tree_node *left_biggest;
   6     int direction;
   7     node=tree_root;
   8     parent_node=NULL;
   9     direction=0;
  10 
  11     /* while文で削除すべき対象を見つける(find_valueと同じ) */
  12     while(node!=NULL&&node->value!=val)
  13     {
  14         if(node->value>val)
  15         {
  16             parent_node=node;
  17             node=node->left;
  18             direction=-1;       /* 親の左側 */
  19         }
  20         else
  21         {
  22             parent_node=node;
  23             node=node->right;
  24             direction=1;        /* 親の右側 */
  25         }
  26     }
  27     if(node==NULL)  /* 見つからなかった */
  28         return 0;
  29 
  30     if(node->left==NULL||node->right==NULL)
  31     {
  32         /* 左か右，どちらかがNULLであった場合
  33            (両方NULLの場合も含む) */
  34         if(node->left==NULL)
  35         {
  36             /* 親のポインタを変更する */
  37             if(direction==-1)
  38                 parent_node->left=node->right;
  39             if(direction==1)
  40                 parent_node->right=node->right;
  41             if(direction==0)
  42                 tree_root=node->right;
  43         }
  44         else
  45         {
  46             /* 親のポインタを変更する */
  47             if(direction==-1)
  48                 parent_node->left=node->left;
  49             if(direction==1)
  50                 parent_node->right=node->left;
  51             if(direction==0)
  52                 tree_root=node->left;
  53         }
  54 
  55         free(node);
  56     }
  57     else
  58     {
  59         /* 両者ともNULLでなかった場合 */
  60 
  61         /* nodeの左側の最も大きな値（最も右側の値）を取得する */
  62         left_biggest=node->left;
  63         parent_node=node;
  64         direction=-1;
  65         while(left_biggest->right!=NULL)
  66         {
  67             parent_node=left_biggest;
  68             left_biggest=left_biggest->right;
  69             direction=1;
  70         }
  71 
  72         /* left_biggestの値をnodeに代入し，
  73            left_biggestは左側の枝を入れる */
  74         node->value=left_biggest->value;
  75         if(direction==-1)
  76             parent_node->left=left_biggest->left;
  77         else
  78             parent_node->right=left_biggest->left;
  79         free(left_biggest);
  80     }
  81 
  82     return 1;
  83 }

2.1.6 メモリーの解放

メモリーを解放する関数は，リスト6の通りである．引数で渡されたポインターが示すノードとその子孫が使っているメモリーを解放している．

リスト6 メモリーの解放．教科書List6-4の一部(転載について)

   1 void free_tree(tree_node* node)
   2 {
   3     if(node==NULL)
   4         return;
   5     /* まず子nodeのメモリを解放する */
   6     free_tree(node->left);
   7     free_tree(node->right);
   8     /* 自分自身を解放 */
   9     free(node);
  10 }

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

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

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

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

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

[Previous: 1 本日の学習内容] [Up: ツリー構造(その2)] [Next: 3 多数の子を持つツリー]
[Top:ページの先頭に戻る]

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

no counter

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