从二叉树中删除节点

Question

我试图用 C++ 实现二叉树，但是我的 deleteNode 函数无法正常工作。我的 deleteNode 函数出了什么问题？

template<class T>
class TreeNode {
public:
    T data;
    TreeNode<T> *right;
    TreeNode<T> *left;

    TreeNode(T data) {
        this->data = data;
        right = NULL;
        left = NULL;
    }
};

template<class T>
class Tree {
public:
    TreeNode<T> *root;

    Tree() {
        root = NULL;
    }

    void deleteNode(T data) {
        TreeNode<T> *current = root;
        TreeNode<T> *parent = NULL;

        while (current != NULL && current->data != data) {
            parent = current;
            if (current->data < data) {
                current = current->right;
            } else if (current->data > data) {
                current = current->left;
            }
        }

        if (current == NULL) {
            return;
        }

        if (current->left == NULL || current->right == NULL) {
            TreeNode<T> *newCurrent = (current->left == NULL) ? current->right : current->left;

            if (parent == NULL) {
                root = newCurrent;
            } else if (current == parent->left) {
                parent->left = newCurrent;
            } else {
                parent->right = newCurrent;
            }

            delete current;
        }
        else {
            TreeNode<T> *successorParent = current;
            TreeNode<T> *successor = current->right;

            while (successor->left != NULL) {
                successorParent = successor;
                successor = successor->left;
            }

            current->data = successor->data;

            if (successorParent->left == successor) {
                successorParent->left = successor->right;
            } else {
                successorParent->right = successor->right;
            }

            delete successor;
        }
    }
}

我也尝试调试我的功能并更改了几次内容，但始终不起作用。

（新版本的deleteNode怎么样？它可以工作，但并非在所有情况下都有效，我不知道为什么。）

Answer 1

deleteNode 函数中有一些问题需要解决。以下是更正：

更新While循环中的条件： 将 while 循环中的条件从 while (current != NULL || current->data != data) 更改为 while (current != NULL && current->data != data)。这确保了只要 current 不为 NULL 并且未找到数据，循环就会继续。

处理节点有两个子节点的情况： 当要删除的节点有两个子节点时，需要用左子树中的最大值替换该节点的数据，然后递归删除该最大节点。这是删除具有两个子节点的常见策略。

更新节点删除逻辑： 您应该根据子节点的数量以不同的方式处理节点的删除，而不是直接使用 free(current) 。

这是更正后的deleteNode函数：

template<class T>
void Tree<T>::deleteNode(T data) {
    root = deleteNodeHelper(root, data);
}

template<class T>
TreeNode<T>* Tree<T>::deleteNodeHelper(TreeNode<T>* root, T data) {
    if (root == NULL) {
        return root;
    }

    if (data < root->data) {
        root->left = deleteNodeHelper(root->left, data);
    } else if (data > root->data) {
        root->right = deleteNodeHelper(root->right, data);
    } else {
        // Node with only one child or no child
        if (root->left == NULL) {
            TreeNode<T>* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            TreeNode<T>* temp = root->left;
            free(root);
            return temp;
        }

        // Node with two children
        TreeNode<T>* temp = findMin(root->right);
        root->data = temp->data;
        root->right = deleteNodeHelper(root->right, temp->data);
    }

    return root;
}

template<class T>
TreeNode<T>* Tree<T>::findMin(TreeNode<T>* root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

在此更正版本中，deleteNodeHelper 是一个处理删除逻辑的递归辅助函数，findMin 是一个实用函数，用于查找子树中的最小值（用于替换具有两个子节点的节点）。