4feidiguisuanfa.cpp

遍历二叉树的4个非递归算法 vc编程基础

#include <stdlib.h>
#include <stdio.h>
#define Maxsize  100
#define OK 1
#define OVERFLOW -2
typedef struct BinNode			/*定义二叉树结构*/
{  
	char data;
	struct BinNode	*lchild,*rchild;
} BinNode, *BinTree;
/**************************************建树**************************************************/
int CreateBinTree(BinTree *Tree)
{
	char ch;
	scanf("%c",&ch);
	if(ch == '.') 
		(*Tree) = NULL;
	else
	{
		if(!((*Tree) = (BinTree)malloc(sizeof(BinNode)))) 
			exit(OVERFLOW);
		(*Tree)->data = ch;
		CreateBinTree(&((*Tree)->lchild));
		CreateBinTree(&((*Tree)->rchild));
	}
	return OK; 
}/*CreateBiTree*/
/**************************************先序遍历************************************************/
void  Preorder (BinTree T)
{
	BinNode *stack[Maxsize],*p;
	int top;
	if(T)
	{
		top=1;             //根结点入栈
		stack[top]=T;
		while(top>0)
		{
			p=stack[top];  //退栈并访问该结点
			top--;
			printf("%c",p->data);
			if(p->rchild)   //右孩子入栈
			{
				top++;
				stack[top]=p->rchild;
			}
			if(p->lchild)   //左孩子入栈
			{
				top++;
				stack[top]=p->lchild;
			}
		}
	}
}
/**************************************中序遍历************************************************/
void Inorder(BinTree T)
{
	BinNode *stack[Maxsize],*p;
	int top=0;
	p=T;
	do
	{
		while(p)             //扫描左结点
		{
			top++;
			stack[top]=p;
			p=p->lchild;
		}
		if(top>0)
		{
			p=stack[top];    //*p所指结点为无左子树的结点或其左子树已遍历过
			top--;
			printf("%c",p->data);
			p=p->rchild;
		}
	}while(p || top!=0);
}

/**************************************后序遍历************************************************/
void Postorder(BinTree T)
{
	BinNode *stack[Maxsize],*p;
	int tag[Maxsize];
	int top=0;
	p=T;
	do
	{
		while(p)
		{
			top++;
			stack[top]=p;
			tag[top]=0;
			p=p->lchild;
		}
		if(top>0)
		{
			if(tag[top]==1) //该结点已经被访问过，说明其右孩子已经被访问过
			{
				printf("%c",stack[top]->data);
				top--;
			}
			else 
			{
				p=stack[top];
				if(top>0)
				{
					p=p->rchild;
					tag[top]=1;
				}
			}
		}
	}while(p || top!=0);
}

/**************************************层次遍历************************************************/

void Translevel(BinTree T)
{
	struct Bin
	{
		BinTree R[Maxsize];
		int f,r;
	}q;
	q.f=0;
	q.r=0;
	if(T)
		printf("%c",T->data);
	q.R[q.r]=T;  //结点T入队列
	q.r=q.r+1;
	while(q.f<q.r)  //队列不空
	{
		T=q.R[q.f];
		q.f=q.f+1;
		if(T->lchild)
		{
			printf("%c",T->lchild->data);
			q.R[q.r]=T->lchild;
			q.r=q.r+1;
		}
		if(T->rchild)
		{
			printf("%c",T->rchild->data);
			q.R[q.r]=T->rchild;
			q.r=q.r+1;
		}
	}
}

/*********************************************************************************************/

void main()		
{  
	BinTree T=NULL;
	printf("请输入您要建立的二叉树的先序扩展序列(用.表示空)\n");

	CreateBinTree(&T);
	printf("构造二叉树成功!\n");
    printf("先序遍历：");
    Preorder(T);
    printf("\n中序遍历：");
	Inorder(T);
	printf("\n后序遍历：");
	Postorder(T);
    printf("\n层次遍历：");
    Translevel(T);
    printf("\n");
}