数据结构 实验7 二叉树的应用

通过该实验，使学生理解二叉树的链式存储，掌握二叉树的几种遍历算法，并通过该实验使学生理解递归的含义，掌握C语言编写递归函数的方法和注意事项。

实现教材中算法6.4描述的二叉树创建算法，在此基础上实现二叉树的先序、后序递归遍历算法、两种非递归中序遍历、层序遍历、求二叉树的深度。注意：在非递归算法中用到栈和队列时，不要调用系统的栈和队列，需要自己实现栈和队列的操作。

 创建
输入 ：ABCKaTeX parse error: Can't use function '$' in math mode at position 3: DE$̲GF$$$ ($表示空格)
该输入对应的树如图所示
 先序 屏幕输出 A B C D E G F
 后序 屏幕输出 C G E F D B A
 中序 屏幕输出 C B E G D F A
(两种中序非递归还需看源代码)
 层序 屏幕输出 A B C D E F G
 深度 屏幕显示 深度为5
 另外自己画出一棵树，再测试一遍。

     Dev  C++

#include
#include
using namespace std;
#define OK 1
#define ERROR 0
#define MAX_TREE_SIZE 100
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef char TElemType;
typedef bool Status;
typedef struct BiTNode{
	TElemType data;
	struct BiTNode *lchild ,*rchild;
}BiTNode,*BiTree;
BiTree T;

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

Status PushStack(SqStack &S,SElemType p)
{
	if(S.top-S.base>=S.stacksize)
	{
		S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
		if(!S.base)	exit(OVERFLOW);
		S.top=S.base+S.stacksize;
		S.stacksize+=STACKINCREMENT;
	}
	*S.top++ = p;
	return OK;
}

Status PopStack(SqStack &S,SElemType &p)
{
	if(S.top == S.base)	return ERROR;
	p=*--S.top;
	return OK;
}

Status TopStack(SqStack &S,SElemType &p)
{
	if(S.top==S.base)
		return ERROR;
	p=*(S.top-1);
	return OK;
}

//1.创建二叉树 
Status createBiTree(BiTree &T)
{
	char ch;
	cin>>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 Print(TElemType e)
{
	printf("%c ",e);
	return OK;
}
//2.先序 
Status lastT(BiTree &T,Status(* visit)(TElemType e))
{
	if(T)
	{
		if(visit(T->data))
			if(lastT(T->lchild,Print))
				if(lastT(T->rchild,Print))
					return OK;
		return ERROR;
	}
	return OK;
}
//3.中序1 
Status zhongT(BiTree &T,Status(* visit)(TElemType e))
{
	SqStack S;
	InitStack(S);
	SElemType p;
	PushStack(S,T);
	while(S.top!=S.base)
	{
		while(TopStack(S,p) &&  p)
			PushStack(S,p->lchild);
		PopStack(S,p);
		if(S.top!=S.base)
		{
			PopStack(S,p);
			if(!visit(p->data))
				return ERROR;
			PushStack(S,p->rchild);
		}
	}
}
//4.中序2 
Status zhongT2(BiTree T,Status(* visit)(TElemType e))
{
	SqStack S;
	InitStack(S);
	SElemType p;
	p=T;
	while(p || S.top!=S.base)
	{
		if(p)
		{
			PushStack(S,p);
			p=p->lchild;
		}
		else
		{
			PopStack(S,p);
			if(!visit(p->data))
				return ERROR;
			p=p->rchild;
		}
	}
	return OK;
}
//5.后序 
Status postTree(BiTree &T,Status(* visit)(TElemType e))
{
	if(T)
	{
		if(postTree(T->lchild,Print))
			if(postTree(T->rchild,Print))
				if(visit(T->data))
					return OK;
		return ERROR;
	}
	return OK;
}
//6.层序 
Status cengTree(BiTree &T,Status(* visit)(TElemType e))
{
	int i=0,j=0;
	BiTree p[100];
	if(T)
		p[j++]=T;
	while(idata);
		if(p[i]->lchild)
			p[j++]=p[i]->lchild;
		if(p[i]->rchild)
			p[j++]=p[i]->rchild;
		i++;
	}
}

int DeepTree(BiTree T)
{
	int LD,RD;
	if(T==NULL)
		return 0;
	else
	{
		LD=DeepTree(T->lchild);
		RD=DeepTree(T->rchild);
		return (LD>=RD?LD:RD)+1;
	}
}

int main()
{
	cout<<"********************************"<>n;
		switch(n)
		{
			case 1:
				cout<<"请输入二叉树的元素来构建二叉树 ($表示空格) ：n    "; 
				createBiTree(T);
				cout<<"创建成功!"<