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()已返回并且您将能够打印其内容而不会调用未定义的行为。