利用栈实现的二叉树遍历问题

#include<stdio.h>
#include<string.h>
#include<malloc.h>
nclude<stdlib.h>
typedef  char ElemType;
typedef struct BiTNode {
    ElemType data;
    struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;
#define Stack_Size 100
#define TRUE 1
#define FALSE 0
typedef BiTree StackElementType;
typedef struct {
    StackElementType elem[Stack_Size];
    int top;
}SeqStack;
//初始化顺序栈
void InitStack(SeqStack* S) {
    //S = (SeqStack*)malloc(sizeof(SeqStack));
    S->top = -1;
}
//判满
int Judge_full(SeqStack S) {
    if (S.top == (Stack_Size - 1)) {
        return 1;
    }
    else {
        return 0;
    }
}
//判空
int Judge_empty(SeqStack S) {
    if (S.top == -1) {
        return 1;
    }
    else {
        return 0;
    }
}
//进栈
void Push(SeqStack* S, StackElementType x) {
    if (S->top == Stack_Size - 1){}
    else {
        S->top++;
        S->elem[S->top] = x;
    }
}
//出栈
void Pop(SeqStack* S, StackElementType* x) {
    if (S->top == -1) {}
    else {
        *x = S->elem[S->top];
        S->top--;
    }
}
BiTree create() {
    BiTree t;
    ElemType ch;
    scanf_s("%c", &ch);
    if (ch == '#') t = NULL;
    else {
        t = (BiTree)malloc(sizeof(BiTNode));
        t->data = ch;
        t->lchild = create();
        t->rchild = create();
    }
    return t;
}
void Create(BiTree* bt) {
    ElemType ch;
    ch = getchar();
    if (ch == '#') *bt = NULL;
    else {
        *bt = (BiTree)malloc(sizeof(BiTNode));
        (*bt)->data = ch;
        Create(&((*bt)->lchild));
        Create(&((*bt)->rchild));
    }
    printf("over");
}
//先序遍历
void PreOrder(BiTree t) {
    if (t) {
        printf("%c", t->data);
        PreOrder(t->lchild);
        PreOrder(t->rchild);
    }
}
//中序遍历
void InOrder(BiTree t) {
    if (t) {
        InOrder(t->lchild);
        printf("%c", t->data);
        InOrder(t->rchild);
    }
}
//后序遍历
void PostOrder(BiTree t) {
    if (t) {
        PostOrder(t->lchild);
        PostOrder(t->rchild);
        printf("%c", t->data);
    }
}
//二叉树深度
int TreeDepth(BiTree t) {
    int y,y1, y2;
    if (t) {
        y1 = TreeDepth(t->lchild);
        y2 = TreeDepth(t->rchild);
        y = (y1 > y2 ? y1 : y2) + 1;
    }
    else {
        y = 0;
    }
    return y;
}
//二叉树结点数
int Count(BiTree t) {
    int y;
    if (t) {
        y = 1 + Count(t->lchild) + Count(t->rchild);
    }
    else {
        y = 0;
    }
    return y;
}
//二叉树叶子数
int Leaf(BiTree t) {
    int y;
    if (t) {
        if (!t->lchild && !t->rchild) y = 1;
        else y = Leaf(t->lchild) + Leaf(t->rchild);
    }
    else {
        y = 0;
    }
    return y;
}
//先序遍历(非递归)
void PreOrder_1(BiTree t) {
    SeqStack s;
    BiTree p;
    InitStack(&s);
    while (t || !StackElementType(&s)) {
        if (t) {
            printf("%c", t->data);
            Push(&s, t);
            t = t->lchild;
        }
        else {
            Pop(&s, &p);
            t = p->rchild;
        }
    }
}
//中序遍历(非递归)
void InOrder_1(BiTree t) {
    SeqStack s;
    BiTree p;
    InitStack(&s);
    while (t || !StackElementType(&s)) {
        if (t) {
            Push(&s, t);
            t = t->lchild;
        }
        else {
            Pop(&s, &p);
            printf("%c", p->data);
            t = p->rchild;
        }
    }
}
int main() {
    BiTree t;
    printf("Input the tree node:\n");
    t = create();
    //Create(&t);
    printf("\nPreOrder"); PreOrder(t);
    printf("\nInOrder"); InOrder(t);
    printf("\nPostOrder"); PostOrder(t);
    printf("\nthe Tree's deepth are %d", TreeDepth(t));
    printf("\nthe Tree's count are %d", Count(t));
    printf("\nthe Tree's leaf are %d", Leaf(t));
    printf("\nPreOrder_1"); PreOrder_1(t);
    printf("\nInOrder_1"); InOrder_1(t);
    return 0;
}

通过递归实现的二叉树遍历没问题，但在用了和栈有关的二叉树遍历就不顺畅，输出结果就和图片中一样不正常。

基于Monster 组和GPT的调写：

非递归遍历算法中，判断栈是否为空的函数调用写错了，用了StackElementType(&s)，这实际上不是一个有效的函数。我已经替换为正确的函数Judge_empty(s)。

#include<stdio.h>
#include<string.h>
#include<malloc.h>
#include<stdlib.h>
typedef  char ElemType;
typedef struct BiTNode {
    ElemType data;
    struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;
#define Stack_Size 100
#define TRUE 1
#define FALSE 0
typedef BiTree StackElementType;
typedef struct {
    StackElementType elem[Stack_Size];
    int top;
}SeqStack;
//初始化顺序栈
void InitStack(SeqStack* S) {
    S->top = -1;
}
//判满
int Judge_full(SeqStack S) {
    if (S.top == (Stack_Size - 1)) {
        return 1;
    }
    else {
        return 0;
    }
}
//判空
int Judge_empty(SeqStack S) {
    if (S.top == -1) {
        return 1;
    }
    else {
        return 0;
    }
}
//进栈
void Push(SeqStack* S, StackElementType x) {
    if (S->top == Stack_Size - 1){}
    else {
        S->top++;
        S->elem[S->top] = x;
    }
}
//出栈
void Pop(SeqStack* S, StackElementType* x) {
    if (S->top == -1) {}
    else {
        *x = S->elem[S->top];
        S->top--;
    }
}
BiTree create() {
    BiTree t;
    ElemType ch;
    scanf_s("%c", &ch);
    if (ch == '#') t = NULL;
    else {
        t = (BiTree)malloc(sizeof(BiTNode));
        t->data = ch;
        t->lchild = create();
        t->rchild = create();
    }
    return t;
}
void Create(BiTree* bt) {
    ElemType ch;
    ch = getchar();
    if (ch == '#') *bt = NULL;
    else {
        *bt = (BiTree)malloc(sizeof(BiTNode));
        (*bt)->data = ch;
        Create(&((*bt)->lchild));
        Create(&((*bt)->rchild));
    }
}
//先序遍历
void PreOrder(BiTree t) {
    if (t) {
        printf("%c", t->data);
        PreOrder(t->lchild);
        PreOrder(t->rchild);
    }
}
//中序遍历
void InOrder(BiTree t) {
    if (t) {
        InOrder(t->lchild);
        printf("%c", t->data);
        InOrder(t->rchild);
    }
}
//后序遍历
void PostOrder(BiTree t) {
    if (t) {
        PostOrder(t->lchild);
        PostOrder(t->rchild);
        printf("%c", t->data);
    }
}
//二叉树深度
int TreeDepth(BiTree t) {
    int y,y1, y2;
    if (t) {
        y1 = TreeDepth(t->lchild);
        y2 = TreeDepth(t->rchild);
        y = (y1 > y2 ? y1 : y2) + 1;
    }
    else {
        y = 0;
    }
    return y;
}
//二叉树结点数
int Count(BiTree t) {
    int y;
    if (t) {
        y= 1 + Count(t->lchild) + Count(t->rchild);
    }
    else {
        y = 0;
    }
    return y;
}
//二叉树叶子数
int Leaf(BiTree t) {
    int y;
    if (t) {
        if (!t->lchild && !t->rchild) y = 1;
        else y = Leaf(t->lchild) + Leaf(t->rchild);
    }
    else {
        y = 0;
    }
    return y;
}
//先序遍历(非递归)
void PreOrder_1(BiTree t) {
    SeqStack s;
    BiTree p;
    InitStack(&s);
    while (t || !Judge_empty(s)) {  // 修改为正确的栈空判断函数
        if (t) {
            printf("%c", t->data);
            Push(&s, t);
            t = t->lchild;
        }
        else {
            Pop(&s, &p);
            t = p->rchild;
        }
    }
}
//中序遍历(非递归)
void InOrder_1(BiTree t) {
    SeqStack s;
    BiTree p;
    InitStack(&s);
    while (t || !Judge_empty(s)) {  // 修改为正确的栈空判断函数
        if (t) {
            Push(&s, t);
            t = t->lchild;
        }
        else {
            Pop(&s, &p);
            printf("%c", p->data);
            t = p->rchild;
        }
    }
}
int main() {
    BiTree t;
    printf("Input the tree node:\n");
    t = create();
    printf("\nPreOrder"); PreOrder(t);
    printf("\nInOrder"); InOrder(t);
    printf("\nPostOrder"); PostOrder(t);
    printf("\nthe Tree's deepth are %d", TreeDepth(t));
    printf("\nthe Tree's count are %d", Count(t));
    printf("\nthe Tree's leaf are %d", Leaf(t));
    printf("\nPreOrder_1"); PreOrder_1(t);
    printf("\nInOrder_1"); InOrder_1(t);
    return 0;
}