二叉树非递归中序遍历?

BEI_TIAN_XUAN
  • 7

我用vs2019实现C语言二叉树非递归中序遍历时,遍历时(InOrderTraverse(BiTree T))函数中打印没实现。

问题代码:

Status InOrderTraverse(BiTree T)  //非递归中序遍历
{
    BiTree P;
    SqStack S;
    InitStack(&S);
    P = T;
    while (P || !StackEmpty(S))
    {
        while (P)
        {
            Push(&S,P);
            P = P->lchild;
        }
        if (!StackEmpty(S))
        {
            Pop(&S, &P);
            printf("%c", P->data);
            P = P->rchild;
        }
    }
    return OK;
}

完整源码:

#include<stdio.h>
#include<stdlib.h>
#define MaxSize 100
#define OK 1
#define ERROR 0
typedef char ElemType;
typedef int Status;
typedef struct {
    ElemType* base;
    ElemType* top;
    int StackSize;
}SqStack; //顺序栈
Status InitStack(SqStack* S)  //初始化
{
    S->base = (ElemType*)malloc(sizeof(ElemType) * MaxSize);
    if (!S->base)
        exit(0);
    S->top = S->base;
    S->StackSize = MaxSize;
    return OK;
}
Status StackEmpty(SqStack S)  //判断是否为空栈
{
    if (S.base == S.top)
        return OK;
    else
        ERROR;
}
Status Push(SqStack* S, ElemType e)  //入栈
{
    if (!S->base)
        return ERROR;
    *(S->top) = e;
    S->top++;
    return OK;
}
Status Pop(SqStack* S, ElemType* e)  //出栈
{
    if (S->base == S->top)
        return ERROR;
    *e = *(S->top - 1);
    S->top--;
    return OK;
}
typedef struct BiNode {
    ElemType data;
    struct BiNode* lchild, * rchild;
}BiNode, * BiTree;
Status Create_BiTree(BiTree *T)  //初始化二叉树
{
    char ch;
    scanf("%c", &ch);
    if (ch == '#')
    {
        *T = NULL;
    }
    else
    {
        *T = (BiTree)malloc(sizeof(BiNode));
        (*T)->data = ch;
        Create_BiTree(&(*T)->lchild);
        Create_BiTree(&(*T)->rchild);
    }
    return OK;
}
Status InOrderTraverse(BiTree T)  //非递归中序遍历
{
    BiTree P;
    SqStack S;
    InitStack(&S);
    P = T;
    while (P || !StackEmpty(S))
    {
        while (P)
        {
            Push(&S,P);
            P = P->lchild;
        }
        if (!StackEmpty(S))
        {
            Pop(&S, &P);
            printf("%c", P->data);
            P = P->rchild;
        }
    }
    return OK;
}
int main()
{
    BiTree T;
    printf("请输入字符(#表示空指针):");
    Create_BiTree(&T);
    printf("非递归遍历:");
    InOrderTraverse(T);

    return 0;
}
评论
阅读 159
撰写回答

登录后参与交流、获取后续更新提醒

宣传栏