c++ - 从 C++ 二进制搜索树中删除一个节点(类不是结构)

Question

出于学术目的，我正在尝试使用 C++ 管理 BST。

除了 DeleteNode 函数，我在任何地方都没有遇到问题，还有 我选择用 class 而不是 struct 来实现这个数据结构。

问题是，我无法弄清楚如何使删除功能正常工作，我经常遇到 0xDDDDDDDD 错误，我的调试器说，有时我可以删除节点，有时我的程序崩溃。

我认为这可能是指针的问题，但我无法弄清楚我哪里做错了。

这是我的删除节点功能，我遇到了严重的麻烦:

编辑:无子删除案例完美，令我生气的是单子(monad)删除案例。

 //function that delete a selected node
    void DeleteNode(TreeNode* root,int key) {
        /*we got three case here:*/


        //until we find the right node with value in the tree
        if (root->getValue() != key && root != nullptr) {
            if (root->getValue() > key) {
                DeleteNode(root->Left, key);
            }
            else if (root->getValue() < key) {
                DeleteNode(root->Right, key);
            }
        }
        else { //when we found the right node, then operate 
               /* THIS WORKS PERFECTLY! */

            //first case: our node got no right and left son
            if (!root->Left && !root->Right) {

                TreeNode* tmp = root->Father; 

                if (tmp->Left == root) { //if the son is a left son
                    tmp->Left = nullptr;
                    delete root;
                }
                else if (tmp->Right == root) { //if the son is a right son
                    tmp->Right = nullptr;
                    delete root;
                }

            }
            //second case: our node got a left but no right son
            /* THIS ONE DOESN'T WORK. */
            else if (!root->Right) { 
                TreeNode *tmp = root;
                root = root->Left; //new root is the left son of the root
                root->Father = tmp->Father; //linking the father to the new son
                tmp->Father->Left = root; //linking the son to the new father

                delete tmp;                     

                std::cout << "Erased!" << std::endl;
            }
            else if (!root->Left) {
                TreeNode *tmp = root;
                root = root->Right; //new root is the right son of the root
                root->Father = tmp->Father; //linking the father to the new son
                tmp->Father->Right = root; //linking the son to the new father

                delete tmp;

                std::cout << "Erased!" << std::endl;

            }
        }


        }

我尝试了很多组合，但每次的结果都是一样的:它在第一次出现 InOrder 显示函数时崩溃。 (如果没有，该函数只会删除第一个节点，然后在我尝试删除一个新节点时崩溃。)

这是一个简单的主程序，我正在尝试执行删除操作:

int main()
{

    TreeNode root;

    root.insertNode(&root,50);
    root.insertNode(&root,30);
    root.insertNode(&root,20);
    root.insertNode(&root,40);
    root.insertNode(&root,70);
    root.insertNode(&root,60);
    root.insertNode(&root,80);

    for (int i = 0; i < 5; i++) {
        int n;
        cin >> n;

        root.DeleteNode(&root, n);

        cout << "In-Order: "; root.inOrder(&root);
        cout << endl;
        cout << "Pre-Order: "; root.preOrder(&root);
        cout << endl;
        cout << "Post-Order: "; root.postOrder(&root);
        cout << endl;
    }

}

这是我完整的 BST 代码(除了我之前提交的 delete 代码，只是为了更完整地理解我的代码)

    class TreeNode {
private:
    int value;
    TreeNode* Left;
    TreeNode* Right;
    TreeNode* Father;

public:

    //constructor
    TreeNode() {
        this->Right = nullptr;
        this->Left = nullptr;
        this->Father = nullptr;
    }

    TreeNode(int value) {
        this->value = value;
        this->Right = nullptr;
        this->Left = nullptr;
        this->Father = nullptr;
    }

    //functions
    int getValue() { return value; }
    void setValue(int value) { this->value = value; }


    //function to create a new node and insert a value into it
    TreeNode* insertNode(TreeNode* root, int value) {

        if (root->getValue() == NULL) {
            root->setValue(value);
            root->Father = nullptr;
        }

        else {
            if (value > root->getValue()) {
                if (root->Right) {
                    insertNode(root->Right, value);
                }
                else
                    root->Right = new TreeNode(value);
                    root->Right->Father = root;
            }
            else if (value < root->getValue()) {
                if (root->Left) {
                    insertNode(root->Left, value);
                }
                else
                    root->Left = new TreeNode(value);
                    root->Left->Father = root;
            }

        }
        return root;
    }

    //function to search a value into a BST
    TreeNode* SearchNode(TreeNode* root, int key) {

        if (root->getValue() == key) {
            return root;
        }
        else if (root->getValue() < key) {
            if (root->Right) {
                SearchNode(root->Right, key);
            }
            else return nullptr;
        }
        else if (root->getValue() > key) {
            if (root->Left) {
                SearchNode(root->Left, key);
            }
            else return nullptr;
        }
    }

    //function that return the height of the tree 
    int TreeHeigth(TreeNode* root) {

        int heigth;

        if (root == nullptr) {
            return 0;
        }
        else {
            return heigth = 1 + max(TreeHeigth(root->Left), TreeHeigth(root->Right));
        }
    }

    //function that returns the number of the nodes
    int CountTreeNode(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        else {
            return CountTreeNode(root->Left) + CountTreeNode(root->Right) + 1;
        }
    }

    //function that returns the minimum values into the tree
    TreeNode* MinimumNode(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }

        while (root->Left != nullptr) {
            root = root->Left;
        }

        return root;
    }

    //function that returns the maximum value into the tree  
    TreeNode* MaximumNode(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }

        while (root->Right != nullptr) {
            root = root->Right;
        }

        return root;
    }

    //function that returns a successor of a given nodeb
    TreeNode* SuccessorNode(TreeNode* node) {

        //first case: our node got a rigth subtree:
        if (node->Right != nullptr) {
            return MinimumNode(node->Right); 
        }

        //second case: our node doesnt got a right subtree: lets get 
        //upper in the tree until our node isn't a left child.

        TreeNode* Ancestor = node->Father;

        while (Ancestor != nullptr && node == Ancestor->Right) {
            node = Ancestor;
            Ancestor = Ancestor->Father;
        }

    }

    //function tht returns a predecessor of a given node
    TreeNode* PredecessorNode(TreeNode* node) {

        //first case: (inverse to successor) our node got a left subtree:
        if (node->Left != nullptr) {
            return MaximumNode(node->Left);
        }

        TreeNode* Ancestor;

            if (node->Father == nullptr)
                return nullptr;
            else 
                Ancestor = node->Father;

        while (Ancestor != nullptr && node == Ancestor->Left) {
            node = Ancestor;
            Ancestor = Ancestor->Father;
        }

        return Ancestor;
    }



    //function that prints information about nodes
    void InfoNode(TreeNode *root) {

        root != nullptr ? std::cout << "Nodo corrente: " << root->getValue() << std::endl
            : std::cout << "Nodo corrente: " << "NULL" << std::endl;

        root->Father != nullptr? std::cout << "Padre: " << root->Father->getValue() << std::endl
            : std::cout << "Padre: " << "NULL" << std::endl;

        root->Left != nullptr ? std::cout << "Figlio SX: " << root->Left->getValue() << std::endl
            : std::cout << "Figlio SX: " << "NULL" << std::endl;

        root->Right!= nullptr ? std::cout << "Figlio DX: " << (root->Right)->getValue() << std::endl
            : std::cout << "Figlio DX: " << "NULL" << std::endl;
    }

    //visits of a tree
    void preOrder(TreeNode* root) {
        if (root != nullptr) {
            std::cout << root->getValue() << " ";
            preOrder(root->Left);
            preOrder(root->Right);
        }
    }

    void inOrder(TreeNode* root) {
        if (root != nullptr) {
            inOrder(root->Left);
            std::cout << root->getValue() << " ";
            inOrder(root->Right);
        }

    }

    void postOrder(TreeNode *root) {
        if (root != nullptr) {
            postOrder(root->Left);
            postOrder(root->Right);
            std::cout << root->getValue() << " ";
        }
    }


    //max between 2 numbers
    int max(int a, int b) {
        return a > b ? a : b;
    }


    };

还有我正在尝试处理的树的表示:

          50
       /     \
      30      70
     /  \    /  \
   20   40  60   80 

我哪里做错了？

Answer 1

看这个条件:root->getValue() != key && root != nullptr，这首先调用 getValue 然后检查 root 具有合法值(value)。交换它们(root != nullptr && root->getValue() != key)。

最后我认为您必须将最后一行更改为 tmp->Father->Left = root; 以解决崩溃问题。

TreeNode *tmp = root;
root = root->Right; //new root is the right son of the root
root->Father = tmp->Father; //linking the father to the new son
tmp->Father->Right = root; //linking the son to the new father

PS:也为对方做这个交换...

注意:在 root 是他父亲的左 child 之前，这是真的，否则你的代码是真的。准确地说，如果 root 的父亲执行 tmp->Father->Left = root; else tmp->Father->Right = root，则必须检查 root 是否为左子;

注意:如您所述，您的代码不处理删除具有两个子节点的节点。