从二叉树中删除节点

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;
        if (root == NULL){
            return;
        }
        while(current != NULL || current->data != data){
            if (current->data < data){
                current = current->right;
            }
            else if (current->data > data){
                current = current->left;
            }
        }
        if (current->left == NULL && current->right == NULL){
            free(current);
        }
        else if (current->left == NULL){
            TreeNode<T> *temp = current->right;
            current = temp;
            free(temp);
        }
        else if (current->right == NULL){
            TreeNode<T> *temp = current->left;
            current = temp;
            free(temp);
        }
        else{
            TreeNode<T> *leftmax = current->left;
            while (leftmax->right != NULL){
                leftmax = leftmax->right;
            }
            current = leftmax;
            free(leftmax);
        }
    }
}

我也尝试调试我的功能并更改了几次，但始终没有成功

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 是一个实用函数，用于查找子树中的最小值（用于替换具有两个子节点的节点）。