Удаление узлов в BST используя free (N) - PullRequest
Новая
       93

Удаление узлов в BST используя free (N)

0 голосов
/ 30 марта 2011

Я кодирую двоичное дерево поиска, и у меня возникли небольшие проблемы с поиском способа эффективного удаления узла.

У меня есть этот код: 

struct node* deleteNode(int i, struct node *N)

{
    if (N==NULL)
    {
        return NULL;
    }
    else if (i<N->value)
    {
        N->size--;
        N->lChild=deleteNode(i,N->lChild);
    }
    else if (i>N->value)
    {
        N->size--;
        N->rChild=deleteNode(i,N->rChild);
    }
    else if (N->lChild==NULL)
    {
        return N->rChild;
    }
    else if (N->rChild==NULL)
    {
        return N->lChild;
    }
    else
    {
        N->size--;
        N->value=findMin(N->rChild);
        N->rChild=deleteNode(N->value,N->rChild);
    }
    return N;
}

И N - этоструктура узла, которая имеет 5 полей: значение, lChild, rChild, размер, высота.Фактически, то, что я делаю здесь, это чтобы дерево не указывало на узел, который я хочу удалить, а когда я пытаюсь поместить что-то вроде: 

    else if (N->rChild==NULL)
    {
        free(N);
        N=NULL;
        return N->lChild;
    }

или любой похожий код,это не работаетМожет кто-нибудь указать мне правильное направление, пожалуйста?Спасибо.

1 Ответ

1 голос
/ 30 марта 2011

Прежде всего, вы говорите, что N = NULL, а затем вызываете N-> lchild N, это пустое значение и ничего не указывает, так как вы ожидаете получить значение lchild?

Поскольку это домашнее задание, я не буду давать прямой ответ, но намеки.

Чтобы удалить узел, проверьте, есть ли у него дочерние элементы, не освобождает ли он его, и удалите ссылки на него, такие как родительский дочерний элемент ptr. Если у него есть 1 дочерний объект, поменяйте ptr, который указывает на узел, который вы хотите удалить с дочерним, и освободите узел. То же самое относится, если у вас есть 2 детей.

...