使用Stack实现后缀表达式构建二叉树时出现未知错误

云原生阿岚

2026-8-10

后缀表达式构建二叉树时栈操作崩溃问题

我尝试用指针实现二叉树，随后通过栈从后缀表达式创建新二叉树并打印。负责该功能的create函数每次执行到StTop或StPop时，程序就会停止运行。

create函数逻辑如下：

接收字符串后遍历每个字符c：
- 若c是字母，则创建一棵以c为根、子节点均为NULL的二叉树，将其压入名为niz的栈；
- 若c是运算符，则从栈中弹出最后一个和倒数第二个元素，创建一棵以c为根、最后弹出的元素为右子树、倒数第二个元素为左子树的新二叉树，再将新树压回栈。

以下是完整代码：

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

#define LAMBDA NULL
#define MAXLENGHT 10000

typedef char labeltype;

typedef struct celltag{
    labeltype label;
    struct celltag *leftchild;
    struct celltag *rightchild;
} celltype;

typedef celltype *node; //ovo ti je cvor
typedef celltype *BinaryTree;


void BiMakeNull(BinaryTree *Tp)
{
    *Tp=NULL;
}

int BiEmpty(BinaryTree T)
{
    if(T==NULL) return 0;
    return 1;
}

void BiCreate(labeltype l, BinaryTree TL, BinaryTree TR, BinaryTree *Tp)
{
    (*Tp)=(celltype*)malloc(sizeof(celltype));
    (*Tp)->label= l;
    (*Tp)->leftchild=TL;
    (*Tp)->leftchild=TR;
}

void BiLeftSubtree(BinaryTree T, BinaryTree *TLp)
{
    (*TLp)=T->leftchild;
}

void BiRightSubtree(BinaryTree T, BinaryTree *TRp)
{
    (*TRp)=T->rightchild;
}

node BiInsertLeftChild(labeltype l, node i, BinaryTree *Tp)
{
    if(i==NULL) exit(1);
    if(i->leftchild != NULL) exit(2);

    i->leftchild->label=l;
    i->leftchild->leftchild=NULL;
    i->leftchild->rightchild=NULL;

    return i->leftchild;
}

 node BiInsertRightChild(labeltype l, node i, BinaryTree *Tp)
 {
    if(i==NULL) exit(1);
    if(i->rightchild != NULL) exit(2);

    i->rightchild->label=l;
    i->rightchild->rightchild=NULL;
    i->rightchild->rightchild=NULL;

    return i->rightchild;
 }

 void BiDelete(node i, BinaryTree *Tp)
 {
     if(i==NULL) exit(3);
     if(i->leftchild!=NULL || i->rightchild!= NULL) exit(4);

     i=NULL;
 }

 node BiRoot(BinaryTree T)
 {
     if(T==NULL) return LAMBDA;
     return T;
 }

 node BiLeftChild(node i, BinaryTree T)
 {
     if(i==NULL) exit(5);
     if(i->leftchild==NULL) return LAMBDA;
     return i->leftchild;
 }

 node BiRightChild(node i, BinaryTree T)
 {
     if(i==NULL) exit(5);
     if(i->rightchild==NULL) return LAMBDA;
     return i->rightchild;
 }

 node nadiRoditelja(node i, node root)
 {
     if(root->leftchild==i || root->rightchild==i) return root;

     if(root->leftchild!=NULL) {nadiRoditelja(i, root->leftchild);}
     if(root->rightchild!=NULL) {nadiRoditelja(i, root->rightchild);}

 }

 node BiParent(node i, BinaryTree T)
 {
     if(i==NULL) exit(6);
     if(i==T) return LAMBDA;

     node parent;
     parent=nadiRoditelja(i, BiRoot(T));
     return parent;
 }

 labeltype BiLabel(node i, BinaryTree T)
 {
     if(i==NULL) exit(7);
     return i->label;
 }

void BiChangeLabel(labeltype l, node i, BinaryTree *Tp)
{
    if(i==NULL) exit(8);
    i->label=l;
}


//implementacija stoga pomocu polja 


typedef struct {
    int top;
    BinaryTree elementi[MAXLENGHT];
} Stack;


void StMakeNull(Stack *St)
{
    St->top=MAXLENGHT;
}

int StEmpty(Stack S)
{
    if(S.top>=MAXLENGHT) return 1;
    return 0;
}

void StPush(BinaryTree x, Stack *Sp)
{
    if(Sp->top==0) exit(101);
    else{
        Sp->top--;
        Sp->elementi[Sp->top]=x;
    }
}

void StPop(Stack *Sp)
{
    if(StEmpty(*Sp)){exit(212);}
    else{
            Sp->top++;
    }

}

BinaryTree StTop(Stack S)
{
    if(StEmpty(S)) {exit(202);}
    else{
        return (S.elementi[S.top]);
    }
}




void Postorder(node i, BinaryTree T)
{
    if(i)
    {
        Postorder(BiLeftChild(i,T), T);
        Postorder(BiRightChild(i, T), T);
        printf(" %c", BiLabel(i, T));
    }
}

void printajdrvo(BinaryTree T, node root)
{
    printf(" %c ", BiLabel(root, T));
    if(BiLabel(BiLeftChild(root, T), T)== 0) {printf(" NULL ");return;}
    else{printf(" %c ", BiLabel(BiLeftChild(root, T), T) );}

    if(BiLabel(BiRightChild(root, T), T)== 0) {printf(" NULL\n"); return;}
    else{printf(" %c\n", BiLabel(BiRightChild(root, T), T) );}

    printajdrvo(T, BiLeftChild(root, T));
    printajdrvo(T, BiRightChild(root, T));

}

BinaryTree create(char string[100])
{
    Stack niz;
    StMakeNull(&niz);
    BinaryTree pom, poml, pomr;
    BiMakeNull(&pom);
    BiMakeNull(&poml);
    BiMakeNull(&pomr);
    BinaryTree newroot;

    int i=0;
    while(string[i]!='\0')
    {
        BiCreate(string[i], poml, pomr, &pom);



        if(string[i]>='A' && string[i]<='z')
        {
            StPush(pom, &niz);
        }
        else{

            BinaryTree l,d;
            BiMakeNull(&l);
            BiMakeNull(&d);
            BiMakeNull(&newroot);
            newroot=pom;
            
            d=StTop(niz);

            StPop(&niz);

            l=StTop(niz);

            StPop(&niz);

            BiCreate(string[i],l,d,&newroot);
            StPush(newroot, &niz);

        }
        BiMakeNull(&pom);
      i++;
    }
    return newroot;
}

int main()
{

    char string[100];
    printf("Enter postfix: \n");
    scanf(" %s", string);
    BinaryTree T;
    BiMakeNull(&T);
    T = create(string);
    printajdrvo(T, BiRoot(T));
    Postorder(BiRoot(T), T);
    return 0;
}

问题排查与修复建议

1. `BiCreate`函数的致命错误

函数中错误地将右子树赋值给了左孩子，导致所有节点的左子树被覆盖：

// 错误代码
(*Tp)->leftchild=TL;
(*Tp)->leftchild=TR;

// 修复后
(*Tp)->leftchild=TL;
(*Tp)->rightchild=TR;

这个错误会导致后续树结构完全错误，访问左子树时出现异常。

2. `create`函数的逻辑冗余与错误

循环开头的BiCreate(string[i], poml, pomr, &pom);完全多余，且poml/pomr都是NULL，处理运算符时还会重新创建节点，造成内存泄漏。应只在处理字母时创建节点。
处理运算符时newroot=pom;是无效操作，后续BiCreate会覆盖newroot，直接删除即可。

修复后的create函数：

BinaryTree create(char string[100])
{
    Stack niz;
    StMakeNull(&niz);
    BinaryTree newroot = NULL;

    int i=0;
    while(string[i]!='\0')
    {
        if(string[i]>='A' && string[i]<='z')
        {
            // 仅在处理字母时创建节点，子节点为NULL
            BinaryTree pom;
            BiCreate(string[i], NULL, NULL, &pom);
            StPush(pom, &niz);
        }
        else{
            // 检查栈中是否有至少两个元素，避免非法访问
            if(StEmpty(niz)) exit(212);
            BinaryTree d = StTop(niz);
            StPop(&niz);
            
            if(StEmpty(niz)) exit(212);
            BinaryTree l = StTop(niz);
            StPop(&niz);

            BiCreate(string[i], l, d, &newroot);
            StPush(newroot, &niz);
        }
      i++;
    }
    // 最后栈顶就是整个树的根节点
    return StTop(niz);
}

3. `printajdrvo`函数的空指针访问错误

当节点的左/右子树为NULL时，调用BiLabel(BiLeftChild(root, T), T)会触发exit(7)（因为BiLabel不允许空指针）。修复方法是先判断子节点是否存在：

void printajdrvo(BinaryTree T, node root)
{
    if(root == NULL) return;
    
    printf(" %c ", BiLabel(root, T));
    
    node left = BiLeftChild(root, T);
    if(left == NULL) {
        printf(" NULL ");
    } else {
        printf(" %c ", BiLabel(left, T));
    }
    
    node right = BiRightChild(root, T);
    if(right == NULL) {
        printf(" NULL\n");
    } else {
        printf(" %c\n", BiLabel(right, T));
    }

    printajdrvo(T, left);
    printajdrvo(T, right);
}

4. 其他潜在问题

BiInsertLeftChild和BiInsertRightChild函数直接访问i->leftchild->label，但i->leftchild未分配内存，会导致崩溃。如果后续需要使用这两个函数，需先为子节点分配内存：

node BiInsertLeftChild(labeltype l, node i, BinaryTree *Tp)
{
    if(i==NULL) exit(1);
    if(i->leftchild != NULL) exit(2);

    i->leftchild = (celltype*)malloc(sizeof(celltype));
    i->leftchild->label=l;
    i->leftchild->leftchild=NULL;
    i->leftchild->rightchild=NULL;

    return i->leftchild;
}

输入校验：建议在main函数中检查后缀表达式的合法性，避免因输入错误导致栈空操作。

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

使用Stack实现后缀表达式构建二叉树时出现未知错误

问题排查与修复建议 #

1. BiCreate函数的致命错误 #

2. create函数的逻辑冗余与错误 #

3. printajdrvo函数的空指针访问错误 #

4. 其他潜在问题 #

问题排查与修复建议

1. `BiCreate`函数的致命错误

2. `create`函数的逻辑冗余与错误

3. `printajdrvo`函数的空指针访问错误

4. 其他潜在问题