bitree.cpp

数据结构中的二叉树的遍历（前序、中序、后序）算法

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include "..\\header\\Bitree.h"

Status Visit(TElemType e)
{
	printf("%c", e);
	return OK;
}

//按先序次序输入二叉树中结点的值(一个字符)，空格字符表示空树，
//构造二叉链表表示的二叉树T
Status CreateBiTree(BiTree &T)
{
	TElemType ch;
	scanf("%c", &ch);
	if(ch == '#') T=NULL;
	else
	{
		if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
		T->data = ch;				//生成根结点

		CreateBiTree(T->lchild);	//构造左子树
		CreateBiTree(T->rchild);	//构造右子树
	}
	return OK;
}

//销毁树
Status DestroyBiTree(BiTree &T)
{
	if (T==NULL) return OK;

	DestroyBiTree(T->lchild);
	DestroyBiTree(T->rchild);

	free(T);	
	T = NULL;
	return OK;
}

//先序递归遍历二叉树T，对每个结点调用函数Visit一次且仅一次。
Status PreOrderTraverseR(BiTree T, Status(*Visit)(TElemType e))
{
	if(T)
	{
		if(Visit(T->data))
			if(PreOrderTraverseR(T->lchild, Visit))
				if(PreOrderTraverseR(T->rchild, Visit)) 
					return OK;

		return ERROR;

	}else
		return OK;
}

//先序非递归遍历二叉树T，对每个结点调用函数Visit一次且仅一次。
Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
	SqStack S;
	InitStack(S);

	BiTNode* p = T;
	while(p != NULL || !IsStackEmpty(S))
	{
		while(p != NULL)
		{
			if(!Visit(p->data)) 
				return ERROR;

			Push(S, p);

			p = p->lchild;
		}
		
		if(!IsStackEmpty(S))
		{
			p = Pop(S);				//为什么这个调用可以！实际上Pop函数返回值在系统Stack中已经分配地址			
			p = p->rchild;
		}
	}

	DestroyStack(S);
	return OK;	
}

//中序递归遍历二叉树T，对每个结点调用函数Visit一次且仅一次。
Status InOrderTraverseR(BiTree T, Status(*Visit)(TElemType e))
{
	if(T)
	{
		if(InOrderTraverseR(T->lchild, Visit))
			if(Visit(T->data))
			{
				if(InOrderTraverseR(T->rchild, Visit)) 
					return OK;
			}else
				return ERROR;
	}else
		return OK;
	
	return OK;
}

//中序非递归遍历二叉树T，对每个结点调用函数Visit一次且仅一次。
Status InOrderTraverse1(BiTree T, Status(*Visit)(TElemType e))	//方法1(6.2)
{
	SqStack S;
	InitStack(S);

	BiTNode* p = T;
	while(p != NULL || !IsStackEmpty(S))
	{
		while(p != NULL)
		{
			Push(S, p);
			p = p->lchild;
		}

		
		if(!IsStackEmpty(S))
		{
			//p = (BiTNode*)malloc(sizeof(BiTNode));
			//Pop(S, p);			//Here, the problem is how to delete p?

			p = Pop(S);				//为什么这个调用可以！实际上Pop函数返回值在系统Stack中已经分配地址

			if(!Visit(p->data)) 
				return ERROR;
			
			p = p->rchild;
		}
	}

	DestroyStack(S);
	return OK;
}

//中序非递归遍历二叉树T，对每个结点调用函数Visit一次且仅一次。
Status InOrderTraverse2(BiTree T, Status(*Visit)(TElemType e))	//方法2(6.3)
{

	return OK;
}

//后序递归遍历二叉树T，对每个结点调用函数Visit一次且仅一次。
Status PostOrderTraverseR(BiTree T, Status(*Visit)(TElemType e))
{
	if(T)
	{
		if(PostOrderTraverseR(T->lchild, Visit))
			if(PostOrderTraverseR(T->rchild, Visit)) 
				if(!Visit(T->data)) 
					return ERROR;
	}else
		return OK;

	return OK;
}

//后序非递归遍历二叉树T，对每个结点调用函数Visit一次且仅一次。
Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
	SqStack S;
	InitStack(S);
	
	BiTNode* p = T;
	do
	{
		while(p != NULL)
		{
			p->tag = L;
			Push(S, p);

			p = p->lchild;
		}
		
		while(!IsStackEmpty(S) && ((S.top-1)->tag==R))
		{
			p = Pop(S);				//为什么这个调用可以！实际上Pop函数返回值在系统Stack中已经分配地址			

			if(!Visit(p->data)) 
				return ERROR;
		}

        if (!IsStackEmpty(S))
        {
            (S.top-1)->tag = R;     //遍历右子树
			p = (S.top-1)->rchild;
        }    
	}while(!IsStackEmpty(S));

	DestroyStack(S);
	return OK;	
}

//层序遍历二叉树，对每个结点调用函数Visit一次且仅一次。
//使用队列来实现其遍历过程。
Status LevelOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
	LinkQueue Q;

	InitQueue(Q);
	BiTNode* p = T;	

	EnQueue(Q, p);
	while(!IsQueueEmpty(Q))
	{
		BiTNode* q = (BiTNode*)malloc(sizeof(BiTNode));
		DeQueue(Q, q);
		
		if(q)
		{
			if(!Visit(q->data))
				return ERROR;

			EnQueue(Q,q->lchild);
			EnQueue(Q,q->rchild);
		}
		if(q)
		{
			free(q);
			q = NULL;
		}
	}

	DestroyQueue(Q);
	return OK;
}

Status (*VisitPtr)(TElemType);			//函数指针变量VisitPtr	

int main(int argc, char* argv[])
{
	BiTree root;

	printf("sizeof BiTNode:%d\n", sizeof(BiTNode));
	printf("Please input the pre-nodes of tree:(ex. ABC##DE#G##F###)\n");
	if(!CreateBiTree(root)) return -1;

	//VisitPtr = Visit;  //将Visit函数的地址赋给VisitPtr变量
	//(*FunP)(20);    //这是通过函数指针变量VisitPtr来调用Visit函数的。
	//(*VisitPtr)('c');

	printf("\n PreOrder VisitR(cursive): ");
	PreOrderTraverseR(root, Visit);

	printf("\n PreOrder Visit: ");
	PreOrderTraverse(root, Visit);

	printf("\n InOrder VisitR(cursive): ");
	InOrderTraverseR(root, Visit);

	printf("\n InOrder Visit1: ");
	InOrderTraverse1(root, Visit);
	
	printf("\n InOrder Visit2: ");
	InOrderTraverse2(root, Visit);

	printf("\n PostOrder VisitR(cursive): ");
	PostOrderTraverseR(root, Visit);

	printf("\n PostOrder Visit: ");
	PostOrderTraverse(root, Visit);

	printf("\n LevelOrder Visit:");
	LevelOrderTraverse(root, Visit);

	DestroyBiTree(root);

	system("pause");

	return 0;
}