这是用于移除avl树中的项目的代码，在移除功能中什么是“后继者”。 ？我得到这个错误 [英] this is a code for remove item in avl tree ,in remove function what is "successor" ? i get error for this

问题描述

struct node
{
    int key ;
    int h;
    node *left;
    node *root;
    node *right;
};


int h(struct node* x)
{
    if (x == NULL)
        return 0;
    return x->h;
}


int balanceavl(struct node *n)
{
    if (n == NULL)
        return 0;
    return (h(n->left) , h(n->right));


}


node* rightrotate(struct node *y)
{
    struct node *x = y->left;
    struct node *z = x->right;

    x->right = y;
    y->left = z;

    y->h = max(h(y->left), h(y->right))+1;
    x->h = max(h(x->left), h(x->right))+1;

    return x;
}


node* leftrotate(struct node *x)
{
    struct node *y = x->right;
    struct node *z = y->left;

    y->left = x;
    x->right = z;

    y->h = max(h(y->left), h(y->right))+1;
    x->h = max(h(x->left), h(x->right))+1;

    return y;
}


struct node *remove(struct node *root, int key)
{

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

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

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

    }
    else {

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

        } else if ((root->right == NULL)  && (root->left != NULL)){
            remove_node = root->left;
            *root = *remove_node;
            free(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 = remove(root->right, remove_node->key);
        }
    }

    if (root == NULL) {
        return root;
//lr
    if (balanceavl(root) == 2){
        if (balanceavl(root->left) == -1) {
            root->left =  leftrotate(root->left);
            return rightrotate(root);
//ll
        } else if (balanceavl(root->left) == 1) {
            return rightrotate(root);
        }
    }
//rr
    if (balanceavl(root) == -2) {
        if (balanceavl(root->right) == -1) {
            return leftrotate(root);
        }


        //rl
        else if (balanceavl(root->right) == 1)  {
                root->right = rightrotate(root->right);
                return leftrotate(root);
            }
        }
    }

    return root;
}

推荐答案

你错过了函数 node * successor（struct node * x ），你有没有复制一切？



/ Fredrik

You''re missing the function node* successor(struct node *x), did you copy everything when you got this?

/Fredrik

这篇关于这是用于移除avl树中的项目的代码，在移除功能中什么是“后继者”。 ？我得到这个错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！