binarytree.cpp

二叉树的遍历操作

#include "Operater Declare.h"

void CreateBinTree(BinTree &T)
{
	//按照先序次序的递归建立二叉树操作
	TElemType ch;
	scanf("%c",&ch);
	if(ch==' ')
	{
		T=NULL;
	}
	else
	{
		if(!(T=(BinTree)malloc(sizeof(BiTNode)))) 
		{
			exit(OVERFLOW);
		}
		T->data=ch;
		CreateBinTree(T->lchild);
		CreateBinTree(T->rchild);
	}
	return;
}

//-------遍历操作------
void PreOrderTraverse(BinTree T)
{
	//先序遍历
	//操作结果：输出二叉树中各个节点的值
	if(T)
	{
		printf("%c ",T->data);
		PreOrderTraverse(T->lchild);
		PreOrderTraverse(T->rchild);

	}
	return;
}

void InOrderTraverse(BinTree T)
{
	//中序遍历
	//操作结果：输出二叉树中各个节点的值
	if(T)
	{
		InOrderTraverse(T->lchild);
		printf("%c ",T->data);
		InOrderTraverse(T->rchild);

	}
	return;
}

void PostOrderTraverse(BinTree T)
{
	//后序遍历
	//操作结果：输出二叉树中各个节点的值
	if(T)
	{
		PostOrderTraverse(T->lchild);
		PostOrderTraverse(T->rchild);
		printf("%c ",T->data);
	}
	return;
}

void LevelOrderTraverse(BinTree T)
{
	//层次遍历
	LinkQueue q;
	QElemType a;
	if(T)
	{
		InitQueue(q);
		EnQueue(q,T);
		while(!QueueEmpty(q))
		{
			DeQueue(q,a);
			printf("%c ",a->data);
			if(a->lchild)
				EnQueue(q,a->lchild);
			if(a->rchild)
				EnQueue(q,a->rchild);
		}
	}
	return;
}

void PreOrderTraverseRE(BinTree T)
{
	SqStack S;
	BinTree p;
	InitStack(S);
	p=T;
	while(p || !StackEmpty(S))
	{
		if(p)
		{
			printf("%c ",p->data);
			Push(S,p);
			p=p->lchild;
		}
		else
		{
			Pop(S,p);
			p=p->rchild;
		}
	}
	printf("\n");
	return;		
}

void InOrderTraverseRE(BinTree T)
{
	//中序非递归遍历
	SqStack S;
	BinTree p;
	InitStack(S);
	p=T;
	while(p || !StackEmpty(S))
	{
		if(p)
		{
			Push(S,p);	
			p=p->lchild;
		}
		else
		{
			Pop(S,p);
			printf("%c ",p->data);
			p=p->rchild;
		}
	}
	printf("\n");
	return;
}

void PostOrderTraverseRE(BinTree T)
{
	//后序非递归遍历
	BinTree p;
	SqStack S;
	InitStack(S);
	p=T;
	p->mark=zero;
	Push(S,p);//根结点进栈
	while(! StackEmpty(S))
	{
		Pop(S,p);
		switch(p->mark)
		{
		case 0:
			p->mark=one;
			Push(S,p);
			if(p->lchild)
			{
				p=p->lchild;
				p->mark=zero;
				Push(S,p);  //访问左子树
			}
			break;

		case 1:
			p->mark=two;
			Push(S,p);
			if(p->rchild)
			{
				p=p->rchild;
				p->mark=zero;
				Push(S,p);  //访问右子树
			
			}
			break;

		case 2:
			printf("%c ",p->data);


		}

	}
	return;
}