非递归实现二叉树的先序遍历时运行出错调试通过

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);
}

Answer 1

该回答引用自GPT-deepseek, 由博主 GISer Liu 编写：

问题分析

用户在使用非递归方法实现二叉树的先序遍历时遇到了运行时错误。具体表现为：

1. 直接运行时报错。
2. 调试时可以正常运行。
3. 将.h和.c文件的内容复制到主程序中后，问题消失。

问题定位

1. 头文件和源文件的链接问题：可能是由于头文件和源文件的链接不正确导致的。在不同的文件中定义和使用相同的结构体或函数时，可能会出现链接错误。
2. 栈的初始化和使用问题：栈的初始化和使用可能存在问题，导致运行时错误。

解决方案

1. 检查头文件和源文件的链接

确保头文件和源文件的链接正确，避免重复定义和链接错误。可以通过以下步骤进行检查：

• 确保头文件中使用了条件编译指令，避免重复包含。
• 确保源文件中包含了相应的头文件。

2. 检查栈的初始化和使用

确保栈的初始化和使用正确，避免运行时错误。可以通过以下步骤进行检查：

• 确保栈的初始化函数正确初始化了栈。
• 确保栈的操作函数（如pushStack和popStack）正确处理了栈的节点。

修改后的代码

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 NULL; // 修改返回值为NULL
    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);
        if (root == NULL) break; // 添加NULL检查
        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);
}

解释

1. 头文件和源文件的链接：确保头文件中使用了条件编译指令，避免重复包含。源文件中包含了相应的头文件。
2. 栈的初始化和使用：在popStack函数中，修改返回值为NULL，并在preOrder函数中添加对NULL的检查，避免访问空指针。

通过以上修改，可以解决非递归实现二叉树先序遍历时的运行时错误。

如果该回答解决了您的问题，请采纳！如果没有，请私信联系或评论您的疑惑