二叉树的前序遍历非递归实现有错误，但是调试没有问题

Question

当使用非递归方法实现二叉树的前序遍历时，我编写了自己的堆栈。运行时发生错误。

当我尝试调试并找到问题时，它又正常运行了。这是为什么？

当我将.h和.c文件中的内容复制到主程序中时，问题也消失了。这是为什么？

开发环境为CLion 2024.2+MinGw CMakeLists.txt

cmake_minimum_required(VERSION 3.29)
project(CLionProjectC11 C)

set(CMAKE_C_STANDARD 11)

add_executable(BT BT.c Stack.c)
add_executable(BT2 BT2.c)

stack.h

#ifndef STACK_H
#define STACK_H

#include <stdbool.h>

#ifndef STACK_DATA_T
#define STACK_DATA_T int
#endif  // STACK_DATA_T

typedef struct StackNode {
    STACK_DATA_T data;
    struct StackNode *next;
} Stack, *StackNode;

bool initStack(StackNode stack);

bool isEmptyStack(StackNode stack);

bool pushStack(StackNode stack, STACK_DATA_T data);

STACK_DATA_T popStack(StackNode stack);

#endif //STACK_H

stack.c

#include <stdio.h>
#include <stdlib.h>
#include "Stack.h"

bool initStack(StackNode stack) {
    stack->data = 0;
    stack->next = NULL;
    return true;
}

bool isEmptyStack(StackNode stack) {
    return stack->next == NULL;
}

bool pushStack(StackNode stack, STACK_DATA_T data) {
    StackNode node = malloc(sizeof(Stack));
    if (node == NULL) return false;
    node->data = data;
    node->next = stack->next;
    stack->next = node;
    return true;
}

STACK_DATA_T popStack(StackNode stack) {
    if (isEmptyStack(stack)) return false;
    StackNode node = stack->next;
    stack->next = stack->next->next;
    STACK_DATA_T data = node->data;
    free(node);
    return data;
}

BT.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct TreeNode {
    char element;
    struct TreeNode *left;
    struct TreeNode *right;
} Tree, *TreeNode;

#define STACK_DATA_T TreeNode
#include "Stack.h"

void preOrder(TreeNode root) {
    Stack head;
    initStack(&head);
    while (root || !isEmptyStack(&head)) {
        while (root) {
            printf("%c ", root->element);
            pushStack(&head, root);
            root = root->left;
        }
        root = popStack(&head);
        root = root->right;
    }
}

int main() {
    TreeNode a = malloc(sizeof(Tree));
    TreeNode b = malloc(sizeof(Tree));
    TreeNode c = malloc(sizeof(Tree));
    a->element = 'A';
    b->element = 'B';
    c->element = 'C';
    a->left = b;
    a->right = c;
    b->left = b->right = c->left = c->right = NULL;

    preOrder(a);
    printf("\n");

    free(a);
    free(b);
    free(c);
}

BT2.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct TreeNode {
    char element;
    struct TreeNode *left;
    struct TreeNode *right;
} Tree, *TreeNode;

#define STACK_DATA_T TreeNode

typedef struct StackNode {
    STACK_DATA_T data;
    struct StackNode *next;
} Stack, *StackNode;

bool initStack(StackNode stack) {
    stack->data = 0;
    stack->next = NULL;
    return true;
}

bool isEmptyStack(StackNode stack) {
    return stack->next == NULL;
}

bool pushStack(StackNode stack, STACK_DATA_T data) {
    StackNode node = malloc(sizeof(Stack));
    if (node == NULL) return false;
    node->data = data;
    node->next = stack->next;
    stack->next = node;
    return true;
}

STACK_DATA_T popStack(StackNode stack) {
    if (isEmptyStack(stack)) return false;
    StackNode node = stack->next;
    stack->next = stack->next->next;
    STACK_DATA_T data = node->data;
    free(node);
    return data;
}

void preOrder(TreeNode root) {
    Stack head;
    initStack(&head);
    while (root || !isEmptyStack(&head)) {
        while (root) {
            printf("%c ", root->element);
            pushStack(&head, root);
            root = root->left;
        }
        root = popStack(&head);
        root = root->right;
    }
}

int main() {
    TreeNode a = malloc(sizeof(Tree));
    TreeNode b = malloc(sizeof(Tree));
    TreeNode c = malloc(sizeof(Tree));
    a->element = 'A';
    b->element = 'B';
    c->element = 'C';
    a->left = b;
    a->right = c;
    b->left = b->right = c->left = c->right = NULL;

    preOrder(a);
    printf("\n");

    free(a);
    free(b);
    free(c);
}

我试图通过调试发现问题，但是在调试过程中运行正确。我也复制了。手。将.c文件复制到主程序中，运行正常。这是为什么？

Answer 1

stack.h

包含：

#ifndef STACK_DATA_T
#define STACK_DATA_T int
#endif  // STACK_DATA_T

BT.c

在包含

STACK_DATA_T

之前将

TreeNode

定义为

Stack.h

，所以。

stack.c

在包含

STACK_DATA_T

之前不定义

Stack.h.

。因此，这两个文件使用

STACK_DATA_T

获得不同的数据结构和函数定义。

int

使用的

stack.h

不足以表示指针，因此

pushStack

和

popStack

例程无法保留压入堆栈和从堆栈弹出的地址的所有位。

BT2.c

定义了

STACK_DATA_T

并且不包含

#ifndef

代码，因此它始终使用

TreeNode

代表

STACK_DATA_T

。