二叉树非递归遍历 C语言实现

二叉树非递归遍历 算法文档内有简要概括

#include <stdio.h>
#include <stdlib.h>

typedef struct BitNode
{
char data;
BitNode *lchild,*rchild;
int ltag,rtag;
}BitNode,*BitTree,ElemType; //树的结构体定义

typedef struct node
{
ElemType stack;
struct node *next;
}linkstack; //栈的结构体定义

int initstack(linkstack **s)//初始化一个带头结点的空栈
{
*s=(linkstack *)malloc(sizeof(linkstack));
if(*s==NULL)exit(-1);
(*s)->next=NULL;
return 1;
}

int push(linkstack *s,ElemType *x)//入栈操作，将x的数据元素插入栈s中，使x成为新的栈顶元素
{
linkstack *p,*q;
q=s;
p=(linkstack *)malloc(sizeof(linkstack));
if(!p)exit(-1);
p->stack=*x;
p->next=NULL;
while(q->next)
q=q->next;
q->next=p;
return 1;
}
/////////////////////////////////////////////////
//因为非递归遍历算法 调用的栈不需要 全部出栈
//进栈的链表实现的 真正算法为
// q->stack=*x;
// q->next=S->next;
// S->next=q;
////////////////////////////////////////////////

int pop(linkstack *s,ElemType *e)//出栈操作,先将栈s的栈顶结点的值送到e所指向的内存单元，然后删除栈顶结点
{
linkstack *p,*q;
p=s;
if(s->next==NULL)return 0;
while(p->next)
{
q=p;
p=p->next;
}
q->next=NULL;
*e=p->stack;
free(p);
return 1;
}

int emptystack(linkstack *s)//判断栈是否为空
{
if(s->next==NULL)return 1;
else return 0;
}

int gettop(linkstack *s,ElemType *e)
{
linkstack *p,*q;
p=s;
if(s->next==NULL)return 0;
while(p->next)
{
q=p;
p=p->next;
}
*e=p->stack;
return 1;
}

BitTree CreateBiTree()
{
BitTree bt;
char x;
x=getchar();
if(x=='#') bt=NULL;
else
{
bt=(BitTree)malloc(sizeof(BitNode));
bt->data=x;
bt->lchild=NULL;
bt->rchild=NULL;
bt->lchild=CreateBiTree();
bt->rchild=CreateBiTree();
}
return bt;
}
//////////////////////////////////////////////////////////////////////////
//Comment:非递归先序遍历 二叉树
//Algorithm:沿着左指针访问沿途经过的根节点，同时将右指针进栈，以便在递归访
//问左子树完成后能得到右子树的根节点的地址，如此重复进行，直到栈空。
//////////////////////////////////////////////////////////////////////////
void PreOrderBiTree(BitTree T)
{
linkstack *S;
BitTree p,q;
q=(BitTree)malloc(sizeof(BitNode));
initstack(&S);
p=T;
while(p||!emptystack(S))
{
while (p)
{
printf("%c ",p->data);
push(S,p);
p=p->lchild;
}
if(pop(S,q))
p=q->rchild;
}
}
//////////////////////////////////////////////////////////////////////////
//Comment:非递归中序遍历 二叉树
//Algorithm:先沿着左指针走到二叉树中最左下的结点，即左指针为空的结点，将沿
//途经过的根节点，指针进栈。当左指针为空时，从栈中取出根节点访问，然后再跳
//到右子树上。
//////////////////////////////////////////////////////////////////////////
void InOr

二叉树非递归遍历 算法文档内有简要概括

derBiTree(BitTree T)
{
linkstack *S;
BitTree p,q;
q=(BitTree)malloc(sizeof(BitNode));
initstack(&S);
p=T;
while (p||!emptystack(S))
{
while (p)
{
push(S,p);
p=p->lchild;
}
pop(S,q);
printf("%c",q->data);
p=q->rchild;
}
}
//////////////////////////////////////////////////////////////////////////
//Comment:非递归后续遍历 二叉树
//Algorithm:先沿着左指针走到二叉树中最左下的结点，将沿途经过的根节点指针进
//栈，若右子树为空，则弹栈并访问根节点，否则，跳到右子树上。
//////////////////////////////////////////////////////////////////////////
void PostOrderBiTree(BitTree T)
{
linkstack *S;
BitTree p,q;
char flag;//标记访问过的节点
initstack(&S);
q=(BitTree)malloc(sizeof(BitNode));
p=T;
while (p||!emptystack(S))
{
if(p!=q)
{
while(p) //当子树p不为空时 进栈
{
push(S,p);
if(p->lchild)p=p->lchild; //不为空 后移指向左子树
else p=p->rchild; //为空指向 右子树
}
}
if (emptystack(S))break;
gettop(S,q);
if(q->rchild==p) //判断是 遍历过 右子树 如遍历过右子树 说明该遍历根子树
{
p=(BitTree)malloc(sizeof(BitNode));
pop(S,p);
printf("%c",p->data);
p=q;
flag = p->data; //记录 遍历过的子树
}
else
{
p=q->rchild;
if (flag == p->data)//如果根节点的右子树刚刚访问完成，那么打印根节点。
{
p=(BitTree)malloc(sizeof(BitNode));
pop(S,p);
printf("%c",p->data);
p=q;
flag = p->data;
}
}


}

}

本文来源：https://www.bwwdw.com/article/qvcj.html