数据结构之树和二叉树---二叉树的遍历

Myth丶恋晨 2022-08-03 12:55 120阅读 0赞

问题：分别用递归和非递归方式实现二叉树的先序遍历，中序遍历，后序遍历及层序遍历

二叉树的基本操作见[数据结构之树和二叉树---二叉树的基本操作][---]

//递归方式实现先序遍历

void PreOrderTraverse(BiTree bt)
    {
    	if(bt)
    	{
    		printf("%c ", bt->data);
    		PreOrderTraverse(bt->lchild);
    		PreOrderTraverse(bt->rchild);
    	}else
    		printf("0 ");
    }

//递归方式实现中序遍历

void InOrderTraverse(BiTree bt)
    {
    	if(bt)
    	{
    		InOrderTraverse(bt->lchild);
    		printf("%c ", bt->data);
    		InOrderTraverse(bt->rchild);
    	}else
    		printf("0 ");
    }

//递归方式实现后序遍历

void PostOrderTraverse(BiTree bt)
    {
    	if(bt)
    	{
    		PostOrderTraverse(bt->lchild);
    		PostOrderTraverse(bt->rchild);
    		printf("%c ", bt->data);
    	}else
    		printf("0 ");
    }

//递归方式实现层序遍历

void LevelOrderTraverse(BiTree bt, LinkQueue *lq)
    {
    	ElemType elem;
    	if(lq->front!=lq->rear)
    	{
    		DeQueue(lq, &elem);
    		if(elem!=NULL)
    		{
    			printf("%c ", elem->data);
    			EnQueue(lq, elem->lchild);
    			EnQueue(lq, elem->rchild);
    		}else
    			printf("0 ");
    		LevelOrderTraverse(bt, lq);
    	}
    }

//非递归方式实现先序遍历

void PreOrderTraverse_N_Recur(BiTree bt)
    {
    	ElemType stackElem;
    	MyStack *stack = InitStack();
    	PushStack(stack, bt);
    
    	while(stack->top!=stack->base)
    	{
    		PopStack(stack,&stackElem);
    		if(stackElem!=NULL)
    		{
    			printf("%c ", stackElem->data);
    			PushStack(stack,stackElem->rchild);
    			PushStack(stack, stackElem->lchild);
    		}else
    			printf("0 ");
    	}
    }

//非递归方式中序遍历

void InOrderTraverse_N_Recur(BiTree bt)
    {
    	ElemType stackElem;
    	MyStack *stack = InitStack();
    	PushStack(stack, bt);
    
    	while(stack->top!=stack->base)
    	{
    		while((stackElem=(*(stack->top-1))->lchild)!=NULL)
    			PushStack(stack, stackElem);
    		do
    		{
    			printf("0 ");
    			PopStack(stack, &stackElem);
    			printf("%c ", stackElem->data);
    		}while(!stackElem->rchild&&stack->top!=stack->base);
    		if(stackElem->rchild!=NULL)
    			PushStack(stack, stackElem->rchild);
    		else
    			printf("0 ");
    	}
    }

//非递归方式后序遍历

void PostOrderTraverse_N_Recur(BiTree bt)
    {
    	ElemType stackElem;
    	MyStack *stack = InitStack();
    	BiTNode *tbn;
    	PushStack(stack, bt);
    
    	while(stack->top!=stack->base)
    	{
    		while((stackElem=*(stack->top-1))->lchild!=NULL)
    			PushStack(stack, stackElem->lchild);
    		printf("0 ");
    		if(stackElem->rchild!=NULL)
    			PushStack(stack, stackElem->rchild);
    		else
    		{
    			printf("0 ");
    			PopStack(stack, &stackElem);
    			while (stack->top!=stack->base)
    			{
    				while((*(stack->top-1))->rchild==stackElem)
    				{
    					printf("%c ", stackElem->data);
    					PopStack(stack, &stackElem);
    					if (stack->top==stack->base)
    					{
    						printf("%c ", stackElem->data);
    						return ;
    					}
    				}
    				if((*(stack->top-1))->lchild==stackElem)
    				{
    					printf("%c ", stackElem->data);
    					if((*(stack->top-1))->rchild!=NULL)
    					{
    						PushStack(stack, (*(stack->top-1))->rchild);
    						break;
    					}
    					else
    					{
    						printf("0 ");
    						PopStack(stack, &stackElem);
    					}
    				}
    			}
    		}
    	}
    	return ;
    }

//非递归方式实现层序遍历

void LevelOrderTraverse_N_Recur(BiTree bt)
    {
    	ElemType elem;
    	LinkQueue *lq = InitQueue();
    
    	EnQueue(lq, bt);
    	while(lq->front!=lq->rear)
    	{
    		DeQueue(lq, &elem);
    		if(elem!=NULL)
    		{
    			printf("%c ", elem->data);
    			EnQueue(lq, elem->lchild);
    			EnQueue(lq, elem->rchild);
    		}else
    			printf("0 ");
    	}
    }

[---]: http://blog.csdn.net/i2linux/article/details/47333865