Ich habe eine Klasse BSTLink geschrieben, um eine BST in eine doppelt verknüpfte Liste zu konvertieren, aber den Konstruktaufruf in der Klasse, in der ich versuche, die Knotenzeiger von BST durch Verweis zu übergeben, wirft einen Fehler auf "Keine übereinstimmende Funktion für den Aufruf von BSTLink :: construct (BST *, BST *, BST *)" Warum ist es nicht möglich, die Adresse der Knoten von BST auszuwählen?Fehler: Keine übereinstimmende Funktion für den Aufruf von 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;
}