二叉树创建，为什么没有运行结果的?

Question

#include <stdio.h>
#include <malloc.h>

#define MaxSize 100

typedef char ElemType;

typedef struct node {
    ElemType data;
    struct node* lchild;
    struct node* rchild;
} BTNode;

void CreateBTree(BTNode*& b, char* str) {
    b = NULL;
    BTNode* St[MaxSize];
    BTNode* p;
    int top = -1;
    int childType = 0;
    int j = 0;
    char ch;
    ch = str[j];
    while (ch!= '\0') {
        switch (ch) {
        case '(':
            top++;
            St[top] = p;
            childType = 1;
            break;
        case ')':
            top--;
            break;
        case ',':
            childType = 2;
            break;
        default:
            p = (BTNode*)malloc(sizeof(BTNode));
            p->data = ch;
            p->lchild = p->rchild = NULL;
            if (b == NULL) {
                b = p;
            } else {
                switch (childType) {
                case 1:
                    St[top]->lchild = p;
                    break;
                case 2:
                    St[top]->rchild = p;
                    break;
                }
            }
        }
        j++;
        ch = str[j];
    }
}

void DispBTree(BTNode* b) {
    if (b!= NULL) {
        printf("%c", b->data);
        if (b->lchild!= NULL || b->rchild!= NULL) {
            printf("(");
            DispBTree(b->lchild);
            if (b->rchild!= NULL) {
                printf(",");
            }
            DispBTree(b->rchild);
            printf(")");
        }
    }
}

int main() {
    BTNode* b;
    char str[] = "A(B(D,E(J,K(L,M(,N))))),C(F,G(,I)))";
    CreateBTree(b, str);
    printf("初始化二叉树：");
    DispBTree(b);
    return 0;
}

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

您的代码中存在一些问题，这可能是导致运行结果不正确的原因。以下是可能的问题及其解决方案：

1. 内存分配问题：在创建二叉树时，您的代码使用了一个栈结构来存储节点指针，并尝试将新创建的节点插入到正确的位置。然而，在插入新节点时，如果栈为空（即当前没有父节点），您将新节点分配给栈顶元素（应该是空的），这可能会导致未定义的行为。因此，在分配新节点之前，您需要确保栈顶元素不是空的。此外，您还需要确保在每次创建新节点后正确更新栈顶元素指针。以下是修正后的创建二叉树的代码片段：

void CreateBTree(BTNode*& b, char* str) {
    b = NULL;
    BTNode* St[MaxSize]; // 初始化栈为空
    int top = -1; // 栈顶指针初始化为-1表示空栈
    int j = 0;
    while (str[j] != '\0') { // 循环直到字符串结束
        switch (str[j]) {
            case '(': // 遇到左括号，入栈或创建节点
                if (top < MaxSize - 1) { // 确保栈未满（这是一个边界条件）
                    St[++top] = b; // 将当前节点（可能是根）放入栈顶元素的位置（右移top索引以预留新位置）
                } else { // 避免数组溢出错误处理（如果栈已满）
                    printf("Error: Stack is full.\n");
                    exit(EXIT_FAILURE); // 或其他错误处理机制
                }
                break; // 这里不需要创建节点，因为下一个字符可能是右括号或逗号，我们需要等待来确定节点的位置
            case ')': // 遇到右括号，出栈并检查是否有子节点需要连接（如果当前节点不是根节点）
                if (top >= 0) { // 确保栈不为空（这是一个边界条件）并从栈中取出最后一个元素以连接子节点
                    if (St[top]->lchild == NULL) { // 检查是否有左子节点要连接（确保左子树不为空）否则会导致无效的二叉树结构或未定义的内存访问错误）
                        St[top]->lchild = b; // 连接左子节点到当前节点的左子树位置（注意这里的顺序很重要）并更新当前节点指针为左子节点以便进一步处理子树结构（如果需要的话）然后更新栈顶指针以移除最后一个元素（出栈操作）最后检查是否有右子节点需要连接。这个循环过程在内部调用时会持续进行直到所有节点的子节点都被正确连接。这样就可以保证创建的二叉树结构是有效的。否则可能会导致未定义的行为或错误的结果。因此您需要确保正确地处理所有可能的边界条件和异常情况以确保程序的正确性和稳定性。如果您遇到任何其他问题或需要进一步帮助请随时向我询问我会尽力提供帮助。