البحث شجرة ثنائية

Question

أنا أكتب وظيفة تكرارية للبحث في شجرة ثنائية لقيمة معينة. هذا مترجم في الاتجاه المدخري حتى أتوصل إلى كيفية تقيام الطبقات.

افترض أن صفي هو BinarySearchtree، ولديه مؤشر إلى عقدة الجذر للشجرة. افترض أيضا أن العقد يتم إدراجها من خلال وظيفة إدراج، ولديها مؤشرات إلى طفلين. هنا نسخة مختصرة من بنية العقدة:

struct Node
{
   public:
      Node *left_, *right_;
      int value_

      Node(int val) : value_(val), left_(0), right_(0) { }
      //done in this manner to always make sure blank children are
      //init to zero, or null
      Node(int val, Node *left, Node *right) : value_(val), left_(0), right_(0) 
          { left_ = left; right_ = right; } 
}

لذلك، يمكنك أن تفترض بأمان أن مؤشرات الأنباء الخاصة بالعقدة ستكون فارغة.

هنا هو رمزي:

int BinarySearchTree::search(int val)
{
    Node* next = this->root();

    while (next->left() != 0 || next->right () != 0)
    {
        if (val == next->value())
        {
            return next->value();
        }    
        else if (val < next->value())
        {
            next = next->left();   
        }
        else if (val > next->value())
        {
            next = next->right();
        }
    } 

    //not found
    return 0;
}

يتم رفض هذا الرمز من قبل صديق لسببين:

1) إذا كان المقبل لا يوجد لديه أطفال، فسيقوم كلاهما بتقييمه إلى الصفر وسأقوم بإنهاء الحلقة (لن أتحقق من الفاصل المطلق أعلاه مقابل القيمة التالية).

2) إذا كان المقبل لديه طفل واحد، ولكن يجب أن تكون البيانات التي تبحث عنها على الجانب الفارغ من الشجرة، وسيتم تعيين التالي إلى 0، وسوف حلقة مرة أخرى، مقارنة بعد ذلك (وهو 0) إلى اليسار واليمين أشجار مثل while(0->left()), ، مما أدى إلى سلوك غير محدد.

قلت أن الحل لكلا المشكلتين يكمن في حالة الحلقة، لكنني لا أستطيع أن أرى ما يمكنني فعله لسهولة العلاج بالوضع. هل يمكن لمجتمع فائض المكدس تقديم أي رؤى؟

Answer 1

أعتقد أنه يجب أن تكون اختبارا إذا كان التالي ليس فارغا في حلقة الخاص بك مثل ذلك:

int BinarySearchTree::search(int val)
{
    Node* next = this->root();

    while (next)
    {
        if (val == next->value())
        {
            return next->value();
        }    
        else if (val < next->value())
        {
            next = next->left();   
        }
        else if (val > next->value())
        {
            next = next->right();
        }
    } 

    //not found
    return 0;
}

Answer 2

جرب هذا:

while (next != NULL) ?

Answer 3

بادئ ذي بدء، لست متأكدا من السبب في أنك تعيد INT. ماذا لو كنت تبحث عن 0 في الشجرة. ربما تريد شيئا مثل هذا:

bool BinarySearchTree::Search(int val) {
  Node* current = root();
  while (current != NULL) {
    // Check if it's here
    if (val == current->value()) {
      return true;
    }
    if (val < current->value()) {
      current = current->left();
    } else {
      current = current->right();
    }
  }
  // Not found
  return false;
}

لاحظ أن حلقة ثابتة: في بداية كل حلقة، فأنت في عقدة غير فارغة تحتاج إلى "معالجة". تحقق أولا مما إذا كانت العقدة التي تريدها. إذا لم يكن الأمر كذلك، فقم بإجراء فرع، واسمحوا الحلقة تقرر ما إذا كان الفرع "جيد" (أي غير فارغة). ثم ستسمح للتكرار الحلقة التالية بعناية بالاختبار.