Binary Tree(２分木)
木
リストは１つのデータをつなげていくデータ構造でした．2つ以上のデータ をつなげていくデータ構造は木構造とよばれます．その中でも2 本の枝をもっているのが2分木です．いいかたを変えると，リストは腕が1本あり，それを１つの次のデータにつなげていきますが，2分木は腕が2本あります．
木構造にデータを格納する際に，順序性をもたせてデータ管理する木を順序木といいます．一般に順序木としての2分木 は，現在のデータ基準にして「それより大きいデータ」，「それより小さいデータ」をそれぞれ右または左に振り分けてつなげていきます．
本講義で は、小さいデータを左、大きいデータを右というように統一して考えます。
2分木の探索（2分木 からデータを探す）
2分木に格納されたデータから，あるデータを探そうとした場合，簡単にデータを探すことがで きます．
２分木において，目標となるノードを探す手順は以下のとおりです．
- ルー トを最初のノードにする
- 目標値がノードより小さければ左，大きければ右に移動
- 1,2の繰り返し
２ 分木のデータの出力
2分木に 格納されたデータを出力する際には，以下のパターンがあります．
- 横型探索 ・・・ 自 分と同世代のノードを横に辿って出力していきます．
- 縦型探索 ・・・ 子ノードを辿っていきながら出力していきます．
- ・行きがけ順 ・・・ 出会ったときに即座に出力します
- ・通りがけ順 ・・・ 子ノードをまたぐ際に出力します。
- ・帰りがけ順 ・・・ 戻るときに出力します。
2分木を利用したデータ構造は，通りがけ順で出力するとソーティングされた形 で出力するという利点があります。
2分木におけるデータ（ノード）削除 （教科書p400～）
削除のパターン（場合分け）は３つ。詳細は教科書で。
- 子ノードを持たない場合
- １つだけ子ノードを持つ場合
- ２つの子ノードを持つ場合
- （１）削除したいノードの左部分木から最大値のノードを見つける
- （２）最大値を削除ノードへ代入
- （３）最大値のあったノードを削除
2分木実装するために再帰アルゴリズムについて理解しよう
2分木のプログラムを作成するときには，再帰アルゴリズムを知ってお くと便利です．（詳細は5章参照）
再帰 ・・・ ある事象が自分自身によって定義されていること．
例）GNUの 定義