C Binary Search Tree Insertion Pointer Issue

Question

Я пытаюсь внедрить двоичное дерево поиска, но сталкивается с проблемами.

Я реализовал дерево, используя следующий узел и структуры Дерево

typedef struct Node { 
    double value; 

    struct Node *parent; 
    struct Node *right_child; 
    struct Node *left_child; 
} Node; 

typedef struct Tree { 
    struct Node *root; 
} Tree; 

Ниже функция вставки

void insert(Tree *t, Node n) { 

    Node *x = t->root, *y = NULL; 

    //follow tree down until we reach a leaf of the tree 
    while (x != NULL) { 

     //save last non-NULL value. We will insert node n as a child to this leaf. 
     y = x; 

     if (n.value < x->value) { 
      x = x->left_child; 
     } else { 
      x = x->right_child; 
     } 

    } 

    //The parent of the node to insert is the leaf we reached 
    n.parent = y; 

    //If n is greater than y then it is its right child and vice-versa. 
    if (n.value > y->value) { 
     y->right_child = &n; 
    } else { 
     y->left_child = &n; 
    } 

} 

Когда я запускаю это мой основной метод

int main(void) { 

    Node n1; 
    Node n2; 
    Node n3; 


    n1.value = 4; 
    n1.parent = NULL; 
    n1.left_child = NULL; 
    n1.right_child = NULL; 

    n2.value = 2; 
    n2.parent = NULL; 
    n2.left_child = NULL; 
    n2.right_child = NULL; 

    n3.value = 1; 
    n3.parent = NULL; 
    n3.left_child = NULL; 
    n3.right_child = NULL; 

    Tree t; 

    t.root = &n1; 

    insert(&t,n2); 

    insert(&t,n3); 

    printf("n1 left child %f \n", n1.left_child->value); 

    return EXIT_SUCCESS; 
} 

Он печатает n1 left child 1.000000, что является неправильным. Это должно быть 2. Я пробовал вставлять инструкции печати для отладки и кажется, что функция insert назначает детям в конце неправильный указатель (то есть узел не сохраняется после его установки). Поэтому я думаю, что это означает, что что-то не так с y. Я не думаю, что y представляет то, что я хочу, чтобы оно было указателем на листовой узел в дереве (где я буду вставлять новый узел n).

Answer 1

Вы берете адрес временной переменной и вы разыгрываете ее после ее освобождения, а это означает, что ваша программа вызывает неопределенное поведение. В

void insert(Tree *t, Node n) 

Параметр Node n выделяется в кадре стека функции insert(), когда функция возвращает кадр разрушается приводит к n быть высвобождены.

Вы удерживаете указатель на его адрес в Tree *t;, доступ к этому указателю недействителен после возврата функции.

Вы должны передать указатель на адрес n2 и n3 от main(), как этот

insert(&t, &n2); 
insert(&t, &n3); 

и изменить insert() непосредственно принимать указатель вместо локальной копии экземпляра.

С моим Предложенное решение n2 и n3 выделяются в пределах стека кадра main() и, таким образом, имеют продолжительность жизни равную всей жизни программы, так как вы бы передавая их адрес указатели на узлы в дереве будет по-прежнему указывают на действительная память после того, как insert() вернулась, и вы сможете распечатать их содержимое, не вызывая неопределенное поведение.