二叉树遍历

#include <stdio.h>
#include <stack>
#include <queue>
using namespace std;

typedef char DataType;

typedef struct BiTNode
{
	DataType data;
	struct BiTNode *lchild,*rchild;
}BITNode;
typedef BiTNode* BiTree;


//先序创建二叉树
int CreateBiTree(BiTree& T)
{
	DataType data;
	scanf("%c",&data);

	if(data == ‘#‘)
	{
		T = NULL;
	}
	else
	{
		T = new BiTNode;
		T->data = data;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}

	return 0;
}

void Visit(BiTree T)
{
	if(T->data != ‘#‘)
	{
		printf("%c ",T->data);
	}
}

//先序遍历
void PreOrder(BiTree T)
{
	stack<BiTree> stack;
	BiTree p = T;
	while(p || !stack.empty())
	{
		if(p != NULL)
		{
			stack.push(p);
			printf("%c ",p->data);
			p = p->lchild;
		}
		else
		{
			p = stack.top();
			stack.pop();
			p = p->rchild;
		}
	}
}

//中序遍历
void InOrder(BiTree T)
{
	stack<BiTree> stack;
	BiTree p = T;
	while(p || !stack.empty())
	{
		if(p != NULL)
		{
			stack.push(p);
			p = p->lchild;
		}
		else
		{
			p = stack.top();
			printf("%c ",p->data);
			stack.pop();
			p = p->rchild;
		}
	}
}

//后序遍历
void PostOrder(BiTree T)
{
	BiTNode* p,*q;
	stack<BiTree> stack;
	q = NULL;
    p = T;
	while(p != NULL || !stack.empty())
	{
		while(p != NULL)
		{
			stack.push(p);
            p = p->lchild;
		}
		if(!stack.empty())
		{
			p = stack.top();
			if(p->rchild == NULL || p->rchild == q)
			{
				printf("%c ",p->data);
				q = p;
				stack.pop();
				p = NULL;
			}
			else
			{
				p = p->rchild;
			}
		}
	}
}

//层次遍历
void LevelOrder(BiTree T)
{
	BiTree p = T;
	queue<BiTree> queue;
	queue.push(p);
	while(!queue.empty())
	{
		p = queue.front();
		printf("%c ",p->data);
		queue.pop();
		if(p->lchild != NULL)
		{
			queue.push(p->lchild);
		}
		if(p->rchild != NULL)
		{
			queue.push(p->rchild);
		}
	}
}

//深度遍历
void DepthOrder(BiTree T)
{
	stack<BiTNode*> stack;
	stack.push(T);
	BiTNode* p;
	while(!stack.empty())
	{
		p = stack.top();
		printf("%c ",p->data);
		stack.pop();
	    if(p->rchild)
		{
			stack.push(p->rchild);
		}
		if(p->lchild)
		{
			stack.push(p->lchild);
		}
	}
}

//广度遍历
void BreadthOrder(BiTree T)
{
	queue<BiTNode*> queue;
	queue.push(T);
	BiTNode* p;
	while(!queue.empty())
	{
		p = queue.front();
		queue.pop();
		printf("%c ",p->data);
		if(p->lchild)
		{
			queue.push(p->lchild);
		}
		if(p->rchild)
		{
			queue.push(p->rchild);
		}
	}
}

//ABC##DE#G##F###
int main(int argc,char** argv)
{
	BiTree T;  
	CreateBiTree(T);  
	printf("先序遍历：\n");  
	PreOrder(T);  
	printf("\n");  

	printf("中序遍历：\n");  
	InOrder(T);  
	printf("\n");  

	printf("后序遍历：\n");  
	PostOrder(T);  
	printf("\n");

	printf("层次遍历：\n");  
	LevelOrder(T);  
	printf("\n");  

	printf("深度遍历：\n");  
	DepthOrder(T);  
	printf("\n");

	printf("广度遍历：\n");  
	BreadthOrder(T);  
	printf("\n");

	printf("\n");  
	return 0;  

}