bitree.cpp

二叉树的实现

//二叉树功能的实现，包括创建，遍历和求深度
//使用前应定义TElemType
#include <stdlib.h>
#include <stdio.h>
#include "..\include\preDefine.h"
//二叉树存储结构定义
typedef struct BiTNode{
	TElemType data;
	struct BiTNode *lchild,*rchild;
	int tag;
}BiTNode,*BiTree;
typedef BiTree SElemType; 
#include "..\include\stack.cpp"
typedef BiTree QElemType; 
#include "..\include\queue.cpp"
//二叉树的基本操作实现，部分
Status PostOrderTraverse(BiTree &T,Status (*Visit)(BiTree));

Status PrintElement(BiTree n)
{
	printf("%c",n->data);
	return OK;
}
Status FreeElement(BiTree n)
{
	free(n);
	return OK;
}
//按后序遍历销毁二叉树
Status DestroyBiTree(BiTree &T)
{
	PostOrderTraverse(T,FreeElement);
	return OK;
}
//按先序扩展序列建立二叉树
Status CreateBiTree(BiTree &T,char *pch)
{
	static char *p=pch;
	if(*p=='.') T=NULL;
	else
	{
		if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
		T->data=*p;T->tag=0;
		CreateBiTree(T->lchild,++p);
		CreateBiTree(T->rchild,++p);
	}
	return OK;
}
bool BiTreeEmpty(BiTree &T)
{
	if(T->lchild==NULL && T->rchild==NULL) return true;
	else return false;
}
//求二叉树深度，后序遍历
int BiTreeDepth(BiTree &T)
{
	int depthLeft,depthRight,depthval;
	if (!T) depthval = 0;
	else
    { depthLeft = BiTreeDepth(T->lchild);
      depthRight= BiTreeDepth(T->rchild);
      depthval = 1 + (depthLeft>depthRight ? depthLeft : depthRight);
    } 
   return depthval;
}

//递归遍历的实现
Status PreOrderTraverse(BiTree &T,Status (*Visit)(BiTree))
{
	if(T)
	{
		if(Visit(T))
			if(PreOrderTraverse(T->lchild,Visit))
				if(PreOrderTraverse(T->rchild,Visit)) return OK;
		return ERROR;
	}
	else return OK;
}
Status InOrderTraverse(BiTree &T,Status (*Visit)(BiTree))
{
	if(T)
	{
		if(InOrderTraverse(T->lchild,Visit))
			if(Visit(T))
				if(InOrderTraverse(T->rchild,Visit)) return OK;
		return ERROR;
	}
	else return OK;
}
Status PostOrderTraverse(BiTree &T,Status (*Visit)(BiTree))
{
	if(T)
	{
		if(PostOrderTraverse(T->lchild,Visit))
			if(PostOrderTraverse(T->rchild,Visit))
				if(Visit(T)) return OK;
		return ERROR;
	}
	else return OK;
}
//非递归遍历的实现
Status LevelOrderTraverse(BiTree &T,Status (*Visit)(BiTree))
{
	SqQueue Q;	BiTree p;
	InitQueue(Q);	p=T;
	if(p!=NULL) EnQueue(Q,p);
	while(QueueLength(Q)!=0)
	{
		DeQueue(Q,p);
		if(Visit(p)!=OK) return ERROR;
		if(p->lchild!=NULL) EnQueue(Q,p->lchild);	
		if(p->rchild!=NULL) EnQueue(Q,p->rchild);
	}
	DestroyQueue(Q);
	return OK;
}
Status PreOrderTraverse1(BiTree &T,Status (*Visit)(BiTree))
{
	SqStack S;	BiTree p;
	InitStack(S);	p=T;
	while(p || !StackEmpty(S))
	{
		if(p) 
		{
			Push(S,p);	if(Visit(p)!=OK) return ERROR;
			p=p->lchild;
		}
		else {Pop(S,p);	p=p->rchild;}
	}
	DestroyStack(S);
	return OK;
}

Status InOrderTraverse1(BiTree &T,Status (*Visit)(BiTree))
{
	SqStack S;	BiTree p;
	InitStack(S);	p=T;
	while(p || !StackEmpty(S))
	{
		if(p) {Push(S,p);	p=p->lchild;}
		else
		{
			Pop(S,p);	if(Visit(p)!=OK) return ERROR;
			p=p->rchild;
		}
	}
	DestroyStack(S);
	return OK;
}

Status PostOrderTraverse1(BiTree &T,Status (*Visit)(BiTree))
{
	SqStack S;	BiTree p;Status status;
	InitStack(S);	p=T;
	while((p || !StackEmpty(S)) && status!=ERROR)
	{
		if(p) switch(p->tag)
		{
			case 0:p->tag=1;Push(S,p);p=p->lchild;break;
			case 1:p->tag=2;Push(S,p);p=p->rchild;break;
			case 2:if(Visit(p)!=OK) return ERROR;
				p->tag=0;status=Pop(S,p);break;
		}
		else status=Pop(S,p);
	}
	DestroyStack(S);
	return OK;
}