C语言 - 为什么我的程序会出现段错误？

Question

我有些困惑于分段错误，因为我不明白为什么会出现这种情况。我正在尝试遍历一棵已经构建好的树，而且测试也通过了。但是，当我尝试运行下面的函数时，就会出现分段错误。请问有人能告诉我为什么会出现分段错误以及如何避免这种情况吗？谢谢。

void traverse(Node *root)
{
    Node *pointer;
    Node *pre;

    if(root == NULL)
        return;

    pointer = pre;

    while(pointer != NULL)
    {
        if(pointer->leftChild != NULL)
            pointer = pointer->rightChild;
        else
        {
            pre = pointer->leftChild;

            while(pre->rightChild != NULL && pre->rightChild != pointer)
                pre = pre->rightChild;

            if(pre->rightChild != NULL)
            {
                pre->rightChild = pointer;
                pointer = pointer->leftChild;
            }
            else
            {
                pre->rightChild = pointer;
                pointer = pointer->leftChild;
            }
        } 
    }
}

- user3713899

---

你从未初始化 pointer 或 pre，基本上完全忽略了你传入作为参数的 root 节点，因此你尝试在未定义/未初始化的结构体中取消引用指针。 - Marc B

还有在第13行，您正在检查左节点是否为NULL，然后访问右节点。 - martin

在 C 语言中，始终要正确地初始化任何变量，以便在代码读取它之前已经写入。 - alk

同时，调试器肯定可以帮助深入到代码崩溃的行。 - alk

谢谢大家的帮助。我将指针和pre初始化为null，但仍然出现了分段错误。 - user3713899

@user3713899 分段错误基本上是C语言中空指针异常的等价物。对NULL指针进行解引用是导致分段错误的经典原因。 - martin

Answer 1

指针最初包含垃圾值，因为您在代码中没有初始化它。

Node *pointer;
Node *pre;

由于它们包含垃圾值，它们可能不指向NULL，而它们指向的位置已被分配给其他资源，这些资源无法访问，在下一行代码中导致段错误。

if(pointer->leftChild != NULL)
        pointer = pointer->rightChild;

你需要初始化你的指针或者给它分配输入参数。

编辑

我在你的代码中还观察到另一个问题是在if-else条件语句中。在你的if条件中，你正在检查if(pointer->leftChild != NULL)，所以如果这个条件为false（即pointer->leftChild = NULL），你将会进入else块，在那里你进行了如下赋值；

pre = pointer->leftChild; // Here pre is always NULL

如果你继续使用它，它会抛出异常并导致你的代码崩溃。

- Sudipta Kumar Sahoo

---

谢谢。我已经将指针初始化为root和pre = NULL。但是，我仍然出现了故障。 - user3713899

你能贴出调用这个函数的代码吗？ - Sudipta Kumar Sahoo

Answer 2

你需要初始化Node *pre = NULL;和Node *pointer = root;。你没有初始化pre，但是却将pointer = pre;。

除此之外，你应该更改这个：

if ( pointer->rightChild!= NULL)
           // ^^^^^^^^^^ change leftChild to rightChild 
    pointer = pointer->rightChild;

如果树的节点没有指向其父节点的指针，则通常使用递归函数遍历整个树：

void traverse( Node *root )
{
    if ( root == NULL )
        return;

    traverse( root->leftChild );

    // do somethig with root

    traverse( root->rightChild );
}

注意递归函数的参数取代了栈的位置，这对于从叶节点返回到根节点是必要的。

- Rabbid76