C二叉搜索樹插入指針問題

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函數將末尾的子對象指派給錯誤的指針（即n2節點在插入後不會保留）。所以我認爲這意味着y有問題。我不認爲y正在代表我想要的是哪一個指針指向樹中的葉節點（我將插入新節點n）。

Answer 1

您正在接受一個臨時變量的地址，並在解除分配它後取消引用它，這意味着您的程序將調用未定義的行爲。在

void insert(Tree *t, Node n) 

的Node n參數是insert()函數的堆棧幀中分配，當該函數返回該幀被破壞導致n被釋放。

您持有一個指向其地址的指針Tree *t;，該函數返回後訪問該指針無效。

必須從main()一個指針傳遞的n2和n3地址，這樣

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

，改變insert()直接接受指針而不是實例的本地副本。

隨着我建議的解決方案n2和n3是main()棧幀中分配，因而具有壽命等於整個項目生命週期，因爲你會通過他們的地址指針，以你的樹仍然指向節點insert()已返回並且您將能夠打印其內容而不會調用未定義的行爲。