1
BSTを二重リンクリストに変換するクラスBSTLinkを作成しましたが、参照によってBSTのノードポインタを渡そうとすると、 "BSTLink :: construct（BST *、BST *、BST *）への呼び出しに対応する関数がありません"というエラーがスローされる "なぜそれがBSTのノードのアドレスを選択できないのですか？エラー：BSTLink :: construct（BST *、BST *、BST *）の呼び出しに一致する関数がありません
#include <iostream>
#include <cstdlib>
using namespace std;
class BST {
protected:
int value;
BST *left;
BST *right;
public:
BST(int v) {
value = v;
left = NULL;
right = NULL;
}
BST(const BST &cpy) {
left = NULL;
right = NULL;
value = cpy.GetValue();
}
~BST() {
delete left;
delete right;
}
BST *GetLeft() const {
return left;
}
BST *GetRight() const {
return right;
}
int GetValue() const {
return value;
}
void SetLeft(BST *l) {
left = l;
}
void SetRight(BST *r) {
right = r;
}
void SetValue(int v) {
value = v;
}
};
class BinTree {
protected:
BST *root;
void copy_bintree(BST *rt, BST *rt_cpy) {
BST *l = new BST(*(rt_cpy->GetLeft()));
BST *r = new BST(*(rt_cpy->GetRight()));
rt->SetLeft(l);
rt->SetRight(r);
if (l)
copy_bintree(l,rt->GetLeft());
if (r)
copy_bintree(r,rt->GetRight());
}
void delete_bintree(BST *rt) {
if (root) {
BST *l = root->GetLeft();
BST *r = root->GetRight();
delete root;
delete_bintree(l);
delete_bintree(r);
}
}
void insert_node(BST *rt, BST *n) {
if (rt->GetLeft() == NULL && n->GetValue() <= rt->GetValue()) {
rt->SetLeft(n);
}
else if(rt->GetRight() == NULL && n->GetValue() > rt->GetValue()) {
rt->SetRight(n);
}
else if (n->GetValue() <= rt->GetValue()) {
insert_node(rt->GetLeft(), n);
}
else if (n->GetValue() > rt->GetValue()) {
insert_node(rt->GetRight(), n);
}
}
void get_parent(BST *rt, BST *n, BST *&par) {
if (rt == n) {
par = NULL;
} else if (rt->GetLeft() == n || rt->GetRight() == n) {
par = rt;
} else if (rt->GetLeft() && n->GetValue() <= rt->GetValue()) {
get_parent(rt->GetLeft(),n,par);
} else if (rt->GetRight() && n->GetValue() > rt->GetValue()) {
get_parent(rt->GetRight(),n,par);
} else
par = NULL;
}
BST *get_left_child(BST *rt) {
if (rt->GetLeft() == NULL)
return rt;
else
return get_left_child(rt->GetLeft());
}
void delete_nd(BST *&node) {
BST *left = get_left_child(node->GetRight());
node->SetValue(left->GetValue());
BST *par_left;
get_parent(node->GetRight(),left,par_left);
if (par_left) {
par_left->SetLeft(left->GetRight());
} else {
node->SetRight(left->GetRight());
}
left->SetRight(NULL);
delete left;
}
void delete_node(BST *&node) {
node->SetLeft(NULL);
node->SetRight(NULL);
delete node;
}
public:
BinTree() {
root = NULL;
}
BinTree(const BinTree &cpy) {
root = new BST(*(cpy.GetRoot()));
if (root)
copy_bintree(root,cpy.GetRoot());
}
~BinTree() {
delete_bintree(root);
}
BST *GetRoot() const {return root;}
void InsertNode(BST *node) {
if (!root)
root = node;
else {
insert_node(root, node);
}
}
void DeleteNode(BST *node) {
BST *par;
get_parent(root,node,par);
if (par == NULL) {
delete_nd(node);
} else if (par->GetLeft() == node) {
if (!node->GetLeft()) {
par->SetLeft(node->GetRight());
delete_node(node);
}
else if (!node->GetRight()) {
par->SetLeft(node->GetLeft());
delete_node(node);
}
else {
delete_nd(node);
}
} else {
if (!node->GetLeft()) {
par->SetRight(node->GetRight());
delete_node(node);
}
else if (!node->GetRight()) {
par->SetRight(node->GetLeft());
delete_node(node);
}
else {
delete_nd(node);
}
}
}
void InOrder(BST *rt) {
if (rt) {
InOrder(rt->GetLeft());
cout<<rt->GetValue()<<endl;
InOrder(rt->GetRight());
}
}
void PreOrder(BST *rt) {
if (rt) {
cout<<rt->GetValue()<<endl;
PreOrder(rt->GetLeft());
PreOrder(rt->GetRight());
}
}
void PostOrder(BST *rt) {
if (rt) {
PostOrder(rt->GetLeft());
PostOrder(rt->GetRight());
cout<<rt->GetValue()<<endl;
}
}
};
class BSTLink {
protected:
BST *start;
void construct(BST*& l, BST*& rt, BST*& r) {
if (l) {
BST *ll = l->GetLeft();
BST *lr = l->GetRight();
construct(ll,l,lr);
}
if (r) {
BST *rl = r->GetLeft();
BST *rr = r->GetRight();
construct(rl,r,rr);
}
if (l) {
l->SetRight(rt);
l->SetLeft(NULL);
}
if (r) {
r->SetLeft(rt);
r->SetRight(NULL);
}
}
BST *GetStart(BST *rt) {
while (rt->GetLeft()) {
rt = rt->GetLeft();
}
return rt;
}
public:
BSTLink(BinTree *&tree) {
if (tree->GetRoot()) {
construct(tree->GetRoot()->GetLeft(), tree->GetRoot(), tree->GetRoot()->GetRight());
start = GetStart(tree->GetRoot());
}
else
start = NULL;
}
void Print() {
while (start) {
cout<<start->GetValue()<<endl;
start = start->GetRight();
}
}
};
int main() {
BinTree *bt = new BinTree();
BST *n1 = new BST(6);
BST *n2 = new BST(11);
BST *n3 = new BST(9);
BST *n4 = new BST(3);
BST *n5 = new BST(4);
BST *n6 = new BST(1);
BST *n7 = new BST(5);
BST *n8 = new BST(2);
bt->InsertNode(n1);
bt->InsertNode(n2);
bt->InsertNode(n3);
bt->InsertNode(n4);
bt->InsertNode(n5);
bt->InsertNode(n6);
bt->InsertNode(n7);
bt->InsertNode(n8);
//bt->DeleteNode(bt->GetRoot());
//bt->DeleteNode(n7);
//bt->InOrder(bt->GetRoot());
BSTLink *lnk = new BSTLink(bt);
lnk->Print();
return 0;
}