非递归中序遍历二叉树

╰半夏微凉° 2022-06-15 00:22 227阅读 0赞

/*非递归中序遍历二叉树*/
    #include<stdio.h>
    #define maxsize 100
    typedef char datatype;
    /*二叉链表类型定义*/
    typedef struct Binnode
    {
        datatype data;                   /*数据域*/
        struct BinNode* lchild,*rchild;  /*指向左、右孩子的指针*/
    }BinNode,*Bintree;
    /*顺序栈类型定义*/
    typedef struct
    {
        Bintree data[maxsize];            /*存储栈中数据元素*/
        int top;                          /*标志栈顶位置*/
    }SeqStk;
    /*初始化栈*/
    int InitStack(SeqStk *stk)
    {
        stk->top=0;
        return 1;
    }
    /*判栈空*/
    int EmptyStack(SeqStk *stk)
    {
        if(stk->top==0)                   /*若栈为空，则返回值1，否则返回0.*/
            return 1;
        else
            return 0;
    }
    /*入栈*/
    int Push(SeqStk *stk,Bintree x)
    {
       if(stk->top==maxsize-1)                      /*判断栈是否满*/
       {
           printf("栈满\n");
           return 0;
       }
       else
       {
           stk->top++;                              /*栈未满，top值加1.*/
           stk->data[stk->top]=x;                   /*元素x进栈*/
           return 1;
    
       }
    }
    /*出栈*/
    int Pop(SeqStk *stk)
    {
        if(EmptyStack(stk))                         /*判断是否下溢（栈空）*/
        {
            printf("下溢\n");
            return 0;
        }
        else                                        /*未下溢，栈顶元素出栈。*/
        {
            stk->top--;                             /*top值减1*/
            return 1;
        }
    }
    /*取栈顶数据元素，栈顶数据元素通过参数返回。*/
    Bintree GetTop(SeqStk *stk)
    {
        if(EmptyStack(stk))
            printf("栈空\n");                        /*栈空，返回NULLData.*/
        else
            return stk->data[stk->top];             /*返回栈顶数据元素*/
    }
    /*按先序创建二叉树*/
    Bintree CreateTree(Bintree T)
    {
        datatype ch;
        scanf("%c",&ch);
        if(ch=='#')
            return NULL;
        else
        {
            T=(Bintree)malloc(sizeof(BinNode));
            T->data=ch;
            T->lchild=CreateTree(T->lchild);/*创建左子树*/
            T->rchild=CreateTree(T->rchild);/*创建右子树*/
            return T;
        }
    }
    
    /*非递归中序遍历二叉树*/
    void preorder(Bintree T)
    {
        Bintree p;
        SeqStk s;
        InitStack(&s);
        p=T;
        while(p || !EmptyStack(&s))
        {
            if(p)
            {
    
                Push(&s,p);                 /*当前结点指针入栈*/
                p=p->lchild;                /*当前指针指向左孩子*/
            }
            else
            {
                p=GetTop(&s);               /*栈顶元素退栈*/
                Pop(&s);
                printf("%c ",p->data);      /*访问当前结点*/
                p=p->rchild;                /*当前指针指向右孩子*/
            }
        }
    }
    main()
    {
        Bintree t;
        printf("请按先序的方式输入二叉树的结点元素（注：#表示节点为空）:");
        t=CreateTree(t);
        printf("非递归中序遍历二叉树:");
        preorder(t);
    }