C++ شجرة البحث الثنائية وظيفة البحث العودية

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

لذلك هذا هو بلدي وظيفة البحث عن بلدي BST الدرجة مع تي عقدة.x هي البيانات التي تم البحث عنها داخل الشجرة لين هو مجرد مبلغ العقد يجب أن السفر إلى الخروج مع مطابقة عقدة إذا كان موجودا.لم implented ذلك حتى الآن, أنا فقط تدريجيا النامية مهمتي.أنا أتصل أنه من خلال القيام بذلك:

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

v هو مجرد ناقل وكان لمقارنتها ، لذلك هذا هو مجرد توريد مع الباحث.الخطأ أنا الحصول على:

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]

لذلك أنا لست متأكدا ما أفعله خطأ أو حيث أفعله خطأ.

Answer 1

حسنا، ربما ينبغي أن يكون bool BST<T>::search(struct Node<T>*& root, const T& x) CONST بعد أن مثل ذلك: bool BST<T>::search(struct Node<T>*& root, const T& x) const. في الأساس، وكنت قد دعا وظيفة غير CONST من وظيفة CONST وهذا لا لا.

وراجع للشغل، وهذا يبدو المشتبه لي "struct Node<T>*&" ... ربما كنت إسقاط ووالعمل مع Node<T>* ... ولكن ربما كنت بحاجة إلى ذلك بسبب <م> البنية ؟

وأيضا، وهذا هو C ++، لا يوجد أي سبب لترك عقدة بمثابة البنية ... تحتاج الى ان يكون على البنية في تعريف المعلمة يبدو سيئا فحسب IMHO. لماذا لا تجعل عقدة فئة؟

Answer 2

هناك عدة مشاكل في البحث الخاص بك التعليمات البرمجية:

• ترتيب الفرز إلى الوراء ، إذا كانت البيانات عقدة أقل من ما كنت ابحث, يجب عليك البحث في فرع غير الفرع الأيسر.

• يجب أن تعود نتيجة دعوة متكررة

• ومن غير الواضح أيضا لماذا تمر root بالإشارة.بدلا من ذلك ينبغي أن مرت كما const مؤهل المؤشر و طريقة الجسم يجب أن يكون const تأهل أيضا.

هنا هو البديل:

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

و هنا هو أبسط عدم تنفيذ العودية:

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

الخوارزمية :

1. تأخذ العقدة قيمة البيانات ؛
2. كرر الخطوات من 3 إلى 5 حتى نجد قيمة أو نذهب أبعد من الشجرة.
3. إذا كانت البيانات يساوي الجذر عقدة قيمة البحث بنجاح وإنهاء الخوارزمية.
4. إذا كانت البيانات أقل من عقدة الجذر قيمة علينا البحث عن يسار الشجرة الفرعية.
5. آخر البيانات أقل من عقدة الجذر قيمة علينا البحث عن يسار الشجرة الفرعية.
6. إخراج طباعة رسالة "وجد" أو "لم يتم العثور على".

---

تنفيذ C++

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