c++ - 错误:没有用于调用 BSTLink::construct(BST*, BST*, BST*) 的匹配函数

Question

我已经编写了一个 BSTLink 类来将 BST 转换为双向链表，但是在我尝试通过引用传递 BST 的节点指针的类中的构造调用抛出一个错误“没有匹配的函数来调用 BSTLink::construct(BST*, 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;
}

Answer 1

您的construct() 引用了指针:

void construct(BST*& l, BST*& rt, BST*& r) {
                  ^^       ^^        ^^

但在某些情况下，您会尝试使用临时对象调用该函数。例如:

construct(tree->GetRoot()->GetLeft(), tree->GetRoot(), tree->GetRoot()->GetRight());

GetLeft()、GetRoot() 和 GetRight() 都返回一个临时类型 BST*，并且非常量左值引用不能绑定(bind)到临时对象。

但是，您实际上永远不需要修改传入指针。 construct() 函数只修改指向的对象。所以简单地按值(value)来看待它们。并更改名称:

void construct(BST* left, BST* root, BST* right) { ... }