|
progC.pdf Tree を変更：2014-02-05 |
 実行結果 |
二分探索木のリストです．Tree は抽象クラスで，オブジェクトを作れません．
/* --- p4.cpp （半角 < を全角 ＜ で置換）--- */
#include ＜stdio.h>
#include ＜stdlib.h>
#include ＜string.h>
class Node{
public:
int d; Node *l, *r;
Node(void){d = 0; l = r = NULL;}
Node(int d0){Node( ); d = d0;}
void show(char *s, Node *p){
char sl[8], sr[8];
if(strlen(s) > 7){exit(1);}
if(p == NULL) return;
strcpy(sl, s); strcpy(sr, s);
show(strcat(sl, "L"), p->l);
printf("%s: %d\n", s, p->d);
show(strcat(sr, "R"), p->r);
}
};
class Tree{
public:
Node *root, *tmp, *idle; int sz;
Tree(void){root = tmp = idle = NULL; sz = 0;}
Tree(Node *p, int n){
root = tmp = NULL; idle = p; sz = n;
for(int k = 0; k < n-1; k++){p[k].r = &p[k+1];}
p[n-1].r = NULL;
}
void push(Node *p){p->r = idle; idle = p; sz++;}
void pop(void){
if(sz == 0){exit(1);}
tmp = idle; idle = idle->r; sz--;
tmp->l = tmp->r = NULL;
}
virtual void ins(int k) = 0; //純粋仮想関数 {
//pop( ); tmp->d = k; tmp->r = root; root = tmp;
//} //デバッグ用
virtual void del(int k) = 0; //純粋仮想関数 {
//if(root == NULL || root->d != k){return;}
//tmp = root->r; push(root); root = tmp;
//} //デバッグ用
virtual void show(void){root->show("", root);}
};
class STree: public Tree{
public:
STree(Node *p, int n): Tree(p, n){ }
Node* search(int k);
void ins(int);
void del(int);
};
Node* STree::search(int k){
Node *p=root;
while(p != NULL && p->d != k){
if(p->d < k){p = p->r;}else{p = p->l;}
}
if(p == NULL){printf("not ");}
printf("found\n"); return p;
}
void STree::ins(int k){
Node *p=root;
pop( ); if(tmp == NULL) return;
while(p != NULL && k != p->d){
if(k < p->d){
if(p->l != NULL){p = p->l;}else{p->l = tmp; break;}
}else{
if(p->r != NULL){p = p->r;}else{p->r = tmp; break;}
}
}
tmp->d = k; if(p == NULL){root = tmp;}
} //既存なら変更なし
void STree::del(int k){ //削除
Node *p=root, *p1=root, *p2, *p3;
while(p != NULL && p->d != k){
p1 = p; //if(p->d == k){break;}
p = (k < p->d ? p->l: p->r);
} //「□?□:□」は[#19%31B]
p2 = p; if(p == NULL){return;}
if(p->l == NULL || p->r == NULL){
if(p->l == NULL){p = p->r;}else{p = p->l;}
}else{
p3 = p = p->r;
while(p->l != NULL){ p3 = p;
if(p->l != NULL){p = p->l;}
}
if(p != p3){p3->l = p->r;}
if(p == p3){p2->r = p3->r;}
p->l = p2->l; p->r = p2->r;
}
push(p2);
if(p1 == p2){root = p;}
else if(p1->l == p2){p1->l = p;}
else{p1->r = p;}
} //不在なら変更なし
//
int main(void){
Node n[8]; STree t(n, 8);
t.ins(7); t.ins(3); t.ins(5); t.ins(9); t.ins(2);
t.show( ); printf("\n"); t.del(3); t.show( );
return 0;
}
参考資料（[n]は本文でも引用, *.pptはブロック解除が面倒なので未調査）：
