二分木（二進木） - 理工学部・情報科学科

二分木（二進木）
理工学部情報科学科
上級プログラミング
二分木

あるデータ群の大小関係を表現するデータ構造
例： 8, 10, 3, 9, 5, 1, 12, 4, 11 という整数の入力列から
昇順（または降順）の二進木を構成する。
構成方法：
root
（根）
新しいノードを追加するとき、
木のノードと比較して
小さければ左へ、
そうでなければ右へたどり、
空き場所につなげる
0
8
0 0
3
10
0 0
0 0
1
5
9
12
0 0
0 0
0 0
0 0
4
11
0 0
0 0
二分木の設計（１）
BinNodeオブジェクト
class BinTree {
private:
idata
class BinNode {
8
public:
right
left
0 0
int idata;
BinNode *left, *right; // 左右の二分木を指すポインタ
BinNode(int a=0){ idata=a; left=right=0; } // ノードのコンストラクタ
void printNode(){ cout<<idata<<“ ”; } // ノードの表示
};
BinNode *root;
void traverse(BinNode *rp); // rpの木をたどりながら表示
BinNode* addNode(BinNode *rp, BinNode *node);
// rpの木にnodeを連結
public:
BinTree(){ root=0; } // 木のコンストラクタ
void printTree(){ traverse(root); } // 木全体を表示
void insert(int x){ // 木にデータxを追加する
BinNode *np=new BinNode(x); // データxを持つノードを作成
root=addNode(root, np); // rootの木に作成したノードを追加
};
}
BinTreeを利用したmain関数の例
int main(){
BinTree bt; //空の二進木を作成
int x;
cout << "正整数をいくつか入力せよ --> ";
while(cin>>x && x>0){ // 負数が入力されるまで正整数を入力
bt.insert(x); // xをデータとして持つノードを木に追加
}
bt.printTree(); // btの木全体を表示する
cout << endl;
このmain関数が動作するためには、
return 0;
insert関数(addNode関数)、
}
printTree関数(traverse関数)を
どのように記述すれば良いか？
二分木と再帰的考え方（addNodeの場合）
二分木の構築は、「木にノードをつなぐ」という考え方
「nodeをrpの木に連結する」と考える
node
0
rp
0
1
8
0 0
0 0
ポイント１：
3
10
0 0
0 0
つまり、
addNode(rp, node)
をしたい。
ポイント２：
5
9
0 0
0 0
そして addNode(rp, node) が返すの
は、出来上がった木の根である
（木の根が変わるときがあるから）
だから BinNode* addNode(BinNode *rp, BinNode *node); という
プロトタイプ宣言になっている。クラス外で定義するときは、以下のように記述。
BinTree::BinNode* BinTree::addNode(BinNode *rp, BinNode *node){･･･}
二分木と再帰的考え方（addNodeの場合）
再帰をさせない境界条件について先に処理する
境界条件1：つなぎ先が空の木ならば、nodeが根になる
rp
node
0
0
8
空の木
0 0
境界条件2：空のnodeをつなげても、木は変わらない
rp
node
0
8
0
0 0
10
3
0 0
0 0
5
0 0
9
0 0
境界条件1,2がそれぞれ成立するときに
addNode(rp, node)
に何をリターンさせるかはこの図から明らか。
二分木と再帰的考え方（addNodeの場合）
addNode(rp, node)の中でやることは・・・・・・
rp
0
8
１つのノードではなく
左右に部分木を持つ木と
考えるのがコツ
0 0
node
0
1
0 0
3
10
0 0
0 0
5
9
0 0
0 0
①nodeはrpの左右どちらに行くか?
この例では8のノードの左側に行く。
②空きでなければ、
「rpの左下の木にnodeをつなぐ」
つまり、addNode(rp->left, node)
このとき左下部分木が空かどうか
気にしなくて良い（前述の境界条件のお陰）
これは最初の「rpの木にnodeをつなぐ」と
同じ表現をしている（再帰的な表現 → 再帰関数）
二分木と再帰的考え方（traverseの場合）
二分木のデータを小さい順にたどる（ここでは表示する）
root
（根）
「この木の全データを昇順に表示する」
つまり、traverse(root)という呼び出しに
対して、何をするか？
0
8
0 0
3
10
0 0
0 0
①空の木だったら何もすることは
ない
この例ではrootは空(0)ではない。
1
5
9
12
0 0
0 0
0 0
0 0
4
11
0 0
0 0
二分木と再帰的考え方（traverseの場合）
二分木のデータを小さい順にたどる（ここでは表示する）(続き）
root
（根）
この木全体を根ノードと左右の部分木に
分けて考える。
0
8
いきなり根ノードのデータを表示できるわけ
ではない。
根ノードの左下の部分木は根ノードより
小さいデータの集合であることに注目。
そこで・・・
0 0
3
10
0 0
0 0
1
5
9
12
0 0
0 0
0 0
0 0
②左下の部分木を表示する。
つまり、traverse( ？ )
③根ノードのデータを表示する。
つまり、根のprintNode()を使用
4
11
0 0
0 0
④右下の部分木を表示する。
つまり、traverse( ？ )
二分木からのノードの削除
int main(){
BinTree bt; //空の二進木を作成
int x;
cout << "正整数をいくつか入力せよ --> ";
while(cin>>x && x>0){ // 負数が入力されるまで正整数を入力
bt.insert(x); // xをデータとして持つノードを木に追加
}
bt.printTree(); // btの木全体を表示する
cout << endl;
while(cout<<"削除したい正整数 -->" && cin>>x && x>0){
bt.remove(x);
BinTreeクラスに
bt.printTree();
remove()メンバ関数を追加
cout << endl;
}
return 0;
}
二分木からのノードの削除
class BinTree {
private:
class BinNode {
public:
int idata;
BinNode *left, *right; // 左右の二分木を指すポインタ
BinNode(int a=0){ idata=a; left=right=0; }
void printNode(){ cout <<idata <<" "; } // 自分のデータの表示
};
BinNode *root;
void traverse(BinNode *rp); // rpの木を表示
BinNode* addNode(BinNode *rp, BinNode *node); // rpの木にnodeを連結
BinNode* delNode(BinNode *rp, int x);
// rpの木からデータxを持つノードを１つ削除する
// delNodeが返すのも削除完了後の木の根（addNodeと同様に根が変わるときがあるから）
public:
BinTree(){ root=0; }
void printTree(){ traverse(root); } // 木全体を表示
void insert(int x){ // 木にデータxを追加する
BinNode *np=new BinNode(x); // データxを持つノードを作成
root=addNode(root, np); // rootの木に作成したノードを追加
}
void remove(int x){ root=delNode(root, x); }
// 木からデータxを持つノードを１つ削除する
};
二分木からのノードの削除
二分木の中のノードを削除する場合には、そのノード
に部分木があるかどうかで処理が異なりそう･･･
1.削除するノードが末端の
（それより下に左右とも
部分木がない）場合
例：左の二分木から「４」の
ノードを削除する場合、
そのノードを削除するだ
けで良い。
root
（根）
0
8
0 0
3
10
0 0
0 0
1
5
9
12
0 0
0 0
0 0
0 0
4
11
0 0
0 0
二分木からのノードの削除
2.削除するノードが左下に
のみ部分木を持つ場合
例：左の二分木から「20」の
ノードを削除する場合、
その削除するノードを、
左下の部分木で置換する。
root
（根）
0
8
0 0
3
２０
0 0
0 0
1
5
15
0 0
0 0
0 0
4
11
18
0 0
0 0
0 0
二分木からのノードの削除
3.削除するノードが右下に
のみ部分木を持つ場合
例：左の二分木から「10」の
ノードを削除する場合、
その削除するノードを、
右下の部分木で置換する。
root
（根）
0
8
0 0
3
10
0 0
0 0
1
5
0 0
0 0
4
0 0
15
0 0
11
18
0 0
0 0
二分木からのノードの削除
4.削除するノードが左右に
部分木を持つ場合
例：左の二分木から「20」の
ノードを削除する場合、
まず、その削除したノード
の代わりに、右下の部分
木を接続する。次に、削除
したノードの左下の部分木
を、木に追加する（左右逆
も可能）。
root
（根）
0
8
0 0
3
２０
0 0
0 0
1
5
15
30
0 0
0 0
0 0
0 0
結果的に削除したノードの右下部分木の
最左端に接続されることになる。つまり、
addNode(右下部分木, 左下の部分木)
で出来る木を、削除したノードの代わりに
親のノードに連結すれば良い。
4
11
18
25
37
0 0
0 0
0 0
0 0
0 0
二分木からのノードの削除
以上4ケースを場合分けしても良いが、再帰の境界条件を
うまく設定することで、場合分けを減らすことが可能。
境界条件：「空の木からノードを削除したら、結果は空の木」
rp
この境界条件を利用すると、rpの木の
根が削除対象でない場合、rpのノード
の左下部分木か右下部分木の適切な
方で削除対象を削除することになるが、
それらの部分木が空であるかどうかは
場合分けの必要が無くなる。
部分木か空か否かでは、再帰呼び出しの
場合分けが不要となる。
0
２０
0 0
15
30
0 0
0 0
11
18
25
37
0 0
0 0
0 0
0 0

Download Report