Удаление двоичного дерева в NULL после освобождения - PullRequest
Новая
       30

Удаление двоичного дерева в NULL после освобождения

0 голосов
/ 20 ноября 2018

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

void Delete(){
    struct BinaryTree* ptr = root;
    int element;
    printf("Enter element to delete : ");
    scanf("%d",&element);
    while(ptr){
        if(element>ptr->data)
            ptr = ptr->right;
        else if(element<ptr->data)
            ptr = ptr->left;
        else
            break;
    }
    if(ptr->left && ptr->right){
        struct BinaryTree **smallest = &(ptr);
        smallest = &((*smallest)->right);
        while((*smallest)->left){
            smallest = &((*smallest)->left);
        }
        ptr->data = (*smallest)->data;
        free(*smallest);
        *smallest = NULL;

    } else if(ptr->left){
            /*rest cases*/
    }

}

Приведенный выше код работает и устанавливает NODE в NULL.

Но когда я делаю эту процедуру таким образом, она не устанавливается в NULL. 

if(ptr->left && ptr->right){
    struct BinaryTree *smallest = ptr;
    smallest = smallest->right;
    while(smallest->left){
        smallest = smallest->left;
    }
    ptr->data = smallest->data;
    struct BinaryTree **refsmall = &smallest;
    free(*refsmall);
    *refsmall = NULL;
}

Разве эти два метода не одинаковы?Если нет, может кто-нибудь объяснить мне, чем они отличаются? Почему первый метод работает, а второй нет?

Ответы [ 2 ]

0 голосов
/ 20 ноября 2018

Вы должны избегать использования глобальных переменных в вашем коде.Если вы действительно хотите использовать глобальные переменные, первая версия удаления должна выглядеть следующим образом: 

void Delete(){
    /* at some point you will need to change the 'real' root, not the copy of it */
    struct BinaryTree **ptr = &root;
    int element;
    printf("Enter element to delete : ");
    scanf("%d",&element);
    while(*ptr){
        if(element > (*ptr)->data)
            ptr = &(*ptr)->right;
        else if(element < (*ptr)->data)
            ptr = &(*ptr)->left;
        else
            break;
    }
    if((*ptr)->left && (*ptr)->right){
        struct BinaryTree **smallest = ptr;
        smallest = &(*smallest)->right;
        while((*smallest)->left){
            smallest = &(*smallest)->left;
        }
        (*ptr)->data = (*smallest)->data;
        free(*smallest);
        *smallest = NULL;

    } else if((*ptr)->left){
            /*rest cases*/
    }
}

В первой версии вы не сможете удалить корень.

0 голосов
/ 20 ноября 2018 
struct node {
        struct node *l,*r;
        int data;
        };

void delnode(struct node **pp, int data)
{
struct node *del, *l,*r;

        // Walk the tree
while(*pp) {
        if ((*pp)->data < data) {pp = &(*pp)->l; continue;} 
        if ((*pp)->data > data) {pp = &(*pp)->r; continue;}
        break; // found it!
        }
if (!*pp) return; // not found

del = *pp;
l = del->l;
r = del->r;
        // If only one child it wil take del's place.
if (!r) *pp = l;
else if (!l) *pp = r;

        // del has two children.
        // pick one (R) child, and append the (L) other onto its (Leftmost) shoulder
else    {
        *pp = r;
        for (pp= &del->r; *pp; pp=&(*pp)->l) {;} // find Leftmost NULL pointer in the R tree
        *pp = l;
        }
free(del);
}
...