[数据结构与算法]二叉树中序遍历非递归算法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 pop\n",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;

?? ? ? ?

?? ? ? ?

? ? }

?? ?

?? ?

?? ?

}