数据结构 二叉树的非递归遍历

      #include <stdio.h>
      #include <stdlib.h>
      #define STACT_INIT_SIZE 100
      #define STACTINCREMENT 10
      #define OK 1
      #define ERROR 0
      #define OVERFLOW -2
      typedef char TElemType;
      typedef struct BiNode
      {
      	TElemType data;
     	struct BiNode *lchild,*rchild;
      }BiNode, *BiTree;
      typedef BiTree SElemType;
      typedef struct
      {
      	SElemType *base;
      	SElemType *top;
     	int stacksize;
      }SqStack;
      int InitStack(SqStack &S)
      {
      	S.base = (SElemType *)malloc(STACT_INIT_SIZE * sizeof(SElemType));
     	if (!S.base)
      	{
     		exit(OVERFLOW);
      	}
      	S.top = S.base ;
      	S.stacksize = STACT_INIT_SIZE;
     	return OK;
      }
      int Push(SqStack &S, SElemType e)
      {
     	if (S.top - S.base >= S.stacksize)
      	{
      		S.base = (SElemType*)realloc(S.base , (S.stacksize + STACTINCREMENT) * sizeof(SElemType));
     		if (!S.base)
      		{
     			exit(OVERFLOW);
      		}
      		S.top = S.base + S.stacksize ;
      		S.stacksize += STACTINCREMENT;
      	}
      	*S.top++ = e;
     	return OK;
      }
      int Pop(SqStack &S, SElemType &e)
      {
     	if (S.base == S.top)
      	{
     		return ERROR;
      	}
      	e = *--S.top;
     	return OK;
      }
      int GetTop(SqStack S,SElemType &e)
      {
     	if (S.base == S.top)
      	{
     		return ERROR;
      	}
      	e = *(S.top-1);
     	return OK;
      }
      int StackEmpty(SqStack S)
      {
     	if (S.top == S.base )
      	{
     		return 1;
      	}
     	return 0;
      }
      void Create_BiTree(BiTree &T)
      {
      	TElemType ch;
     	scanf("%c",&ch);
     	if (ch == '#')
      	{
      		T = NULL;
      	}
     	else
      	{
      		T = (BiTree)malloc(sizeof(BiNode));
     		if (!T)
      		{
     			exit(OVERFLOW);
      		}
      		T->data = ch;
      		Create_BiTree(T->lchild);
      		Create_BiTree(T->rchild);
      	}
      }
      void PreOrderTraverse1(BiTree T)
      {//先序遍历的递归调用1
      	SqStack S;
      	BiTree p = T;
      	InitStack(S);
      	Push(S,p);
     	while (!StackEmpty(S))
      	{
     		while (GetTop(S,p) && p)
      		{
     			printf("%c",p->data);
      			Push(S,p->lchild);
      		}
      		Pop(S,p);
     		if (!StackEmpty(S))
      		{
      			Pop(S,p);
      			Push(S,p->rchild);
      		}
      	}
      }
      void PreOrderTraverse2(BiTree T)
      {//先序遍历的递归调用2
      	SqStack S;
      	BiTree p = T;
      	InitStack(S);
     	while (p || !StackEmpty(S))
      	{
     		if (p)
      		{
     			printf("%c",p->data);
      			Push(S,p);
      			p = p->lchild;
      		}
     		else
      		{
      			Pop(S,p);
      			p = p->rchild;
      		}
      	}
      }
      void InOrderTraverse1(BiTree T)
      {//中序遍历的非递归调用1
      	SqStack S;
      	BiTree p = T;
      	InitStack(S);
      	Push(S,p);
     	while (!StackEmpty(S))
      	{
     		while (GetTop(S,p) && p)
      		{
      			Push(S,p->lchild);
      		}
      		Pop(S,p);
     		if (!StackEmpty(S))
      		{
      			Pop(S,p);
     			printf("%c",p->data);
      			Push(S,p->rchild);
      		}
      	}
      }
      void InOrderTraverse2(BiTree T)
      {//中序遍历的非递归调用2
      	SqStack S;
      	BiTree p = T;
      	InitStack(S);
     	while (p || !StackEmpty(S))
      	{
     		if (p)
      		{
      			Push(S,p);
      			p = p->lchild;
      		}
     		else
      		{
      			Pop(S,p);
     			printf("%c",p->data);
      			p = p->rchild;
      		}
      	}
      }
      void PostOrderTraverse1(BiTree T)
      {
      	BiTree p,p1;
      	SqStack S;
      	p = T;
      	p1 = NULL;
      	InitStack(S);
     	while (p || !StackEmpty(S))
      	{
     		if (p)
      		{
      			Push(S,p);
     			//visit,先序
      			p = p->lchild;
      		}
     		else
      		{
      			GetTop(S,p);
     			//visit,中序
     			if (p->rchild == p1)
      			{//右子树为空，或者为上一次弹出的子树，则弹出根节点
       Pop(S,p1);
       p = NULL;
      //visit,后序
      printf("%c",p1->data);
      			}
     			else
      			{
       p = p->rchild;
       p1 = NULL;
      			}
      		}
      	}
      }
      int main()
      {
      	BiTree T;
      	Create_BiTree(T);
      	PreOrderTraverse1(T);
     	printf("\n");
      	PreOrderTraverse2(T);
     	printf("\n");
      	InOrderTraverse1(T);
     	printf("\n");
      	InOrderTraverse2(T);
     	printf("\n");
      	PostOrderTraverse1(T);
     	printf("\n");
     	return 0;
      }
  
 

文章来源: blog.csdn.net，作者：悦来客栈的老板，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq523176585/article/details/17249245