C ++ binärer Suchbaum rekursive Suchfunktion

Question

template <class T>
bool BST<T>::search(const T& x, int& len) const
{
    return search(BT<T>::root, x);
}


template <class T>
bool BST<T>::search(struct Node<T>*& root, const T& x)
{
   if (root == NULL)
       return false;
   else
      {
         if (root->data == x)
             return true;
         else if(root->data < x)
             search(root->left, x);
         else 
             search(root->right, x);                 
      }             
}

Das ist also meine Suchfunktion für meine BST-Klasse mit einem T-Knoten. x die Daten innerhalb des Baumes werden gesucht, Len nur die Menge der Knoten ist es mit dem passenden Knoten zurückzulegen hat, zu kommen, wenn es vorhanden ist. Ich habe das noch nicht zuzurAufnahme, bin ich nur meine Aufgabe schrittweise zu entwickeln. Ich rufe sie durch dies zu tun:

if(t.search(v[1], len) == true)
       cout << endl << "true";

v

ist nur ein Vektor schaffe ich musste es zu vergleichen, und so ist diese Versorgung es nur mit einem int. Der Fehler erhalte ich:

BST.h: In member function âbool BST<T>::search(const T&, int&) const [with T = int]â:
prog5.cc:24:   instantiated from here    
BST.h:78: error: no matching function for call to âBST<int>::search(Node<int>* const&, const int&) constâ    
BST.h:76: note: candidates are: bool BST<T>::search(const T&, int&) const [with T = int]
BST.h:83: note:                 bool BST<T>::search(Node<T>*&, const T&) [with T = int]

Also ich bin nicht sicher, was ich falsch mache oder wo ich falsch mache.

Answer 1

Okay, bool BST<T>::search(struct Node<T>*& root, const T& x) wahrscheinlich konst, nachdem es wie so haben sollte: bool BST<T>::search(struct Node<T>*& root, const T& x) const. Grundsätzlich haben Sie eine nicht-konstante Funktion von einer konstanten Funktion genannt und das ist ein No-No.

BTW, vermuten, dass dieses mir „struct Node<T>*&“ sieht ... würde ich wahrscheinlich fallen die & und die Arbeit mit Node<T>* ... aber vielleicht brauchen Sie, dass aufgrund der struct ?

Auch dies ist C ++, gibt es keinen Grund Knoten als eine Struktur zu verlassen ist ... zu müssen haben struct in der Parameterdefinition sieht einfach schlecht, IMHO. Warum nicht Node eine Klasse machen?

Answer 2

Es gibt mehrere Probleme bei der Suche Code:

• Die Sortierreihenfolge nach hinten ist, wenn die Knoten Daten kleiner als das, was Sie suchen, können Sie in dem rechten Zweig suchen sollen, nicht der linke Zweig.

• Sie sollten das Ergebnis des rekursiven Aufrufs zurückkehren

• Es ist auch unklar, warum Sie root durch Verweis übergeben. es sollte stattdessen als const qualifizierte Zeiger und das Verfahren Körper geleitet werden soll, qualifiziert zu const werden.

Hier ist eine Alternative:

template <class T>
bool BST<T>::search(const struct Node<T> *root, const T& x) const {
    if (root == NULL)
        return false;
    else
    if (root->data == x)
        return true;
    else
    if (root->data < x)
        return search(root->right, x);
    else 
        return search(root->left, x);
}

Und hier ist ein einfacher nicht rekursive Implementierung:

template <class T>
bool BST<T>::search(const struct Node<T> *root, const T& x) const {
    while (root != NULL) {
        if (root->data == x)
            return true;
        if (root->data < x)
            root = root->right;
        else 
            root = root->left;
    }
    return false;
}

Answer 3

Algorithmus:

1. node Wertdaten nehmen;
2. Wiederholen Sie Schritt 3 Schritt 5, bis wir den Wert zu finden, oder wir über den Baum gehen.
3. Wenn Daten auf Wurzelknoten Wert gleich ist, ist die Suche erfolgreich ist, und der Algorithmus beendet.
4. Wenn Daten kleiner als Wurzelknoten Wert haben wir den linken Unterbaum suchen.
5. Else Daten kleiner als Wurzelknoten Wert haben wir den linken Unterbaum suchen.
6. Ausgabe drucken Meldung "gefunden" oder "Not Found".

---

C ++ Implementierung

    node* search(node* root, int data)
    {
     if (root==NULL || root->data==data) return root;

     if (root->data < data)   return search(root->right, data);

     return search(root->left, data);
   }