In-order 遍历偏离内存中的其他位置

Question

我正在尝试对 BST 进行 in-order 遍历。在 inOrder() 的第一次调用中，一切都按预期工作：*node 指向根，在调试器中，我可以看到整个三个都被正确表示（即，根的后代被正确表示）。

然而，在下一次对根的左侧 child 的调用中（即 *node 现在表示根的左侧 child），树不再正确表示。唯一正确的是 *node 的 value 和 right child 是 NULL。左边的 child 不是之前追加的值为 3 的节点，但它有一些奇怪的值 - 它似乎指向随机内存位置。

（如果我运行进一步，Xcode 终止说：EXC_BAD_ACCESS...）

你能解释一下为什么会这样吗？

#include <stdio.h>


typedef struct Node Node;
struct Node
{
    int value;
    Node *left;
    Node *right;
};

void inOrder(Node *node)
{
    if(node!=NULL)
    {
        inOrder(node->left);
        printf("%d,", node->value);
        inOrder(node->right);
    }
}

void append(Node *root)
{
    Node n = {3,NULL};
    root->left->left = &n;
}

int main(int argc, const char * argv[])
{
    Node a = {10, NULL};
    Node b = {5, NULL};
    Node root = {8, &b, &a};

    // appends a node with value 3 to the node 5 (just a test)
    append(&root);

    inOrder(&root);
    puts("\n");
}

Answer 1

在 append() 函数内，

void append(Node *root)
{
    Node n = {3,NULL};
    root->left->left = &n;
}

您正在尝试从函数中 return 局部变量 n 的地址。在 append() 之外，n 的地址无效。使用它调用 undefined behaviour.

解决方法：定义n为Node类型的指针，使用malloc()动态分配内存，然后就可以return 指针。动态分配内存的生命周期在释放之前一直有效。

Answer 2

root->left->left = &n;

变量 n 是函数 append() 的局部变量，一旦退出函数 append() n 就不再有效。

所以在变量范围之外访问变量会导致未定义的行为

In-order 遍历偏离内存中的其他位置

In-order traversal deviating to other locations in memory

c

pointers

binary-search-tree