0 
struct node *delete(struct node *root, int key)
{  

    struct node *remove_node;
    if (root == NULL){
        return root;
    }

    if ( key < root->key) {
        root->left = delete(root->left, key);

    } else if ( key > root->key) {
        root->right = delete(root->right,key);

    } else {

        if ((root->left == NULL) && (root->right != NULL)){
            remove_node = root->right;
            *root = *remove_node;
            deletetree(remove_node); // this is for free-ing the memory

        } else if ((root->right == NULL)  && (root->left != NULL)){
            remove_node = root->left;
            *root = *remove_node;
            deletetree(remove_node);

        } else if ((root->right == NULL)  && (root->left == NULL)){
            remove_node = root;
            root = NULL;

        } else {

            remove_node = successor(root);
            root->key = remove_node->key;
            root->right = delete(root->right, remove_node->key);
        }
    }

    if (root == NULL) {
        return root;

    if (balance_factor(root) == 2){
        if (balance_factor(root->left) == -1) {
            return single_right_rotation(root);

        } else if (balance_factor(root->left) == 1) {
            return double_left_rotation(root);
        }
    }

    if (balance_factor(root) == -2) {
        if (balance_factor(root->right) == -1) {
            return single_left_rotation(root);
        }
        else if (balance_factor(root->right) == 1)  { 
        return double_right_rotation(root);
            }
        }
    }

    return root;    
}

这是我删除 AVL 树中元素的代码。一切似乎工作正常，它处理节点 n 没有孩子、一个孩子和两个孩子的所有情况。但是由于一些奇怪的原因，它没有平衡树，也没有到达那个代码块。

希望有人可以帮助我调试代码，因为我找不到“确切”错误的来源。

提前致谢

PS：后继函数只返回要删除的节点右树上的最小元素，而删除树处理释放内存分配的东西。此外，我 100% 认为我的旋转可以正常工作，因为它在我的插入功能中运行良好。

4

1 回答 1

0

您可以使用临时根作为参考，您可以像这样进行更改：

struct node *localRoot = root;

而你把root改成localRoot，大概问题就解决了。我希望它会有所帮助。

于 2014-05-11T21:22:21.667 回答