لماذا فشل رمز C ++ الخاص بي لحذف جميع العقد في BST الخاص بي؟

Question

من المفترض أن يقوم هذا بإجراء BST وحذف كل عقدة، بما في ذلك عقدة الجذر. ومع ذلك، في النهاية، أحصل على رسالة "الجذر لا يزال لديه عقدة اليسار". لماذا لا يتم حذف كل العقد؟

void deleteTree()
{   
    deleteNode(root);
    if(root->right)
        cout << "root still has a right node" << endl;
    if(root->left)
        cout << "root still has a left node" << endl;
    root = 0;

}   

void deleteNode(node *p) 
{   
    if(p->left) 
    {   
        deleteNode(p->left);
        p->left = 0;
    }   
    if(p->right) 
    {   
        deleteNode(p->right);
        p->right = 0;
    }   

    cout << "Deleting node containing " << p->data << endl;
    delete p;
}   

Answer 1

لديك حذف p في نهايةالمطاف (root) ثم يحاول الوصول إلى محتوياتها في deleteTree(), ، أين root لم يعد نقاطا لتخصيص الذاكرة. والنتيجة ستكون غير محددة.

Answer 2

أنت حذف root. وبعد ثم يحاول رمزك الوصول إلى الذاكرة حيث كان ذلك.

أنت بخير في أرض السلوك غير المحددة هناك.

Answer 3

يجب أن لا dereference root بعد حذفها deleteNode. وبعد استخدم مصححا لتفقد السبب root->left غير فارغة.

Answer 4

أنت تبحث في root->left بعد أن تم حذف الجذر بالفعل، مما يجعله متوافلا للاستخدام في كتلة جديدة مخصصة.

Answer 5

سأغير ببساطة الشجرة نفسها، سيكون من الأسهل التعامل معها بعد ذلك:

struct Node
{
  Node(data_type data): mLeft(), mRight(), mData(data) {}
  Node(const Node& rhs): mLeft(), mRight(), mData(rhs.mData)
  {
    if (rhs.mLeft.get()) mLeft.reset(new Node(*rhs.mLeft));
    if (rhs.right.get()) mRight.reset(new Node(*rhs.mRight));
  }
  Node& operator=(Node rhs)
  {
    this->swap(rhs);
    return *this;
  }
  ~Node() { }

  void swap(Node& rhs)
  {
    using std::swap;
    swap(mLeft, rhs.mLeft);
    swap(mRight, rhs.mRight);
    swap(mData, rhs.mData);
  }

  Node* left() const { return mLeft.get(); }
  void left(std::auto_ptr<Node> node) { mLeft= node; }

  Node* right() const { return mRight.get(); }
  void right(std::auto_ptr<Node> node) { mRight = node; }

  data_type& data() { return mData; }
  const data_type& data() const { return mData; }

private:
  std::auto_ptr<Node> mLeft;
  std::auto_ptr<Node> mRight;
  data_type mData;
};

من خلال كونها موجهة نحو الكائنات، أصبحت كل عقدة مسؤولة الآن عن الذاكرة التي تعالجها. أيضا، باستخدام std::auto_ptr في الواجهة، توضح أنه يتطلب الأمر ملكية.

لاحظ أنه تم تصميمه للنسخ العميق، أي نهج آخر يتطلب boost::shared_ptr أو ما يعادلها. ونعم std::auto_ptr يتركك تتعامل مع نسخ بنفسك، لا سحر هناك.

هذا التصميم منظفا كبيرا من استخدام سهل C-struct مع الجميع قادر على التعامل مع الموارد. لا تزال لديك إمكانية الوصول الكامل إلى البيانات الأساسية عبر الملحق ... لكنها تهتم بعدم استدعاء السلوك غير المحدد ...

بالطبع، لا يزال بإمكانك تعطله:

Node& node = ...
delete node.left(); // haha

ولكن إذا كان C ++ قد يحمي من المشكلات غير المقصودة، فإنه يترك الباب مفتوحا إلى رمز الشر.