二叉树非递归前序遍历自定义栈运行异常：调试及合并代码后恢复正常原因

问题场景 #

使用自定义栈实现二叉树非递归前序遍历：

• 分离栈的头文件stack.h和实现文件Stack.c编译的BT程序，运行时出错，但调试过程中执行正常。
• 将栈的代码直接复制到主程序中生成的BT2程序，运行完全正常。
  开发环境为CLion 2024.2 + MinGW。

核心原因：跨编译单元的宏定义不一致 #

问题根源是栈的实现文件Stack.c与主程序BT.c中，STACK_DATA_T的宏定义完全不匹配，导致栈节点的内存布局在两个编译单元中不一样，进而引发内存访问越界错误。

具体细节 #

• Stack.c编译时的栈节点结构
  Stack.c单独编译时，没有定义STACK_DATA_T，会使用stack.h中默认的#define STACK_DATA_T int。此时栈节点的结构为：

  struct StackNode {
      int data;          // 32位系统下占4字节
      struct StackNode *next; // 指针类型，占4/8字节
  };
  

• BT.c编译时的栈节点结构
  BT.c中先定义#define STACK_DATA_T TreeNode（TreeNode是struct TreeNode*指针类型），再引入stack.h。此时栈节点的结构为：

  struct StackNode {
      TreeNode data;     // 指针类型，占4/8字节
      struct StackNode *next; // 指针类型，占4/8字节
  };
  

• 内存不匹配引发的错误
  当BT.c调用pushStack时，Stack.c里的malloc(sizeof(Stack))分配的是int版本的栈节点内存，空间远小于指针版本所需大小。写入TreeNode类型的data时会直接越界，破坏栈的结构或其他内存区域。
  调试时，调试器会给程序添加额外的内存保护或调整内存布局，刚好规避了越界带来的崩溃，所以调试时表现正常。

• 合并代码后问题消失的原因
  BT2.c将栈代码和主程序放在同一个编译单元，STACK_DATA_T的宏定义对整个文件生效，栈节点的内存布局在编译时完全一致，不会出现类型不匹配的问题，因此运行正常。

修复建议 #

1. 改用void指针实现通用栈：这是C语言实现泛型数据结构的标准方式，避免宏定义带来的编译单元不一致问题。
2. 为特定类型单独实现栈：如果只需要存储TreeNode，直接把栈的data类型定义为TreeNode，去掉宏定义。
3. 统一编译单元的宏定义：如果坚持用宏，要确保Stack.c和BT.c使用相同的STACK_DATA_T定义（比如在Stack.c开头也定义#define STACK_DATA_T TreeNode），但这种方式复用性差，不推荐。

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