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() 函数的堆栈帧中分配，当函数 returns 帧被破坏导致 n 被释放。

您持有一个指向它在 Tree *t; 中的地址的指针，在函数返回后访问该指针是无效的。

你必须从 main() 传递指向 n2 和 n3 地址的指针，像这样

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

并更改 insert() 以直接接受指针而不是实例的本地副本。

根据我建议的解决方案，n2 和 n3 分配在 main() 的堆栈帧中，因此其生命周期等于整个程序生命周期，因为您将传递它们在 insert() 返回后，指向树中节点的指针仍将指向有效内存，您将能够在不调用未定义行为的情况下打印它们的内容。

C二叉搜索树插入指针问题

C Binary Search Tree Insertion Pointer Issue

c

algorithm

binary-search-tree