無題 投稿者：mm 投稿日：2013/07/13(Sat) 09:37 No.8
[1] 授業単元：二分木の消去関数の作成
[2] 以下のプログラムのノードを消去する関数delNode()を完成させよ。但し、書き加えていいのは
BinTree::BinNode *BinTree::delNode(BinNode *rp,int x){
}
の中だけとする。
#include <iostream>
using namespace std;
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);
void addNode(BinNode *rp,BinNode *node);
BinNode *delNode(BinNode *rp,int x);
public:
BinTree(){root=0;}
void printTree(){traverse(root);}
void insert(int x){
BinNode *np=new BinNode(x);
if(!root)root=np;
else addNode(root,np);
}
void remove(int x){root=delNode(root,x);}
};
void BinTree::addNode(BinNode *rp,BinNode *node){
if(rp->idata>node->idata){
if(rp->left!=NULL)
addNode(rp->left,node);
else{
rp->left=node;
}
}
else{
if(rp->right!=NULL)
addNode(rp->right,node);
else{
rp->right=node;
}
}
}
BinTree::BinNode *BinTree::delNode(BinNode *rp,int x){
}
void BinTree::traverse(BinNode *rp){
if(rp==NULL)return;
if(rp->left!=NULL){
traverse(rp->left);
}
rp->printNode();
if(rp->right!=NULL){
traverse(rp->right);
}
}
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);
bt.printTree();
cout << endl;
}
return 0;
}
[3] 環境
[3.1] OS： Linux
[3.2] コンパイラ名とバージョン： g++
[3.3] 言語： C++
[4] 期限： 7月15日(月)終日
[5] その他の制限：
上でも書いたように、書き加える場所は
BinTree::BinNode *BinTree::delNode(BinNode *rp,int x){
}
の中だけです。
ちなみに実行結果は
正数値をいくつか入力せよ --> 8 10 3 9 5 1 12 4 11 -1
1 3 4 5 8 9 10 11 12
消去したい正数値 --> 8
1 3 4 5 9 10 11 12
消去したい正数値 --> 1
3 4 5 9 10 11 12
消去したい正数値 --> 12
3 4 5 9 10 11
消去したい正数値 --> 1
左エラー:1:そのようなノードはありません
3 4 5 9 10 11
消去したい正数値 --> 12
右エラー:12:そのようなノードはありません
消去したい正数値 --> -1
終了
|