2016-04-13 23 views
1

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; 
} 

Antwort

1

Ihre construct() nimmt Hinweise auf Zeiger:

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

Aber in einigen Fällen, Sie versuchen, diese Funktion mit Provisorien zu nennen. Zum Beispiel:

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

GetLeft(), GetRoot() und GetRight() alle Rück einen temporären vom Typ BST* und nicht konstanten lvalue Verweise auf Provisorien nicht binden können.

Sie müssen den eingehenden Zeiger jedoch nie wirklich ändern. Die Funktion construct() modifiziert nur die spitzen Objekte. Also nimm sie einfach nach Wert. Und ändern Sie die Namen:

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