1

Raw BinaryTree を作成しました。このツリーでは、挿入は BSTとは異なり、次のようになります::

  1. ツリーが空の場合は、値を追加してルートにします。(仮に30人)
  2. ツリーが空でない場合は、親の値 (30) を入力し、左側のサブツリーに新しい値 (20) を追加します。
  3. 左のサブツリーが空でない場合は、値 (20) を右のサブツリーに挿入します。
  4. 次の挿入では、親の値を再度取得して、値を追加する場所を決定します。＆ すぐ..

2 つの子を持つノードを削除しようとする場合を除いて、正常に動作します。削除に使用するメソッドはdeleteWithCopyです。

私のインストラクターが言ったように、deletewithcopy は次のとおりです。 1. 削除するノード (temp) の親を見つけます。2. temp (削除するノード) が「父」の右の子である場合、一時の直下の後継者を見つけます 3. 一時 (削除するノード) が「父」の左の子である場合、一時の直系の先行を見つけます 4. 値を交換しますtemp とその前身/後継者 5. temp を削除します (現在はツリーの葉です)。

NOW 後継者と先行者を見つける方法。

サクセサ = ノードの論理的サクセサは、左サブツリーの右端の子です

Predecessor = ノードの論理的な先行は、右側のサブツリーの一番左の子です。

アルゴリズムに従って関数を作成しましたが、削除した後、ツリーをトラバース (または印刷) すると、実行時エラー、binarytree.exe の 0x008B5853 で未処理の例外が表示されます: これは、「0xFEEEFEEE は、Visual C++ で解放されたメモリをマークするために使用されます」のエラーです。

私はこのことを何度も何度もドライランしました。私がアクセスしようとしている範囲外のものはメモリにありません。すべてのルーズエンドを修正しましたが、それでも:(

関数は次のとおりです。

void BinaryTree<mytype>::deletewithTwoChild(BTNode<mytype> *temp)
{
    BTNode<mytype> *father = findfather(temp, root);    //found address of father of temp node & stored it in pointer
    BTNode<mytype> *leaf = temp;    //created a copy of temp node

    /////CASE 1 (for predecessor)
if(temp==root || father->left==temp)    //if temp is left child of its father then
{
    leaf = leaf->left;  //move leaf 1 time left
    while(leaf->right!=0 )  //until leaf reaches the right most node of left subtree
    {
        leaf = leaf->right; //move leaf 1 time to right
    }
    //swapping values
    mytype var = leaf->key_value;   //created a template variable to store leaf's key
    leaf->key_value = temp->key_value;  //assigning temp's key to leaf
    temp->key_value = var;  //assigning leaf's key to temp
    if(leaf->right!=0)  //if leaf has right child then call deletewithOneChild function
    {
        deletewithOneChild(leaf);   //call to respective function
    }
    else if(leaf->left==0 && leaf->right==0) //if leaf has no children then
    {
        deleteWithNoChild(leaf);    //call to respective function
    }
}
/////CASE 2 (for successor)
else if(father->right==temp)    //if temp is right child of its father, then
{
    leaf = leaf->right; //move leaf 1 time right
    while(leaf->left!=0)    //until leaf reaches the last node of tree which has no child
    {
        leaf = leaf->left;  //move leaf 1 time to left
    }
    //swapping values
    mytype var = leaf->key_value;   //created a template variable to store leaf's key
    leaf->key_value = temp->key_value;  //assigning temp's key to leaf
    temp->key_value = var;  //assigning leaf's key to temp
    if(leaf->right!=0)  //if leaf has right child then call deletewithOneChild function
    {
        deletewithOneChild(leaf);   //call to respective function
    }
    else if(leaf->left==0 && leaf->right==0) //if leaf has no children then
    {
        deleteWithNoChild(leaf);    //call to respective function
    }
}

}

私が使用しているデータセット：

               30
              /  \
             20  80
            /   /  \
          10  40    120
               \     / \ 
              60  100 140
              / \     /  \
            50  70   130 150

実行時エラーが表示されたときに、ノード 80、60、120、140 を削除しようとしています。Plz help :(( また、30 が削除された場合にツリーを処理する方法についてもガイドが必要です。

4

1 に答える 1

0

私が知っているように、後継者と前任者の定義は異なります。

後継者 : 右側のサブツリーの最小ノード、つまり、右側のサブツリーの最も左のノード。 Predecessor : 左のサブツリーの最大ノード、つまり、左のサブツリーの右端のノード。

問題 1に戻ります。if-elseケース1で値を交換した後の状態に気付きましleaf->rightた. その結果、値を交換した後に削除関数が呼び出されることはありません。これにより、間違った BST の問題が発生したり、さらに悪いことに、プログラムがクラッシュする可能性があります。したがって、この場合の条件は次のようになります。nullleaf->leftnullif-else

// leaf->right always be null, only need to verify leaf->left.
if (leaf->left != 0)
{
    deleteWithOneNode(leaf);
}
else 
{
    deleteWithNoChild(leaf);
}

問題2。私が知っているように、BST での 1 つのノードの削除には、先行ノードまたは後続ノードを選択するルールがなく、削除されたノードの親 (父) ノードは、ノードの値のみを交換するのではなく、ノード全体を交換する場合にのみ使用されます。したがって、私の削除機能は次のようになります。

void BinaryTree<myType>::delete(BTNode<myType>* node, BTNode<myType>* parent)
{
    if (node->right) // find successor first
    {
        BTNode* ptrParent = node;
        BTNode* ptr = node->right;
        while (ptr->left)
        {
            ptrParnet = ptr;
            ptr = ptr->left;
        }

        // Since the ptr will be delete, we only assign the value of ptr to the value node
        node->key_value = ptr->key_value;

        if (node == ptrParent)
        {
            ptrParnet->right = ptr->right;
        }
        else
        {
            ptrParent->left = ptr->right;
        }
        delete ptr;            
    }
    else if (node->left) // find predecessor
    {
        BTNode* ptrParent = node;
        BTNode* ptr = node->left;
        while (ptr->right)
        {
            ptrParent = ptr;
            ptr = ptr->right;
        }

        // Since the ptr will be delete, we only assign the value of ptr to the value node
        node->key_value = ptr->key_value;

        if (node == ptrParent)
        {
            ptrParent->left = ptr->left;
        }
        else
        {
            ptrParent->right = ptr->left;
        }
        delete ptr; 
    }
    else
    {
        if (node->key_value > parent->key_value)
        {
            parent->right = NULL;
        }
        else
        {
            parent->left = NULL;
        }
        delete node;
    }
}

関数を使用すると、30 を削除した後のツリーは次のようになります。

         40
       /    \
     20      80
    /       /   \
   10      60    120
          /  \   /  \
        50   70 100 140
                    /  \
                  130  150
于 2016-11-23T03:16:53.943 に答える