(cache) データ構造：二分探索木［２］ ― トラバーサル

二分探索木［２］ ― トラバーサル

＜目次＞

3. トラバーサルの応用例（１）

6. 演習問題

＜概要＞ この資料では、二分探索木をトラバースするための手順を解説する。また、その基本的な応用として、二分探索木の内容を表示する関数とメモリ領域を解放する関数を実装する。

1. トラバーサルの手順（基礎）

【定義】二分探索木の根からスタートして、すべてのノードを巡回して根に戻ってくる処理を二分探索木の「トラバーサル」と呼ぶ。「走査」と呼ぶこともある。また、この処理を実行することを、二分探索木を「トラバースする」（「走査する」）と言うこともある。

二分探索木のトラバーサルは、単純な再帰的アルゴリズムによって実現できる。いま、ノードvを根とする部分木をトラバースしたかったとしよう。このとき、次のように処理すればよい。

ノードv（へのポインタ）がNULLのときには何もせずに終了する。
ノードv（へのポインタ）がNULLでないときには次のように処理する。
- ノードvの左部分木を（再帰的に）トラバースする。
- ノードvの右部分木を（再帰的に）トラバースする。

この手順は、次のような単純な再帰的プログラムによって実現できる。以下、ノードvを指すポインタ変数をpで表す。

void traverse( struct node * p ){
   if( p != NULL ){
      traverse(p->left);            /* 左部分木をトラバースする */
      traverse(p->right);           /* 右部分木をトラバースする */
   }
}

なお、このプログラムはトラバーサルの基本的な手順だけを示していて（すなわち、各ノードを巡回しているだけであって）、実質的な処理を何もしていない。従って、このままではまったく役に立たない。次節以降にて、このプログラムを土台に実質的な処理を組み込んでいく。

2. トラバーサルの種類

二分探索木のトラバーサルを利用するときには、各ノードに関する何らかの処理を前節のプログラムに組み込んで利用する。その処理の組み込み方には、次の三種類の方法がある。

2.1. 先行順（行きがけ順、先付け、pre-order）

各ノードを訪れた直後にノードに対する処理を実行する。言い換えると、再帰呼び出しを行う前にノードに関する処理を実行する。この方法を「先行順」のトラバーサルと言う。この場合のプログラムは次のようになる。

void traverse( struct node * p ){
   if( p != NULL ){
      pが指すノードに関する何らかの処理を行う;
      traverse(p->left);            /* 左部分木をトラバースする */
      traverse(p->right);           /* 右部分木をトラバースする */
   }
}

2.2. 中間順（通りがけ順、中付け、in-order）

左部分木のトラバースが完了した直後（右部分木のトラバースを実行する前）にノードに関する処理を実行する。この方法を「中間順」のトラバーサルと言う。この場合のプログラムは次のようになる。

void traverse( struct node * p ){
   if( p != NULL ){
      traverse(p->left);            /* 左部分木をトラバースする */
      pが指すノードに関する何らかの処理を行う;
      traverse(p->right);           /* 右部分木をトラバースする */
   }
}

2.3. 後行順（帰りがけ順、後付け、post-order）

左部分木や右部分木のトラバーサルを完了したあとにノードに関する処理を実行する。この方法を「後行順」のトラバーサルと言う。この場合のプログラムは次のようになる。

void traverse( struct node * p ){
   if( p != NULL ){
      traverse(p->left);            /* 左部分木をトラバースする */
      traverse(p->right);           /* 右部分木をトラバースする */
      pが指すノードに関する何らかの処理を行う;
   }
}

3. トラバーサルの応用例（１）

トラバーサルの応用例として、二分探索木の内容を表示する関数とメモリ領域を解放する関数を設計してみよう。

3.1. 内容表示関数

内容表示関数を作るには、先の土台となるプログラムに、pが指すノードの内容を表示する処理を追加するだけでよい。以下に、先行順のトラバーサルを利用した内容表示関数を示す。なお、関数名をdisplayとしているので、再帰呼び出しの関数名も（当然）displayに変更しなければならないことに注意して欲しい。

void display( struct node * p ){
  if( p != NULL ){
    printf("%p:[%d;%p,%p]\n", p, p->value, p->left, p->right);
    display(p->left);            /* 左部分木をトラバースする */
    display(p->right);           /* 右部分木をトラバースする */
  }
}

【参考】再帰的関数（再帰呼び出し）を理解するための要点。
〈要点１〉

「再帰呼び出しを行った先で何が行われるか」なんてことを考えちゃイケナイ。

〈要点２〉「ノードがたくさんある場合」を考える。

「再帰呼び出し『display(p->left);』によって左部分木の内容が正しく表示されるはすだ」と信じる。
「再帰呼び出し『display(p->right);』によって左部分木の内容が正しく表示されるはすだ」と信じる。
以上の信念のもとで、「display関数は二分探索木全体の内容を正しく表示するか？」と考える。

〈要点３〉「ノードがもっとも少ない場合（ノードが一つもない場合）」を考える。

「この場合にも正しく動作するか」と考える。
この場合、display関数は何も表示しないので、確かに正しい。

3.2. メモリ解放関数

メモリ解放関数を作るには、先の土台となるプログラムに、pが指すノードのメモリ領域を解放する処理を追加するだけでよい。ただし、次の点に注意しなければならない。

【注意】（参考：授業では、もう少し詳しく説明する。）

解放してしまったメモリ領域を参照してはならない。運良く動作したとしても、そのようなプログラムは論理的に間違っている。（注：これは、メモリ領域の解放に関して何度か注意してきたことである。）
先行順や中間順のトラバーサルを利用すると、上の注意事項に抵触してしまう。一方、後行順のトラバーサルを使用すると、この注意事項に抵触しない。

あるノードvのメモリ領域を解放するためには、そのノードの子孫たち（左部分木と右部分木に含まれるノード）のメモリ領域をすべて解放しきったあとで、ノードvのメモリ領域を解放しなければならない。そうしなければ、第一の注意事項に抵触してしまうことになる。これが先行順や中間順ではダメで、後行順ならば上の注意事項に抵触することなく解放できる理由である。以下に、後行順のトラバーサルを利用したメモリ解放関数を示す。

void freeTree( struct node * p ){
  if( p != NULL ){
    freeTree(p->left);           /* 左部分木をトラバースする */
    freeTree(p->right);          /* 右部分木をトラバースする */
    free(p);                     /* pが指すノードのメモリ領域を解放する */
  }
}

【参考】再帰的関数（再帰呼び出し）を理解するための要点。
〈要点１〉

「再帰呼び出しを行った先で何が行われるか」なんてことを考えちゃイケナイ。

〈要点２〉「ノードがたくさんある場合」を考える。

「再帰呼び出し『freeTree(p->left);』によって左部分木の各ノード（のメモリ領域）が正しく解放されるはすだ」と信じる。
「再帰呼び出し『freeTree(p->right);』によって左部分木の各ノード（のメモリ領域）が正しく解放されるはすだ」と信じる。
以上の信念のもとで、「freeTreeは二分探索木全体のノードを正しく解放するか？」と考える。

〈要点３〉「ノードがもっとも少ない場合（ノードが一つもない場合）」を考える。

「この場合にも正しく動作するか」と考える。
この場合、freeTree関数は何もしないので、確かに正しい。

【注意】メモリ解放関数に関して、もう一点注意しなければならないことがある。上記のfreeTree関数は、すべてのノードのメモリ領域を解放してくれるが、根を指すポインタ変数rootの値をNULLに設定してくれない。そのまま放置しておくと、解放してしまったメモリ領域をうっかり参照してしまう危険性がある。これに対処する方法として、次の二つが考えられる。

freeTree関数を実行したあと、ポインタ変数rootにNULLを代入する。
上記の処理を行うような関数を用意する。すなわち、freeTree関数を実行したあとポインタ変数rootにNULLを設定するといった処理を行う関数を用意する。

この授業では二番目の方法を採用する。以下に、上記の処理を行う関数を示す。

void freeAll( struct node * * rt ){
  freeTree(*rt);
  *rt = NULL;
}

3.3. 実行例

以下に、内容表示関数とメモリ解放関数を組み込んだプログラム例を示す。なお、二分探索木を構築する処理に関しては前回の資料で示したプログラムと同じ処理を行っている。

/**********************************************************************
 * ヘッダファイル
 **********************************************************************/
#include <stddef.h>                      /*-- NULL , size_t --*/
#include <stdio.h>                       /*-- printf関数    --*/
#include <stdlib.h>                      /*-- malloc関数    --*/

/**********************************************************************
 * 二分探索木のノードを表す自己参照構造体
 **********************************************************************/
struct node {
  int value;                             /*-- データ要素     --*/
  struct node * left;                    /*-- 左側の子供へのポインタ --*/
  struct node * right;                   /*-- 右側の子供へのポインタ --*/
};

/**********************************************************************
 * 基本操作関数（プロトタイプ宣言）
 **********************************************************************/
void init( struct node * * rt );                        /*-- 初期設定 --*/
void add( struct node * * rt, int val );                /*-- 追加 --*/ 
struct node* search( struct node * root, int val );     /*-- 検索 --*/

/**********************************************************************
 * その他の関数（プロトタイプ宣言）
 **********************************************************************/
void display( struct node * p );              /* 内容表示 */
void freeAll( struct node * * rt );           /* メモリ解放(main) */ 
void freeTree( struct node * p );             /* メモリ解放(sub)  */

/**********************************************************************
 * main関数
 **********************************************************************/
int main(void){
  int A[] = { 29, 13, 5, 19, 15, 47, 35, 33, 40, 51, 65, -1 }; 
  int i;

  struct node * root;          /* 二分探索木（の根）を指すポインタ変数 */

  /*-★ 二分探索木の初期設定 --*/
  init( &root );

  /*-★ 各A[i]を二分探索木に追加する --*/
  i = 0;
  while( A[i] > 0 ){ 
    add( &root, A[i] ); 
    i++;
  }

  /*-★ 二分探索木の内容を表示する --*/
  printf("root=%p\n", root);             /* 根へのポインタを表示 */
  display(root);                          /* 二分探索木の内容表示 */

  /*-★ メモリ領域を解放する --*/
  freeAll(&root);

  return 0;
}

/**********************************************************************
 * 基本操作関数（関数本体の定義）
 **********************************************************************/
/*-★ 初期設定関数 --*/
void init( struct node * * rt ){
  *rt = NULL;
}

/*-★ 追加関数（データ要素を追加する） --*/
void add( struct node * * rt, int val ){

   ... 省略（以前のプログラムと同じ） ...

}

/*-★ 検索関数（データ要素を検索する） --*/
struct node * search( struct node * root, int val ){

   ... 省略（以前のプログラムと同じ） ...

}

/**********************************************************************
 * その他の関数（関数本体の定義）
 **********************************************************************/
/*-★ 内容表示関数 --*/
void display( struct node * p ){
  if( p != NULL ){
    printf("%p:[%d;%p,%p]\n", p, p->value, p->left, p->right);
    display(p->left);            /* 左部分木をトラバースする */
    display(p->right);           /* 右部分木をトラバースする */
  }
}

/*-★ メモリ解放関数 --*/
void freeAll( struct node * * rt ){
  freeTree(*rt);
  *rt = NULL;
}

void freeTree( struct node * p ){
  if( p != NULL ){
    freeTree(p->left);            /* 左部分木をトラバースする */
    freeTree(p->right);           /* 右部分木をトラバースする */
    free(p);                      /* メモリ領域を解放する     */
  }
}

（実行結果）

root=0x804a050
0x804a050:[29;0x804a060,0x804a0a0]
0x804a060:[13;0x804a070,0x804a080]
0x804a070:[5;(nil),(nil)]
0x804a080:[19;0x804a090,(nil)]
0x804a090:[15;(nil),(nil)]
0x804a0a0:[47;0x804a0b0,0x804a0e0]
0x804a0b0:[35;0x804a0c0,0x804a0d0]
0x804a0c0:[33;(nil),(nil)]
0x804a0d0:[40;(nil),(nil)]
0x804a0e0:[51;(nil),0x804a0f0]
0x804a0f0:[65;(nil),(nil)]

4. トラバーサルを利用する際の注意点

【注意１】二分探索木のトラバーサルを利用するときには、目的に応じて、先行順・中間順・後行順のどれを利用してもよかったり、どれか一つを使用しなければならないといったこともある。　例えば、内容表示関数についてはどれを利用しても構わないが、メモリ解放関数については後行順でなければならない。またさらに、先行順・中間順・後行順の二つ以上を組み合わせて処理しなければならないこともある。

【注意２】トラバーサルを利用するに当たって、

左部分木と右部分木を再帰的にトラバースすること、
先行順・中間順・後行順といった基本的な処理方法があること

の二点は覚えておいて欲しい。しかしながら、目的に応じて、再帰的なトラバーサルの前・中間・後にどのような処理を組み込めばよいかを適切に判断して欲しい。先行順・中間順・後行順といった考え方にとらわれ過ぎてはいけない。

【注意３】メモリ解放関数のように、トラバーサルを実行する関数（freeTree）と、目的を遂行するための関数（freeAll）を別々に作らなければならないこともある。

【注意４】これまでの説明では、左部分木を先にトラバースして、そのあとで右部分木をトラバースすると述べてきたが、目的によっては、右部分木を先にトラバースして、そのあとで左部分木をトラバースしたほうがよいこともある。そのようなプログラムは、再帰呼び出しの順序を逆転するだけで実現できる。

5. トラバーサルの応用例（２）

二分探索木のトラバーサルの簡単な応用例を幾つか示そう。

5.1. ノード数を求める

二分探索木のノード数を求める関数を示す。戻り値を返す関数のプロトタイプ（雛形）として学習して欲しい。

int count( struct node * p ){
  int cnt = 0;
  if( p != NULL ){
    cnt += count(p->left);       /* 左部分木のノード数 */
    cnt += count(p->right);      /* 右部分木のノード数 */
    cnt++;                       /* pが指すノードをカウント */
  }
  return cnt;
}

〈参考〉p＝NULLのときには、pが指すノードを根とする部分木は空だと考えることができる。従って、p＝NULLのときのノード数は0個になる。そのため、上の関数は、p＝NULLのとき0を返すようにしている。

5.2. 各ノードのレベルを求める

内容表示関数を少し変更して、各ノードの内容とともに、各ノードの「レベル」を表示する関数を示す。まず、ノードの「レベル」を定義しよう。

【定義】二分探索木における各ノードvの「レベル」（以下、level(v)で表す）を（帰納的に）次のように定義する。

二分探索木の根rに対して、level(r)=0 と定める。
根以外の任意のノードvに対して、level(v)=level(u)+1 と定める。ここで、uはvの親を表す。

【例】次図の二分探索木を考える。

この二分探索木における各ノードのレベルは次のようになる。

29を保持したノード（根）のレベルは0である。
13, 47を保持した各ノードのレベルは1である。
5,19,35,51を保持した各ノードのレベルは2である。
15,33,40,65を保持した各ノードのレベルは3である。

（例終わり）

以下に、各ノードの内容とレベルを表示する関数を示す。ノードへのポインタ以外の引数を渡す関数のプロトタイプ（雛形）として学習して欲しい。

void display2( struct node * p, int level ){
  if( p != NULL ){
    printf("%p:[%d;%p,%p]  level=%d\n", p, p->value, p->left, p->right, level);
    display2(p->left, level+1);            /* 左部分木をトラバース */
    display2(p->right,level+1);            /* 右部分木をトラバース */
  }
}

この関数の第二引数 level には、第一引数pが指すノードのレベルを渡す。従って、この関数を（main関数などから）呼び出すときには、根のレベルが0なので、第二引数には0を指定する。

5.3. クローニング

二分探索木のクローン（複製）を作成して、その根へのポインタを返す関数を示す。これは、ノード数を求める関数と同様に、戻り値を返す関数の典型例である。なお、p＝NULLのときにはNULLを戻り値として返していることに注意して欲しい（NULLを返さなければいけない理由を考えよ）。

struct node * clone( struct node * p ){
  struct node * new_node, * new_left, * new_right; 
  if( p != NULL ){
    new_left  = clone(p->left);              /* 左部分木のクローンを作成 */
    new_right = clone(p->right);             /* 右部分木のクローンを作成 */
    new_node = malloc(sizeof(struct node));  /* pが指すノードのクローンを作成 */
    new_node->value = p->value;
    new_node->left  = new_left;
    new_node->right = new_right;
  } else {
    new_node = NULL;
  }
  return new_node;
}

なお、ノード数を求める関数を真似て、この関数を次のように作っても構わない（変数new_nodeをあらかじめNULLに初期設定して、上記のelse節を削除する）。

struct node * clone( struct node * p ){
  struct node * new_node=NULL, * new_left, * new_right; 
  if( p != NULL ){
    new_left  = clone(p->left);              /* 左部分木のクローンを作成 */
    new_right = clone(p->right);             /* 右部分木のクローンを作成 */
    new_node = malloc(sizeof(struct node));  /* pが指すノードのクローンを作成 */
    new_node->value = p->value;
    new_node->left  = new_left;
    new_node->right = new_right;
  }
  return new_node;
}

5.4. 配列に格納する

二分探索木に登録されているデータ要素を（適当な順序で）配列に格納する関数を示す。二分探索木から配列へ変換する関数のプロトタイプ（雛形）として学習して欲しい。

この関数の仕様を説明しておこう。この関数は、

ノードへのポインタp、
int型の配列X、
配列Xの大きさ（配列要素数）size、
配列Xの添字idx（注：この添字idxは「次に格納すべき位置」を表している）

を引数として受け取って、X[idx]にpが指すノードが保持するデータ要素を格納し、それに続けて左部分木内のデータ要素と右部分木内のデータ要素を配列Xに格納する。また、最後に、配列Xに格納したデータ要素の個数を戻り値として返す。ただし、配列要素をすべて使い切ってしまったら（戻り値を返すことを除いて）何もせずに終了する。また、p＝NULLだったら、格納すべきデータ要素が存在しないので、（戻り値を返すことを除いて）何もせずに終了する。

int tree_to_array( struct node * p, int X[], int size, int idx ){
  if( idx < size && p != NULL ){                     /* (a) */ 
    X[idx] = p->value; idx++;                        /* (b) データ要素を格納 */
    idx = tree_to_array( p->left,  X, size, idx );   /* (c) 左部分木 */
    idx = tree_to_array( p->right, X, size, idx );   /* (d) 右部分木 */
  }
  return idx;                                        /* (e) */
}

なお、この関数を呼び出すときにはidxに0（注：最初に格納すべき位置）を渡す。

この関数の動作を直感的に説明しよう。そのために、まず、idxの値が次の二つの意味を持っていることを注意しておこう。

idxの値は、先にも述べたように、「次に格納すべき位置」を表している。さらに、その値は「それまでに格納したデータ要素の個数」も表している。

またさらに、

関数の戻り値は「それまでに格納したデータ要素の個数」である

という点にも注意して欲しい。

以上の二点を念頭に関数の動作（意味）を説明すると次のようになる。なお、以下の(a)～(e)はプログラム中の各行を表す。

(a) 配列要素を使い切ってしまったり（もはや格納できない）、pがNULLだったら（格納すべきデータ要素がない）、(e)だけを実行して終了する。一方、配列要素が残っていて、かつ、p≠NULLだっら以下の(b)～(e)を実行する。
(b) pが指すノードのデータ要素を配列に格納する。さらに、idxを「次に格納すべき位置」にしなければならないので、idxをインクリメントする。
(c) 現在のidxの値以降の配列要素に左部分木内のデータ要素を格納する。さらに、関数tree_to_arrayの戻り値は「それまでに格納したデータ要素の個数」であり、それは「次に格納すべき位置」をも表している。従って、関数からの戻り値をidxに代入する。
(d) 現在のidx（左部分木に関する処理によって得られたidx）の値以降の配列要素に右部分木内のデータ要素を格納する。さらに、関数tree_to_arrayの戻り値は「それまでに格納したデータ要素の個数」であり、それは「次に格納すべき位置」をも表している。従って、関数からの戻り値をidxに代入する。
(e) 以上の処理によって得られるidxの値は「それまでに格納されたデータ要素の個数」を表している。従って、idxの値を返せばよい。なお、if文の内部を実行しなかった場合には、新たなデータ要素を何も格納しなかったことになるので、引数として渡されたidxの値をそのまま返せばよい。

6. 演習問題

【問題１】中間順のトラバーサルを利用した内容表示関数を作成せよ。関数名を in_display にすること。

【問題２】後行順のトラバーサルを利用した内容表示関数を作成せよ。関数名を post_display にすること。

【補助問題】先行順、中間順、後行順のいずれかを利用した内容表示関数は、データ要素を昇順（小さい順）に表示するプログラムにもなっている。どれか？（昇順に表示される理由も考察せよ。）なお、この問題は、次の問題３に対する補助問題であり、プログラミングの問題ではない。

【問題３】二分探索木に登録されているデータ要素を降順（大きい順）に表示する関数を作成せよ。関数名を decreasing_order にすること。〈参考〉右部分木、左部分木の順にトラバースせよ。この点と、補助問題の答えがヒントになるはずである。

【問題４】二分探索木に登録されているデータ要素（整数値）の総和を戻り値として返す関数を作成せよ。関数名を sum にすること。

【問題５】ノードへのポインタと二つの整数値a,b（ただし、a≦bとする）を引数として受け取って、 a以上b以下のデータ要素の個数を戻り値として返す関数を作成せよ。関数名を count_interval にすること。

【問題６】二分探索木の葉の個数を戻り値として返す関数を作成せよ。関数名を count_leaves にすること。

【問題７】二分探索木のすべての内部ノードに対して、左側の子供と右側の子供の位置を交換する（すなわち、左側を右側にし、右側を左側にする）関数を作成せよ。関数名を reverse にすること。

【定義】各ノードのレベルの最大値を二分探索木の「高さ」と呼ぶ。先の図で示した二分探索木について言うと、レベルの最大値は3なので、その二分探索木の高さは3である。

【問題８】二分探索木の高さを求める関数を作成せよ。関数名を height にすること。

【問題９】内容表示関数を次の要件を満たすように変更せよ。

各ノードvの内容を表示する際に、level(v)*2文字分の字下げを行ったあと（つまり、level(v)*2個分の空白を表示したあと）、ノードvの内容を表示する。

先行順、中間順、後行順のすべてに対して、この表示関数を作成すること。関数名は適当に決めて構わない。

【定義】任意のノードvに対して、その左部分木のノード数をLとおき、右部分木のノード数をRとおくとき、L-R をノードvの「均衡度」と呼ぶ。先の図で示した二分探索木について言うと、根の均衡度は 4-6 = -2 であり、整数値47を保持したノード（根の右側の子供）の均衡度は 3-2 = 1 である。

【問題10】各ノードに対して、ノードの内容と均衡度を同時に表示する関数を作成せよ。関数名を balance にすること。〈参考〉同時に表示するためには後行順を利用するとよい。また、部分木のノード数を戻り値として返すこと。そうしないと各ノードの均衡度を求めることができないので。（注意：前の資料では、均衡度も返さなくちゃいけないなんてことを書いていましたが、あれはウソでした。スンマセン。）

【問題11】任意の整数列A=A[0],A[1], ..., A[n-1]に対して、次の方法によって昇順にソーティングすることができる。

整数列Aから二分探索木を構築する。
二分探索木をトラバースすることによって各整数を配列Aに昇順に格納し直す。

この方法に基づいたソーティング関数を作成せよ。

【追加の演習問題】ここをクリック

日本大学文理学部情報システム解析学科 S.Toda / 2005年11月30日