二叉搜索树迭代前序遍历栈存指针原理及段错误疑问

一、BST迭代前序遍历中栈的指针定位原理 #

咱们先拆解你第一个疑惑：为什么用malloc(size * sizeof(node*))分配内存后，stack[++top] = root能正确定位到下一个结构体指针的位置。

这其实是C语言指针数组的特性在起作用：

• 你声明的node **stack是一个指向node*类型的指针，本质上可以当作存储node*的数组来使用。
• malloc(size * sizeof(node*))已经为你分配了能容纳size个node*指针的总字节空间——sizeof(node*)是单个结构体指针占用的字节数（64位系统通常为8字节），乘以size就是所有指针需要的总内存。
• 当你用stack[index]访问数组元素时，C语言会自动计算偏移地址：stack[index]等价于*(stack + index)，这里的index是按照node*的大小来偏移的。比如stack[0]是起始地址，stack[1]就是起始地址加上sizeof(node*)字节的位置，刚好是下一个指针的存储位置。

结合你的BST代码来看：
全局变量size会在每次插入节点时递增，所以iterative_preorder里malloc的空间刚好能容纳所有节点的指针，不会出现越界访问，因此stack[++top] = root这类操作能精准定位到正确的指针存储位置。

二、int指针栈触发段错误的原因 #

再看你写的int指针栈小程序，代码如下：

#include <stdio.h>
#include <stdlib.h>
void main() {
    int** stack = (int**)malloc(2 * sizeof(int*));
    printf("%d", *stack[0]);
}

触发段错误的核心原因是野指针解引用：

• malloc(2 * sizeof(int*))只是分配了能存2个int*指针的空间，但这些指针本身是未初始化的，它们指向的是随机的内存地址（也就是野指针）。
• 你直接执行*stack[0]，试图解引用这个野指针，访问它指向的内存——而这块内存要么不属于你的程序，要么是未分配的，操作系统就会触发段错误来阻止非法内存访问。

对比你的BST代码：
BST栈里存储的root、cur->right、cur->left都是已经通过malloc分配过的node结构体的有效地址，这些指针指向的内存是合法且属于你的程序的，所以解引用它们（比如cur->data）是安全的，不会触发段错误。

内容的提问来源于stack exchange，提问作者Rajesh Gupta