binary_tree.txt

创建一个二叉树及进行二叉树的遍历、计算、复制等相关基本操作

二叉树实验报告
题目：编制一个创建、遍历、计算、复制二叉树的程序

一、问题的描述
1、			本演示程序中，各结点的值定为各字符，树的大小可以很大。树建立时每次读入一个字符，一次以“Enter”为结束字符；树以“0”为结束读入的标志字符。遍历的结果全是字符，为各节点的值；结点个数为整数，深度为整数。
2、	演示程序以用户和计算机的对话方式进行，也就是在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的数字以作为个人手中的密码。
3、	程序执行的命令包括：
1）	扩展先序建立二叉树 
2）	遍历二叉树：1、先序便历；2、中序便历；3、后序便历；4、层次便历
3）	计算二叉树结点数、叶子数、高度、宽度
4）	复制二叉树 
4、测试数据
用户输入的数据为abc00de0g00f000(0为空格)；依次调用程序，则输出结果应为：1、先序便历结果是：abcdegf;2、中序便历结果是：cbegdfa;3、后序便历结果是：cgefdba;4、层次便历结果是：abcdefg;5、结点数是7；6、叶子数是3；7、高度是5；8、宽度是2；9复制上述二叉树再先序便历的结果是：abcdegf。
二、存储结构的描述
结点类型和指针类型
typedef struct BiTNode
{
	char     data;
	struct BiTNode   *lchild,*rchild;
}BiTNode,*BiTree;
为实现上述功能，现以二叉链表表示树。为此需要一个抽象数据类型：二叉链表。
二叉树的抽象数据类型定义为：ADT Linklist{
数据对象D：D是具有相同特性的数据元素的集合
数据关系R：
若D=空集，则R=空集，为空二叉树
若D非空，则R={H},H是如下二元关系：
（1）	在D中存在唯一的称为根的数据元素root，它在关系H下前驱；
（2）	若D-{root}非空，则存在D-{root}={D1,Dr},且D1∩Dr为空；
（3）	若D1非空，则D1中存在唯一的元素x1，<root,x1>∈H,且存在D1上的关系H1属于H；若Dr非空，则Dr中存在唯一的元素xr，<root,xr>∈H,且存在Dr上的关系H1属于H；H={<root,x1>,<root,xr>,H1,H2};
（4）	(D1,{H})是一棵符合本定义的二叉树，称为根的左子树，(Dr,{Hr})是一个符合本定义的二叉树，称为根的右子树。
三、算法思想的描述
1、	创建二叉树：采用递归方法，利用扩展先序，依次读入结点数据，按照先序便历的方式建二叉树，返回头指针；
2、	先、中、后序便历：采用递归方法，先后便历左右子树，在左右子树之前、中间、之后依次打印结点；
3、	计算结点数、叶子数、高度及复制：采用递归方法，按照先序或后序的顺序，实现该功能。计算结点数，依次遍历各结点，计值数加1，返回计值数；计算叶子数，返回左右子树的叶子数之和；计算高度，返回左右子树高度的较大值；复制，在后序遍历各结点时赋值到另一二叉树的相应结点。
4、	计算宽度及层次遍历：函数level,利用先序遍历，使用数组level1[]记录每一层的结点数，用指针的二维数组pl[]分别将各层次的结点的指针放在指针数组的同行;函数widthcsearch，调用函数level，比较level1[10]中的数值，最大值即宽度，依次打印指针二维数组pl[][]所指的结点的值即层次遍历，choice标志被调用程序的功能，0表示计算宽度，1表示层次遍历。
5、	主函数：使用指针数组，实现菜单功能；switch语句，使为实现各功能调用相应的函数。
四、程序结构的描述
1、函数原型及功能
BiTree CreateBiTree1()
	   初始条件：无
操作结果：由计算机终端输入节点值，按照先根次序建立树
void preorder(BiTree bt)
初始条件：二叉树存在
操作结果：先序便历，一个节点只被调用一次
void inorder(BiTree bt)
初始条件：二叉树存在
操作结果：中序便历，一个节点只被调用一次
void postorder(BiTree bt)
初始条件：二叉树存在
操作结果：后序便历，一个节点只被调用一次
int number(BiTree bt)
初始条件：二叉树存在
操作结果：采用递归算法计算树的结点个树，返回结点个树
void leafs(BiTree bt,int &l))
初始条件：二叉树存在
操作结果：采用递归算法计算树的叶子数，返回树的叶子数
int height(BiTree bt)
初始条件：二叉树存在
操作结果：采用递归算法计算树的高度，返回树的高度
void level(BiTree bt, int lev,int i,int level1[10],BiTree pl[][20])
初始条件：二叉树存在
操作结果：利用先序遍历，使用数组level1[]记录每一层的结点数，用指针的二维数组pl[]分别将各层次的结点的指针放在指针数组的同行
void widthcsearch(BiTree bt,int choice)
初始条件：二叉树存在
操作说明与结果：计算宽度和层次遍历
调用函数level
比较level1[10]中的数值，最大值即宽度
依次打印指针二维数组pl[][]所指的结点的值即层次遍历
choice标志被调用程序的功能，0表示计算宽度，1表示层次遍历
BiTree CopyTree(BiTree S)
初始条件：二叉树存在
操作结果：后序便历实现复制，返回头指针
2、本程序包含5个模块：
（1）主程序模块
void main(){
建立树；
 便历树；
 树的计算；
树的复制；
EXIT;
}
（2）	建立树函数——构造树并且返回头指针
（3）	便历树函数——先序、中序、后序层次便历
（4）	树的应用函数——求出树的节点数、叶子数，高度和宽度并且输出结果
（5）	树的复制----将已有的二叉树复制到另一位置
各模块之间的关系：
主程序模块=>建立树函数
主程序模块=>便历树函数
主程序模块=>树的应用函数
	   主程序模块=>树的复制函数
五、调适分析
1、因为数据类型是char，enter键总没处理好，使得程序运行不了。这体现了我的经验不足，也认识到，C语言的掌握是要靠不断练习累积经验的！
2、本程序对预算法函数的分析较好，将函数分为5块，功能不乱
3、建立了菜单按钮，使功能更加清晰了然；
4、算法的时空分析
1）	建立链表时，为一个一个建立，共需n次；执行时，需要对每个节点都便历，时间复杂度为O(n)
2)	  每个结点需要用三个存储单位，空间复杂度为O(n).

	六、测试结果及分析
a)	建立树的输入数据为 abc00de0g00f000
b)	1、先序便历结果是：abcdegf;
c)	中序便历结果是：cbegdfa;
d)	后序便历结果是：cgefdba;
e)	层次便历结果是：abcdefg;
f)	结点数是7；
g)	叶子数是3；
h)	高度是5；
i)	宽度是2；
j)	复制上述二叉树再先序便历的结果是：abcdegf。
分析：实验结果与预期的结果吻合，认为程序编写成功；但因实验测试的数据不多，可能存在些问题不能检查出来。总体可认为实验是成功的。
	
整个程序如下：
typedef struct BiTNode
{
	char     data;
	struct BiTNode   *lchild,*rchild;
}BiTNode,*BiTree;

BiTree CreateBiTree1()
{//递归法利用先序遍历建二叉树
//返回头指针
	char ch;
	BiTree p;
	printf("Please Input The Data:\n");
	scanf("%c",&ch);
	getchar();//消除回车键的影响
	if(ch==' ')
		return NULL；//空子树赋空指针
	p=(BiTree)malloc(sizeof(BiTNode));
	p->data=ch;
	p->lchild=CreateBiTree1();
	p->rchild=CreateBiTree1();
	return p;
}//CreateBiTree1

void preorder(BiTree bt)
{//先序遍历二叉树
	if(!bt)
		return;//递归结束条件
	printf("%c  ",bt->data);//打印结点
	preorder(bt->lchild);
	preorder(bt->rchild);
}//preorder

void inorder(BiTree bt)
{//中序遍历二叉树
	if(!bt)
		return;//递归结束条件
	inorder(bt->lchild);
	printf("%c  ",bt->data);
	inorder(bt->rchild);
}//inorder

void postorder(BiTree bt)
{//后序遍历二叉树
	if(!bt)
		return;//递归结束条件
	postorder(bt->lchild);
	postorder(bt->rchild);
	printf("%c  ",bt->data);
}//postorder

int number(BiTree bt)
{//计算二叉树的结点数，等于左右子树的结点数nl、nr之和
	int nl,nr;
	if(!bt)
		return 0;
	nl=number(bt->lchild);
	nr=number(bt->rchild);
	return 1+nl+nr;
}//number

void leafs(BiTree bt,int &l)
{//计算二叉树的叶子数，等于左右子树的叶子数之和
	if(!bt)
		return;
	if(!bt->lchild&&!bt->rchild)//判断叶子结点的条件
		l++;
	leafs(bt->lchild,l);
	leafs(bt->rchild,l);
	return;
}//leafs

int height(BiTree bt)
{//计算二叉树的高度，高度height取左右子树高度hl、hr的更大值
	int hl,hr,max;
	if(!bt)
		return 0;
	hl=height(bt->lchild);
	hr=height(bt->rchild);
	if(hl>hr)max=hl;
	else max=hr;
	return 1+max;
}//height

void level(BiTree bt, int lev,int i,int level1[10],BiTree pl[][20])
{//利用先序遍历，使用数组level1[]记录每一层的结点数，用指针的二维数组pl[]分别将各层次的结点的指针放在指针数组的同行
	int j=0;
	if(!bt)
		return;
	level1[lev]=i+1;//遇该层次的结点，数组的相应数加1
	while(pl[lev][j])
		j++;//将j移至放该层结点指针的空位置处
	pl[lev][j]=bt;//将结点地址放入j指示的位置
	lev++;//移至下一层
	level(bt->lchild ,lev,level1[lev],level1,pl);
	level(bt->rchild ,lev,level1[lev],level1,pl);
}//level

void widthcsearch(BiTree bt,int choice)
{//计算宽度和层次遍历
//调用函数level
//比较level1[10]中的数值，最大值即宽度
//依次打印指针二维数组pl[][]所指的结点的值即层次遍历
//choice标志被调用程序的功能，0表示计算宽度，1表示层次遍历
	int level1[10],width=0,i,j;
	BiTree pl[10][20];
	if(!bt) 
	{
		printf("空树!\n");
		return;
	}//if
	for(i=0;i<10;i++)
		level1[i]=0;//level[10]赋初值0
	for(i=0;i<10;i++)
		for(j=0;j<20;j++)
			pl[i][j]=NULL;//pl[][]赋初值NULL
	level(bt,0,0,level1,pl);
	if(choice==0)//计算宽度
	{
		for(i=0;i<10;i++)
			if(width<level1[i])
				width=level1[i];
		printf("The width is %d.\n",width);
	}//if
	else if(choice==1)//层次遍历
	{
		for(i=0;pl[i][0]&&i<10;i++)
			for(j=0;pl[i][j]&&j<20;j++)
				printf("%c ",pl[i][j]->data);
	}//else if
}//widthcsearch

BiTree CopyTree(BiTree S)
{//后序便历实现复制，返回头指针
	BiTree T;
	if(!S)
		return NULL;
	else
	{
		BiTree p1,p2;
		p1=CopyTree(S->lchild);
		p2=CopyTree(S->rchild);
		T=(BiTree)malloc(sizeof(BiTNode));
		T->data=S->data;
		T->lchild=p1;
		T->rchild=p2;
	}//else
	return T;
}//CopyTree

void main()
{//使用指针数组存放二叉树的头指针
	BiTree T[11];
	int menu,menu1,menu2,menu3,jn,l=0,h,i,j;
	printf("1 创建二叉树\n2 遍历\n3 计算\n4 复制\n5 EXIT\n请选择:");
	scanf("%d",&menu);
	while(1)
	{
		switch(menu)
		{ 
case(1):
				{ printf("请选择位置(1~10):");
					scanf("%d",&i);
					getchar();
					T[i]=CreateBiTree1();//先序遍历创建二叉树
					break;
				}//case(1)
			case(2):
				{//遍历
					printf("1 先序遍历\n2 中序遍历\n3 后序遍历\n4 层次便历\n请选择:");
					scanf("%d",&menu1);
					printf("请选择要便历的二叉树(1~10):");
					scanf("%d",&i);
					switch(menu1)
					{
					case(1):preorder(T[i]);break;//先序遍历
					case(2):inorder(T[i]);break;//中序遍历
					case(3):postorder(T[i]);break;//后序遍历
					case(4):widthcsearch(T[i],1);break;//层次遍历
					default:return;
					}//switch
					break;
				}//case(2)
			case(3):
				{//计算
					printf("1 结点数\n2 叶子数\n3 二叉树高度\n4 二叉树宽度\n请选择:");
					scanf("%d",&menu2);
					printf("请选择二叉树(1~10):");
					scanf("%d",&i);
					switch(menu2)
					{
					case(1):
						{//计算结点数
							jn=number(T[i]);
							printf("结点数是：%d.\n",jn);
							break;
						}//case(1)
					case(2):
						{//计算叶子数
							leafs(T[i],l);
							printf("叶子数是：%d.\n",l);
							break;
						}//case(2)
					case(3):
						{//计算高度
							h=height(T[i]);
							printf("The height is %d.\n",h+);
							break;
						}//case(3)
					case(4):
						{//计算宽度
							widthcsearch(T[i],0);
							break;
						}//case(4)
					default:return;
					}//switch
					break;
				}//case(3)
				case(4):
					{//复制
						printf("请选择二叉树及位置(1~10):");
						scanf("%d,%d",&i,&j);
						T[j]=CopyTree(T[i]);
						break;
					}//case(4)
				case(5):return;//EXIT
				default:return;
		}//switch
	printf("\n1 创建二叉树\n2 遍历\n3 计算\n4 复制\n5 EXIT\n请选择:");
	scanf("%d",&menu);
	}//while
}//main