0

我正在编写代码以递归方式从 BST 中删除一个节点，主要是作为一个学习练习来实现递归并验证我对我使用的某些编码元素的理解。在这种情况下，问题似乎在于通过引用将指针传递给我的 BST 节点。

我的 BST 代码的 psrt 如下。（这不是我要实现或使用的代码。只是一个练习。我选择 BST 作为示例来实现一些我想用该语言尝试的东西）

标题 -

//BST.h
class TNode
{
public:
    TNode():data(0), left(0), right(0) {}
    int data;
    TNode* left;
    TNode* right;
};

class BST
{
private:
    TNode* Head;

public:
    BST();

    void InsertData(int data);
    void InsertNode(TNode* node);
    void DeleteData(int data);

private:
    void InsertDataPrivate(int data, TNode* &root); 
    void InsertNodePrivate(TNode* node, TNode* &root);
    void DeleteDataPrivate(int data, TNode* &root);
};

CPP -

//BST.cpp
#include "BST.h"

BST::BST(): Head(0)
{

}

void BST::InsertData(int data)
{
    InsertDataPrivate(data, Head);
}

void BST::InsertNode(TNode* node)
{
    InsertNodePrivate(node, Head);
}

void BST::DeleteData(int data)
{
    DeleteDataPrivate(data, Head);
}


void BST::InsertDataPrivate(int data, TNode* &root) 
{
    if(root == 0)
    {
        root = new TNode();
        root->data = data;
    }
    else if(data < root->data) InsertDataPrivate(data, root->left);
    else if(data > root->data) InsertDataPrivate(data, root->right); 
}

void BST::InsertNodePrivate(TNode* node, TNode* &root) 
{
    if(root == 0) // Deep Copy
    {
        root = new TNode();
        root->data = node->data;
    }

    else if(node->data < root->data) InsertNodePrivate(node, root->left);
    else if(node->data > root->data) InsertNodePrivate(node, root->right); 
}

void BST::DeleteDataPrivate(int data, TNode* &root)
{
    if( 0 == root ) return;

    if( root->data == data )
    {
        if(0 == root->left && 0 == root->right)
        {
            delete root;
            root = 0;
        }
        else if(0 == root->left)
        {
            TNode* current = root;
            root = root->right;
            delete current;
            current = 0;
        }
        else if(0 == root->right)
        {
            TNode* current = root;
            root = root->left;
            delete current;
            current = 0;
        }
        else
        {
            TNode* biggestOnLeft = root->left;
            TNode* smallestOnRight = root->right;
            int i = 0;
            while (biggestOnLeft->right) // check if left subtree is longer than right subtree
            {
                biggestOnLeft = biggestOnLeft->right;
                --i;
            }
            while (smallestOnRight->left)
            {
                smallestOnRight = smallestOnRight->left;
                ++i;
            }
            if(i < 0) // left subtree is longer than right subtree
            {
                root->data = biggestOnLeft->data;
                DeleteDataPrivate(biggestOnLeft->data, biggestOnLeft);
            }
            else // right subtree is longer than or equal in size to left subtree
            {
                root->data = smallestOnRight->data;
                DeleteDataPrivate(smallestOnRight->data, smallestOnRight);
            }
        }
    }
    else if(data < root->data && 0 !=root->left)
    {
        DeleteDataPrivate(data, root->left);
    }
    else if(data > root->data && 0 !=root->right)
    {
        DeleteDataPrivate(data, root->right);
    }
}

我的测试代码如下 -

//TestMain.cpp
#include "stdafx.h"
#include "BST.h"


int _tmain(int argc, _TCHAR* argv[])
{
    BST bst;

    bst.InsertData(32);
    bst.InsertData(46);
    bst.InsertData(3463);
    bst.InsertData(32);
    bst.InsertData(856);
    bst.InsertData(8098);
    bst.InsertData(345);
    bst.InsertData(234554);
    bst.InsertData(77);
    bst.InsertData(9);
    bst.InsertData(15);
    bst.InsertData(390);
    bst.InsertData(350);
    bst.InsertData(400);
    bst.InsertData(76);
    bst.InsertData(78);
    bst.InsertData(355);
    bst.DeleteData(77);

    return 0;
}

在我说bst.DeleteData(77);我有问题的最后一步。带有“77”的节点被删除，并被“78”替换，就像你从 BST 中删除一个带有两个子节点的节点一样。但是，在删除具有“77”的父节点之前删除具有“78”的节点后，仍然指向非空位置。

我正在调用我的私有函数，该函数DeleteDataPrivate(int data, TNode* &root);在删除 TNode 指针后将其设置为 NULL。此外，我在函数中通过引用传递指针，以便在递归堆栈展开时将 NULL 值分配给已删除的节点指针。这不会发生。有人可以解释我在这里做错了什么吗？

谢谢你。

钦梅

更新

根据 Dan 在下面的评论，问题在于将值传递给局部变量，这些变量复制了我的指针并且没有分配回任何东西。我已经修改了我的函数以通过使用指向指针的指针来解决此问题，以便展开递归返回的 TNode 指针的值存储在内存中的正确位置，而不是存储在 TNode 指针的某个副本中。

修改后的功能如下

void BST::DeleteDataPrivate(int data, TNode* &root)
{
    if( 0 == root ) return;

    if( root->data == data )
    {
        if(0 == root->left && 0 == root->right)
        {
            delete root;
            root = 0;
        }
        else if(0 == root->left)
        {
            TNode* current = root;
            root = root->right;
            delete current;
            current = 0;
        }
        else if(0 == root->right)
        {
            TNode* current = root;
            root = root->left;
            delete current;
            current = 0;
        }
        else
        {
            TNode* biggestOnLeft = root->left;
            TNode* smallestOnRight = root->right;
            int i = 0;
            while (biggestOnLeft->right) // check if left subtree is longer than right subtree
            {
                biggestOnLeft = biggestOnLeft->right;
                --i;
            }
            while (smallestOnRight->left)
            {
                smallestOnRight = smallestOnRight->left;
                ++i;
            }
            TNode** locationOfDeletedNode = 0;
            if(i < 0) // left subtree is longer than right subtree
            {

                locationOfDeletedNode = &(root->left);
                while(*locationOfDeletedNode != biggestOnLeft) locationOfDeletedNode = &((*locationOfDeletedNode)->right);
            }
            else // right subtree is longer than or equal in size to left subtree
            {
                locationOfDeletedNode = &(root->right);
                while(*locationOfDeletedNode != smallestOnRight) locationOfDeletedNode = &((*locationOfDeletedNode)->left);

            }
            root->data = (*locationOfDeletedNode)->data;
            DeleteDataPrivate((*locationOfDeletedNode)->data, *locationOfDeletedNode);
        }
    }
    else if(data < root->data && 0 !=root->left)
    {
        DeleteDataPrivate(data, root->left);
    }
    else if(data > root->data && 0 !=root->right)
    {
        DeleteDataPrivate(data, root->right);
    }
}

当然，这可以更好地构建，但我的目标是在这里学习简单但棘手的东西，感谢 Dan 和其他人，我在这里做到了。

4

2 回答 2

5

你打电话时

DeleteDataPrivate(biggestOnLeft->data, biggestOnLeft);

它只是分配给局部变量biggestOnLeft，它没有分配给任何对象的成员。

因为当你这样做时

TNode* biggestOnLeft = root->left;

它创建了一个新变量，它是 的副本，root->left而不是同一件事。

修正想法

您可以尝试从根目录开始，然后biggestOnLeft做smallestOnRight

while (biggestOnLeft->right->right)

然后你可以打电话

DeleteDataPrivate(biggestOnLeft->data, biggestOnLeft->right);

免责声明：我没有对此进行测试，可能会出现错字或其他错误。

于 2012-09-25T17:33:07.390 回答
-2

您不能通过引用 TNode 将 NULL 分配给指针，因为引用变量不能为 NULL。请参阅C++ 通过引用传递指针并分配默认值

于 2012-09-25T17:27:26.843 回答