Удаление узла в BST без указателя на его родительский

Question

Я пишу эту телефонную книгу по структурам, расположенным в BST. Она состоит из двух структур:

-Data структура:

typedef struct note 
{ 
    char name[LENGHT]; 
    char surname[LENGHT]; 
    int tel; 
}data; 

-Node структура:

typedef struct junction 
{ 
    data entry; 
    struct junction* left; 
    struct junction* right; 
}node; 

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

void mDestroy(node **dNode)    
{          
    if((*dNode)->left==NULL&&(*dNode)->right==NULL)    
    { 
     free(*dNode); 
     *dNode=NULL; 
     return; 
    } 
} 

Я вырезать остальную часть кода в отношении других случаев и поиска узла, чтобы заменить его, если это не лист. Проблема заключается в том, что когда я запускаю тестовый код, который создает root и 2 дополнительных узла, получает ввод с клавиатуры, отображает их, проходя через дерево в порядке (в алфавитном порядке), удаляет один из узлов без полномочий root и отображает их снова. Функция для обхода дерева:

void fDisplay(node *root) 
{ 
    if(root->left!=NULL) 
     fDisplay(root->left); 
    display(root->entry); 
    printf("\n\n"); 
    if(root->right!=NULL) 
     fDisplay(root->right); 
    return; 
} 

И функция ФАКТИЧЕСКИ отображения данных:

void display(data entry)     
{ 
    puts(entry.name); 
    puts(entry.surname); 
    printf("%d\n", entry.tel); 
    return; 
} 

выход на самом деле выглядит следующим образом:

name1 
surname1 
11111111111 

name2 
surname2 
2222222222 

name3 
surname3 
3333333333 

name1 
surname1 
11111111111 

name2 
surname2 
2222222222 

/*some gibberish*/ 
surname3 
3333333333 

Предположим, что мы удалить третью запись и оба связаны прямо к корню. Отображает третий узел, даже если в функции установлено значение NULL. Сначала я передал *node в качестве аргумента, затем переключился на **node, и я вызываю функцию следующим образом: mDestroy(&node1); Почему он не установил ссылку с родителя на NULL? Может ли он (удаление узла) даже быть выполнен без родительского узла, заданного в качестве параметра, или без вызова его с помощью root и поиска его в дереве для заданного значения?

Answer 1

Прежде всего, я предполагаю, что вы вызываете уничтожить что-то вроде этого:

node* aNode = //create a node 
node* parent = //create a node 
parent.right = aNode; 
mDestroy(&aNode); 

Который принимает адрес указателя на aNode и попутно, что в функцию уничтожения. Этот адрес затем разыменовывается в функции, чтобы дать вам доступ к указателю. Затем указатель освобождается и устанавливается в NULL. Теперь указатель aNode равен NULL, но указатель parent.right не указывает на NULL, он все еще указывает на старое местоположение aNode.

Итак, чтобы удалить узел из дерева, вы должны иметь доступ к указателю в дереве, указывающем на этот узел. Затем вы должны удалить узел и установить указатель в дереве на NULL.