binary tree.cpp

二叉树应用-线索化二叉树遍历的源码以及实验报告！

//ABC##DE#G##F###

#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0
#define OVERFLOW 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef int status;
typedef char TElemType;
typedef enum PointerTag{Link,Thread};

typedef struct BiTNode{
	TElemType data;
	struct BiTNode *lchild ,*rchild;
	PointerTag LTag , RTag;
}BiTNode , *BiTree , BiThrNode , *BiThrTree;

typedef struct{
	BiTree *base;
	BiTree *top;
	int stacksize;
}SqStack;

//二叉树
status CreatBiTree(BiTree &T);
status treedepth(BiTree T);
status Visit(TElemType e);
status PreOrderTraverse(BiTree T,status(*Visit)(TElemType e));
status InOrderTraverse(BiTree T,status(*Visit)(TElemType e));
status PostOrderTraverse(BiTree T,status(*Visit)(TElemType e));
status UnInOrderTraverse(BiTree T,status(*Visit)(TElemType e));	//非递归中序遍历
status UnPreOrderTraverse(BiTree T,status(*Visit)(TElemType e));	//非递归先序遍历
//线索化二叉树
void InOrderThreading(BiThrTree &Thrt,BiThrTree T);
void InThreading(BiThrTree p);
status InOrderTraverse_Thr(BiThrTree T, status (*Visit)(TElemType e));
void PreOrderThreading(BiThrTree &Thrt,BiThrTree T);
status PreOrderTraverse_Thr(BiThrTree T, status (*Visit)(TElemType e));
void PreThreading(BiThrTree p);
void UnThreading(BiThrTree &Thrt);
//栈的操作
status InitStack(SqStack &S);
status GetTop(SqStack S , BiTree &e);
status Push(SqStack &S , BiTree e);
status Pop(SqStack &S , BiTree &e);
status StackEmpty(SqStack S);

//全局变量
SqStack S;
BiThrTree pre;
BiThrTree i;

void main()
{
	printf("\t************\n\t*二叉树演示*\n\t************\n");
	BiTree T;
	BiThrTree Thrt;
	printf("\n创建二叉树(用#表示空格):\n");
	CreatBiTree(T);
	printf("树的高度为:%d",treedepth(T));
	printf("\n递归先序遍历:");
	PreOrderTraverse(T , Visit);
	printf("\n递归中序遍历:");
	InOrderTraverse(T , Visit);
	printf("\n递归后序遍历:");
	PostOrderTraverse(T , Visit);
	printf("\n非递归中序遍历:");
	UnInOrderTraverse(T , Visit);
	printf("\n非递归先序遍历:");
	UnPreOrderTraverse(T , Visit);
	printf("\n中序遍历线索化二叉树:");
	InOrderThreading(Thrt , T);
	InOrderTraverse_Thr(Thrt , Visit);
	printf("\n后序递归去线索化并输出:");
	UnThreading(Thrt);
	printf("\n先序遍历线索化二叉树:");
	PreOrderThreading(Thrt , T);
	printf("\n");
}

status CreatBiTree(BiTree &T){
	char ch;
	ch=getchar();
	if(ch=='#')
	T=NULL;
	else{
		if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
			return ERROR;
		T->data=ch;
		if (CreatBiTree(T->lchild)) T->LTag=Link;
		if (CreatBiTree(T->rchild)) T->RTag=Link;
	}
	return OK;
}

status treedepth(BiTree T)  //树的高度
{
	int lchilddep,rchilddep;
	if(T==NULL)
		return 0;
	else
	{
		lchilddep=treedepth(T->lchild);
		rchilddep=treedepth(T->rchild);
		if(lchilddep>rchilddep)
			return lchilddep+1;
		else
			return rchilddep+1;
	}
}

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

status PreOrderTraverse(BiTree T,status(*Visit)(TElemType e))		//先序遍历
{
	if(T)
	{
		if(Visit(T->data))
			if(PreOrderTraverse(T->lchild,Visit))
				if(PreOrderTraverse(T->rchild,Visit))
					return OK;
				return ERROR;
	}
	else
		return OK;
}//PreOrderTraverse

status InOrderTraverse(BiTree T,status(*Visit)(TElemType e))		//中序遍历
{
	if(T)
	{
		if(InOrderTraverse(T->lchild,Visit))
			if(Visit(T->data))
				if(InOrderTraverse(T->rchild,Visit))
					return OK;
				return ERROR;
	}
	else return OK;
}//InOrderTraverse

status PostOrderTraverse(BiTree T,status(*Visit)(TElemType e))		//后序遍历
{
	if(T)
	{
		if(PostOrderTraverse(T->lchild,Visit))
			if(PostOrderTraverse(T->rchild,Visit))
				if(Visit(T->data))
					return OK;
				return ERROR;
	}
	else return OK;
}//PostOrderTraverse

status UnInOrderTraverse(BiTree T,status(*Visit)(TElemType e))	//非递归中序遍历
{
	BiTree p;
	InitStack(S);
	Push(S,T);
	while(!StackEmpty(S))
	{
		while(GetTop(S,p) && p)
			Push(S,p->lchild);
		Pop(S,p);
		if(!StackEmpty(S))
		{
			Pop(S,p);
			if(!Visit(p->data))
				return ERROR;
			Push(S,p->rchild);
		}//if
	}//while
	return OK;
}//UnInOrderTraverse

status UnPreOrderTraverse(BiTree T,status(*Visit)(TElemType e))	//非递归先序遍历
{
	BiTree p;
	InitStack(S);
	p=T;
	while(p||!StackEmpty(S))
	{
		if(p)
		{
			if(!Visit(p->data))
				return ERROR;
			Push(S,p);
			p=p->lchild;
		}
		else
		{
			Pop(S,p);
			p=p->rchild;
		}//else
	}//while
	return OK;
}//UnPreOrderTraverse

void InOrderThreading(BiThrTree &Thrt,BiThrTree T)
//中序遍厉二叉树T，并将其中序线索化，Thrt指向头结点
{
	if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);
	Thrt->LTag=Link;//建头结点
	Thrt->RTag=Thread;
	Thrt->rchild=Thrt;//右指针回指
	if(!T)
	Thrt->lchild=Thrt;
	else
	{
		Thrt->lchild=T;
		pre=Thrt;
		InThreading(T);//中序遍历进行中序线索化
		pre->rchild=Thrt;
		pre->RTag=Thread;//最后一个结点线索化
		Thrt->rchild=pre;
	}
	i=Thrt;
}//InOrderThreading

void InThreading(BiThrTree p)
{
	if(p)
	{
		InThreading(p->lchild);
		if(!p->lchild)
		{
			p->LTag = Thread;
			p->lchild = pre;
		}
		if(!pre->rchild)
		{
			pre->RTag = Thread;
			pre->rchild = p;
		}
		pre = p;
		InThreading(p->rchild);
	}
}//InThreading

void UnThreading(BiThrTree &Thrt)  //后序去线索化
{
	BiThrTree p=Thrt;
	if(p)
	{
		if(p->LTag == Thread)
		{
			p->lchild = NULL;
			p->LTag = Link;
		}
		if(p->LTag == Link && p->lchild) UnThreading(p->lchild);
		if(p->RTag == Link && p->rchild)UnThreading(p->rchild);
		if(p != i) Visit(p->data);
	}
}

status InOrderTraverse_Thr(BiThrTree T, status (*Visit)(TElemType e))
{
	BiThrTree p;
	p=T->lchild;
	while(p!=T)
	{
		while(p->LTag==Link)
			p=p->lchild;
		if(!Visit(p->data))
			return ERROR;
		while(p->RTag==Thread && p->rchild!=T)
		{
			p=p->rchild;
			Visit(p->data);
		}
		p=p->rchild;
	}
	return OK;
}

void PreOrderThreading(BiThrTree &Thrt,BiThrTree T)
//先序遍厉二叉树T，并将其先序线索化，Thrt指向头结点
{
	if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);
	Thrt->LTag=Link;
	Thrt->RTag=Thread;//建头结点
	Thrt->rchild=Thrt;//右指针回指
	if(!T)
	Thrt->lchild=Thrt;
	else
	{
		Thrt->lchild=T;
		pre=Thrt;
		PreThreading(T);//先序遍历进行先序线索化
		pre->rchild=Thrt;pre->RTag=Thread;//最后一个结点线索化
		Thrt->rchild=pre;
	}
	i=Thrt;
}

status PreOrderTraverse_Thr(BiThrTree T, status (*Visit)(TElemType e)) //error
{
	BiThrTree p;
	p=T->lchild;
	while(p!=T)
	{
		while(p->LTag==Link)
			p=p->lchild;
		if(!Visit(p->data))
			return ERROR;
		while(p->RTag==Thread && p->rchild!=T)
		{
			p=p->rchild; Visit(p->data);
		}
		p=p->rchild;
	}
	return OK;
}//PreOrderTraverse_Thr

void PreThreading(BiThrTree p)
{
	if(p)
	{
		//s=p;
		
		if(!p->lchild)
		{
			p->LTag = Thread;
			p->lchild = pre;
		}
		if(!pre->rchild)
		{
			pre->RTag = Thread;
			pre->rchild = p;
		}
		pre = p;
		Visit(p->data);
		
		if(p->LTag==Link)
			PreThreading(p->lchild);
		if(p->RTag == Link)
			PreThreading(p->rchild);
	}
}//PreThreading

status InitStack(SqStack &S)
{
	S.base=(BiTree *)malloc(STACK_INIT_SIZE * sizeof(BiTree));
	if(!S.base)exit(OVERFLOW);
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
	return OK;
}

status GetTop(SqStack S , BiTree &e)
{
	if(S.top == S.base) return ERROR;
	else{
		e = *(S.top-1);
		return OK;
	}
}


status Push(SqStack &S , BiTree e)
{
	if(S.top - S.base >= S.stacksize)
	{
		S.base = (BiTree *)realloc(S.base , (S.stacksize + STACKINCREMENT) * sizeof(BiTree));
		if(!S.base) exit(OVERFLOW);
		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREMENT;
	}
	*S.top++ = e;
	return OK;
}


status Pop(SqStack &S , BiTree &e)
{
	if(S.top == S.base)
		return ERROR;
	else{
		e = * --S.top;
		return OK;
	}
}

status StackEmpty(SqStack S)
{
	if(S.top == S.base)
		return 1;
	else
		return 0;
}