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

朱雀 2022-09-19 01:44 211阅读 0赞

#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;
    }