二叉树中序遍历非递归算法C语言实现

二叉树中序遍历非递归算法C语言实现

//

//  Inordertraverse.c

//  二叉树链式存储

//

//  Created by 丘** on 2021/7/28.

//

#include "Inordertraverse.h"

#include <stdbool.h>

#include<stdlib.h>

typedef   struct StackNode

{

    int data;

    struct StackNode* next;

    

}StackNode;

typedef struct BiTNode

{

    int data;

    struct BiTNode* lchild,* rchild;

    

    

}BiTnode,* BiTree;

void Push(StackNode*s,BiTree p)//入栈

{

   

    s->data=p->data;

    s=s->next;

}

void Pop(StackNode*s,BiTree q)//弹栈

{

   q->data=s->data;

    printf("%d will be popn",q->data);

    StackNode* p=s;

    s=s->next;

    

    free(p);

    

}

void InitStack(StackNode* s)

{

    s=NULL;

    

    

    

}

bool StackEmpty(StackNode* s)

{

    if(s==NULL)

    {

        

        return  true;

        

    }

    return false;

    

}

void InorderTraverse(BiTree T)

{

    StackNode s;

    InitStack(&s);

    BiTree p=T;

    BiTree q=(BiTree)malloc(sizeof(BiTnode));

    while(p!=NULL||!StackEmpty(&s))

    {

        if(p!=NULL)

        {

            Push(&s, p);

            p=p->lchild;

        }

        else

            Pop(&s,q);

        int e=q->data;

        printf("%d has been cout",e);

        p=q->rchild;

        

        

    }

    

    

    

}