1

わかりましたので、修正されたと思いましたが、まったく一貫性のない結果が得られています。私はそれをゼロから書き直して、新たに始めました。これが私の結果です。エラーもクラッシュも発生しません。エラーが削除されないだけです。それは木を完全に台無しにし、私にさらにたくさんの葉を与え、すべてを混ぜ合わせます. 他にどこに行くべきかわからない

template <class T>
void BST<T>::remove(struct Node<T>*& root, const T& x)
{
   Node<T>* ptr = root;
   bool found = false;
   Node<T>* parent;


   while (ptr != NULL && !found)
   {
       if (x < ptr->data)
       {
           parent = ptr;
           ptr = ptr->left;
       }
       else if (x > ptr->data)
       {
           parent = ptr;
           ptr = ptr->right;
       }
       else
           found = true;
   }

   if (found == false)
       return;
   else
   {
       if(ptr->left != NULL && ptr->right != NULL)
       {
           Node<T>* inOrderPtr = ptr->left;
           parent = ptr;
           while (inOrderPtr->right != NULL)
           {
               parent = inOrderPtr;
               inOrderPtr = inOrderPtr->right;
           }

           ptr->data = inOrderPtr->data;
           ptr = inOrderPtr;
       }
    Node<T>* subPtr = ptr->left;
    if (subPtr == NULL)
        subPtr = ptr->right;

    else if (parent->left == ptr)
        parent->left = subPtr;

    else
        parent->right = subPtr;

    delete ptr;
    }
4

3 に答える 3

1

実際に起こっていたのは、検索が逆になった可能性があるため、実際にはうまくいきましたが、データが実際には正しく一致していなかったため、壁にぶつかったようです. 

if (root->data < x)
        remove(root->left, x);
    else 
        remove(root->right, x);

になるはずだった

if(x < root->data)
remove(root->left, x);
else
remove(root->right, x);
于 2008-10-29T07:09:09.427 に答える
0

remove()3番目のケース（「これが正しいかどうかわからない」というコメントがある場合）では、再帰的に呼び出すべきではありません。削除するノードに 2 つの子がある場合、必要なのは、左の子の右端の子を見つけることです (実行しているように、結果のノードは に格納されますparent)。このノードには右の子がありません - その右の子が削除するノードの右の子になるようにしてください。次に、root変数をその左の子に変更します。ノードのメンバーを変更したり、再帰的dataに呼び出したりする必要はありません。remove

写真で：

前：
         r <-ここにルートポイント
       / \
      / \
     ab
    / \ / \
   xcyy
      / \
     xd
        /
       バツ

後：
      a <-- ここにルートポイント
     / \
    xc
       / \
      xd
         / \
        xb
           / \
          yy
于 2008-10-29T05:22:29.190 に答える
0

ツリーで見つかった各 T は一意ですか? それらはあなたのコードからのもののようです...

これはうまくいくはずです：

それ以外の場合は、ルート ノードを削除します。

Node<T> *tmp_r = root->left;
Node<T> *parent = root;
while (tmp_r->right != NULL)
{
    parent = tmp_r;
    tmp_r = tmp_r->right;
}
Node<T> *tmp_l = tmp_r;
while (tmp_l->left != NULL)
    tmp_l = tmp_l->left;

tmp_l->left = root->left;
tmp_r->right = root->right;
parent->right = NULL;

parent = root;
root = tmp_r;
delete parent;
于 2008-10-29T05:57:56.107 に答える