二叉树各种遍历算法.cpp

各种二叉树的遍历算法

#include<stdio.h>
#include<malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
	ElemType data;
	struct node *lchild;
	struct node *rchild;
}*BTNode;

void CreateBTNode(BTNode &b,char *str)
{
	BTNode St[MaxSize],p=NULL;
	int top=-1,k,j=0;
	char ch;
	b=NULL;
	ch=str[j];
	while(ch!='\0')
	{
		switch(ch)
		{
		    case'(':top++;St[top]=p;k=1;break;
		    case')':top--;break;
            case',':k=2;break;
			default:p=(BTNode)malloc(sizeof(node));
			    p->data=ch;
				p->lchild=p->rchild=NULL;
				if(b==NULL)
					b=p;
				else
				{
					switch(k)
					{
					     case 1:St[top]->lchild=p;break;
					     case 2:St[top]->rchild=p;break;
					}
				}

		}
		j++;
		ch=str[j];
	}
}

void DispBTNode(BTNode b)
{
	if(b!=NULL)
	{
		printf("%c",b->data);
		if(b->lchild!=NULL||b->rchild!=NULL)
		{
			printf("(");
			DispBTNode(b->lchild);
			if(b->rchild !=NULL)
				printf(",");
			DispBTNode(b->rchild);
			printf(")");
		}
	}
}

void PreOrder(BTNode b)    /*先序遍历的递归算法*/
{
	if(b!=NULL)
	{
		printf("%c",b->data);
		PreOrder(b->lchild);
		PreOrder(b->rchild);
	}
}
void PreOrder1(BTNode b)    /*先序遍历的非递归算法一*/
{
	BTNode p;
	struct
	{
		BTNode pt;
		int tag;
	}St[MaxSize];
	int top=-1;
	top++;
	St[top].pt=b;
	St[top].tag=1;
	while(top>-1)
	{
		if(St[top].tag==1)
		{
			p=St[top].pt;
			top--;
			if(p!=NULL)
			{
				top++;
				St[top].pt=p->rchild;
				St[top].tag=1;
				top++;
				St[top].pt=p->lchild;
				St[top].tag=1;
				top++;
				St[top].pt=p;
				St[top].tag=0;
			}
		}
		if(St[top].tag==0)
		{
			printf("%c",St[top].pt->data);
			top--;
		}
	}
}

void PreOrder2(BTNode b)    /*先序遍历的非递归算法二*/
{
	BTNode St[MaxSize],p;
	int top=-1;
	if(b!=NULL)
	{
		top++;
		St[top]=b;
		while(top>-1)
		{
			p=St[top];
			top--;
			printf("%c",p->data);
			if(p->rchild!=NULL)
			{
				top++;
				St[top]=p->rchild;
			}
			if(p->lchild!=NULL)
			{
				top++;
				St[top]=p->lchild;
			}
		}
		printf("\n");
	}
}

void InOrder(BTNode b)    /*中序遍历的递归算法*/
{
	if(b!=NULL)
	{
		InOrder(b->lchild);
		printf("%c",b->data);
		InOrder(b->rchild);
	}
}
void InOrder1(BTNode b)    /*中序遍历的非递归算法一*/
{
	BTNode p;
	struct
	{
		BTNode pt;
		int tag;
	}St[MaxSize];
	int top=-1;
	top++;
	St[top].pt=b;
	St[top].tag=1;
	while(top>-1)
	{
		if(St[top].tag==1)
		{
			p=St[top].pt;
			top--;
			if(p!=NULL)
			{
				top++;
				St[top].pt=p->rchild;
				St[top].tag=1;
				top++;
				St[top].pt=p;
				St[top].tag=0;
				top++;
				St[top].pt=p->lchild;
				St[top].tag=1;
			}
		}
		if(St[top].tag==0)
		{
			printf("%c",St[top].pt->data);
			top--;
		}
	}
}
void InOrder2(BTNode b)    /*中序遍历的非递归算法二*/
{
	BTNode St[MaxSize],p;
	int top=-1;
	if(b!=NULL)
	{
		p=b;
		while(top>-1||p!=NULL)
		{
			while(p!=NULL)
			{
				top++;
				St[top]=p;
				p=p->lchild;
			}
			if(top>-1)
			{
				p=St[top];
				top--;
				printf("%c",p->data);
				p=p->rchild;
			}
		}
		printf("\n");
	}
}

void PostOrder(BTNode b)    /*后序遍历的递归算法*/
{
	if(b!=NULL)
	{
		PostOrder(b->lchild);
		PostOrder(b->rchild);
		printf("%c",b->data);
	}
}
void PostOrder1(BTNode b)    /*后序遍历的非递归算法一*/
{
	BTNode p;
	struct
	{
		BTNode pt;
		int tag;
	}St[MaxSize];
	int top=-1;
	top++;
	St[top].pt=b;
	St[top].tag=1;
	while(top>-1)
	{
		if(St[top].tag==1)
		{
			p=St[top].pt;
			top--;
			if(p!=NULL)
			{
				top++;
				St[top].pt=p;
				St[top].tag=0;
				top++;
				St[top].pt=p->rchild;
				St[top].tag=1;
				top++;
				St[top].pt=p->lchild;
				St[top].tag=1;
			}
		}
		if(St[top].tag==0)
		{
			printf("%c",St[top].pt->data);
			top--;
		}
	}
}
void PostOrder2(BTNode b)    /*后序遍历的非递归算法二*/
{
	BTNode St[MaxSize],p;
	int flag,top=-1;
	if(b!=NULL)
	{
		do
		{
			while(b!=NULL)
			{
				top++;
				St[top]=b;
				b=b->lchild;
			}
			p=NULL;
			flag=1;
			while(top!=-1&&flag)
			{
				b=St[top];
				if(b->rchild==p)
				{
					printf("%c",b->data);
					top--;
					p=b;
				}
				else
				{
					b=b->rchild;
					flag=0;
				}
			}
		}while(top!=-1);
		printf("\n");
	}
}
void TravLevel(BTNode b)         /*层次遍历*/
{
	BTNode Qu[MaxSize];
	int front,rear;
	front=rear=0;
	if(b!=NULL)
		printf("%c",b->data);
	rear++;
	Qu[rear]=b;
	while(rear!=front)
	{
		front=(front+1)%MaxSize;
		b=Qu[front];
		if(b->lchild!=NULL)
		{
			printf("%c",b->lchild->data);
			rear=(rear+1)%MaxSize;
			Qu[rear]=b->lchild;
		}
		if(b->rchild!=NULL)
		{
			printf("%c",b->rchild->data);
			rear=(rear+1)%MaxSize;
			Qu[rear]=b->rchild;
		}
	}
}
void main()
{
	BTNode b;
	CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
	printf("二叉树b： ");DispBTNode(b);printf("\n\n");
	printf("层次遍历序列： ");
	TravLevel(b);
	printf("\n");
	printf("先序遍历序列：\n");
	printf("   递归算法：");PreOrder(b);printf("\n");
	printf("非递归算法1：");PreOrder1(b);printf("\n");
	printf("非递归算法2：");PreOrder2(b);printf("\n");
	printf("中序遍历序列：\n");
	printf("   递归算法：");InOrder(b);printf("\n");
	printf("非递归算法1：");InOrder1(b);printf("\n");
	printf("非递归算法2：");InOrder2(b);printf("\n");
	printf("后序遍历序列：\n");
	printf("   递归算法：");PostOrder(b);printf("\n");
	printf("非递归算法1：");PostOrder1(b);printf("\n");
	printf("非递归算法2：");PostOrder2(b);printf("\n");
}