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

Question

لذا فإن الكود الخاص بي أدناه. أنا لا أحصل على أي أخطاء ويضع كل شيء في العقدة على ما يرام. ولكن استنادًا إلى عبارات التصحيح الخاصة بي في كل مرة يتم فيها إدخال أي شيء ، فإنه يجد الجذر. لست متأكدًا مما إذا كان هذا صحيحًا. ولكن وفقًا لملف الإخراج للواجب ، تختلف إجاباتي عندما يتعلق الأمر بارتفاع الشجرة ، و traversals ، وأنا مسطح ما زلت أواجه مشكلات في وظيفة عدد الأوراق. قصة أخرى رغم ذلك.

بناءً على عبارات التصحيح ، يبدو أن كل شيء يسير بشكل صحيح. لكني أعتقد أنني قد أحتاج إلى عيون جديدة. لا أرى كيف يمكن أن تتغير تعاطي بلدي على الإطلاق لأنها في الحقيقة مسألة فقط حيث أقوم بطلب العقدة التي يجب أن تؤثر على inorder و preorder و postorder.

template <class T>
void BT<T>::insert(const T& item)
 {
    Node<T>* newNode;
    newNode = new Node<T>(item);
    insert(root, newNode);
 }


template <class T>
void BT<T>::insert(struct Node<T> *&root, struct Node<T> *newNode)
 {
    if (root == NULL)
       {
          cout << "Root Found" << newNode->data << endl;
          root = newNode;
       }
    else
        {
           if (newNode->data < root->data)
              {
              insert(root->left, newNode);
              cout << "Inserting Left" << newNode-> data << endl;
              }
           else
               {
               insert(root->right, newNode);
               cout << "Inserting Right" << newNode->data << endl;
               }
        }
 }

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

template <class T>
int BT<T>::height() const
{
   return height(root);
}


  template <class T>
  int BT<T>::height(Node<T>* root) const
   {
   if (root == NULL)
      return 0;
   else 
      {
      if (height(root->right) > height(root->left))
         return 1 + height(root-> right);
      return 1 + height(root->left);
      }
   }

Answer 1

تحتاج إلى تغيير صياغة بيانات التصحيح الخاصة بك

حقا يجب أن تقرأ (وليس عقدة الجذر)

 cout << "Leaf Node Found" << newNode->data << endl;

إنه الجذر فقط عندما يتم استدعاؤه لأول مرة بعد ذلك أي مكالمة مع العقدة-> اليسار أو العقدة-> اليمين يجعلها عقدة وسيطة.

لكتابة الارتفاع () سأفعل هذا:

template <class T>
int BT<T>::height(Node<T>* root) const
{
    if (root == NULL) {return 0;}

    return 1 + max(height(root->left),height(root->right));
}

Answer 2

تحتاج إلى البدء مع جذر init'd إلى Null. أيضا ، أنت تمر *& node في ؛ يجب أن تكون *العقدة. وإلا فأنت تمرر مؤشرًا إلى العنوان (أو المرجع ، لست متأكدًا من أي شيء في هذا السياق ، لكن كلاهما لن يكون على حق). يجب أن تمرر مؤشرًا إلى العقدة ، وليس مرجعًا.

template <class T>
void BT<T>::BT() 
{ root = 0;}

template <class T>
void BT<T>::insert(const T& item)
 {
    Node<T>* newNode;
    newNode = new Node<T>(item);
    insert(root, newNode);
 }

template <class T>
void BT<T>::insert(struct Node<T> *root, struct Node<T> *newNode)
{
 /*stuff*/
}

Answer 3

Vlion:
يجب أن يكون مؤشرًا على مؤشرات اليسار/اليمين/الجذر (أي مؤشر مزدوج) ، وبالتالي فإن الكود المنشور صحيح ، على الرغم من أنه غير واضح إلى حد ما.

@دوغ:
فكر في تغيير وظيفة إدراجك وهكذا:

template <class T>
void BT<T>::insert(struct Node<T>** root, struct Node<T>* newNode)
 {
    if (*root == NULL)
       {
          cout << "Root Found" << newNode->data << endl;
          *root = newNode;
       }

يوضح ذلك نيتك أنك ستغير المؤشر الذي تم تمريره كمعلمة أول (أو بالأحرى ، المؤشر الذي سيتم تمرير عنوانه كمعلمة الأولى.) سيساعد ذلك في تجنب الارتباك مثل المعلمة التي حدثت للتو.

نداءات إلى هذا الإدراج () ، مثل:

insert(&root, newNode);

سيعكس أيضًا نيتك في تغيير قيمة المؤشر. هذه مسألة أسلوب ، لذلك لا يمكنني المجادلة إذا كنت لا تريد التغيير.

---

أما بالنسبة للتحقق مما إذا كانت الشجرة "صحيحة" ، فلماذا لا ترسمها وترى بنفسك؟ شيء على غرار:

template class<T>
void printTree(struct Node<T>* node, int level=0)
{
    if (!node) {
        for (int i=0; i<level; ++i)
            cout << "  ";
        cout << "NULL" << endl;

        return;
    }

    printTree(node->left, level+1);

    for (int i=0; i<level; ++i)
        cout << "  ";
    cout << node->data << endl;

    printTree(node->right, level+1);
}

(رمز غير اختبار)