c++ - BST - 节点神秘地被分配到错误的一侧

Question

我是这样写的:

#include <stdio.h>
#include <string.h>

struct node {
    int value;
    bool right;
    bool left;
    node * rightChild;
    node * leftChild;
};

int insertNode(int value, node* parent, int h) {
    if (value < parent->value) {
        if (!parent->left) {
            node temp = {value, NULL, NULL};
            parent->leftChild = &temp;
            parent->left = true;
            return h + 1;
        }

        return insertNode(value, parent->leftChild, h + 1);
    }
    if (value > parent->value) {
        if (!parent->right) {
            node temp = {value, NULL, NULL};
            if (value == 1)
                printf("here\n\n");
            parent->rightChild = &temp;
            parent->right = true;
            return h + 1;
        }
        return insertNode(value, parent->rightChild, h + 1);
    }
}



int main() {

    int N; scanf("%d", &N);

    int values[N];

    for (int i = 0; i < N; i++)
        scanf("%d", &values[i]);

    node base = {values[0], false, false, NULL, NULL};
    printf("0\n");
    int counter = 0;

    for (int i = 1; i < N; i++) {
        int height = insertNode(values[i], &base, 0);
        counter += height;
        printf("%d\n", counter);
    }
}

所以，我编写了这个程序，它应该做的是从输入构建一个 BST，保留一个计数器，其中包含每个节点的高度总和，并在每次插入节点时输出该计数器的值。

对于大多数测试用例，它可以正常工作，但对于这个测试用例，它不会输出预期的结果。

Input : 8 3 5 1 6 8 7 4 2
Expected Output: 0 1 2 4 7 11 13 15
Obtained Output: 0 1 2 4 7 11 14 18

我追查了这个错误，看起来 1 被插入了，因为 3 的右 child 和 3 的左 child 都没有被插入树中代码中只有一个条件，其中一个节点被设置为另一个节点的右子节点，我检查过，1 永远不会落入该条件。这怎么可能？

老实说，我现在快要被这个搞疯了，有人能帮我理解我做错了什么吗

Answer 1

node temp = {value, NULL, NULL};
if (value == 1)
    printf("here\n\n");
parent->rightChild = &temp;

想想 temp 会发生什么(它超出了范围)，然后想想 parent->rightChild 结果会发生什么(它变成了悬空指针)。对该指针的任何后续访问都会导致您的程序具有未定义的行为，因此显然是随机结果。

您需要动态分配您的节点对象，以便您可以自己控制它们的生命周期(包括将它们扩展到那个小块范围之外)。任何 BST 实现的好例子都应该表明这一点。