bitree.cpp

这是一系列关于二叉树的创建,查找,霍夫曼等数据结构编程,

#include"stdio.h"
#include"stdlib.h"
#include"malloc.h"
#define Maxsize 100
#define OK 1
#define error 0

typedef  struct  BiTNode
{
   char data ;
   struct  BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
int count = 0,record = 1;
void Create_BiTree(BiTree &T,FILE *fp)
{//用一个数组记录根结点以方便回朔，循环读取文件中的广义表字母建起链式存储结构的二叉树
	BiTree Point[Maxsize];//记录根结点
	BiTree p;
	char ch;
	int root=-1,k;
	T=NULL;
	ch=fgetc(fp);

	while(ch != EOF)
	{
		if(ch == '('||ch == ')'||ch == ',')
		{
			if(ch == '(')
				 {
					 root++;
					Point[root] = p;
					k = 1;//k = 1表示下一个结点将是该结点的左右孩子
				 }
	
				if(ch == ')')	root--;//遇到‘）’回朔到根结点
				
		
				if(ch == ',')	k = 2;//k = 2表示下一个结点将是该结点的左右孩子
		}
		
		else
		{
			p = (BiTNode *)malloc(sizeof(BiTNode));
					p->data=ch;
					p->lchild = p->rchild = NULL;
					if(T == NULL)//如果是根结点，创建根结点
					T = p;
				else//否则将孩子结点与根结点连接起来
				{
					switch(k)
					{
						case 1:
							Point[root]->lchild = p;
							break;
						case 2:
							Point[root]->rchild = p;
							break;
					}
				}
		}
		ch = fgetc(fp);
	}
}
void Display_BiTree(BiTree T)
{//显示二叉树T
	if(T!=NULL)
	{//如果T不为空则显示结点值
		printf("%c",T->data);
		if(T->lchild||T->rchild)
		{
			printf("(");
			Display_BiTree(T->lchild);//递归调用左孩子
			if(T->rchild!=NULL)
				printf(",");
			Display_BiTree(T->rchild);//递归调用右孩子
			printf(")");
		}
	}
}
void Count_Leaf(BiTree T)
{//先序遍历二叉树，以 count 返回二叉树中叶子结点的数目
	if(T)
	{
		if((!(T->lchild)) && (!(T->rchild)))
			count++;//对叶子结点计数
		Count_Leaf(T->lchild);
		Count_Leaf(T->rchild);
	}
} 

void BiTree_Depth(BiTree T,int level,int &depth)
{// T指向二叉树的根，level 为 T 所指结点所在层次， 　
 // 其初值为1，depth 为当前求得的最大层次,其初值为0
	if(T)
	{
		if(level > depth)
			depth = level;
		BiTree_Depth(T->lchild,level + 1,depth);
		BiTree_Depth(T->rchild,level + 1,depth);
	}// if
}// BiTree_Depth

void Locate(BiTree T,char e,BiTree &p)
{// 若二叉树 T 中存在和 x 相同的元素，
 // 则 p 指向该结点，显示与所给结点匹配结点的孩子结点
	if(T)
	{
		if(T->data == e)
		{
			p = T;
			if(p)
			{
				
				if(p->lchild || p->rchild)
				{
					if(p->lchild)
						printf("第%d个%c 的左孩子结点为：%c\n",record,e,p->lchild->data);
					else 
						printf("第%d个%c结点无左孩子结点\n",record,e);
					if(p->rchild)
						printf("第%d个%c 的右孩子结点为：%c\n",record,e,p->rchild->data);
					else 
						printf("第%d个%c结点无右孩子结点\n",record,e);
				}

				else
					printf("第%d个%c结点无孩子结点\n",record,e);
			}
			else
				printf("找不到%c结点\n",e);
			record++;
		}
		Locate(T->lchild,e,p);
		Locate(T->rchild,e,p);
	}
}

void main()
{
	int level = 1,depth = 0;
	FILE *fp;
	BiTree T,p = NULL;
	char e;
	printf("\n\n");
	printf("☆☆☆☆☆☆☆☆☆☆☆☆☆☆二叉树基本操作实验☆☆☆☆☆☆☆☆☆☆☆☆\n\n");
	fp = fopen("广义表.txt","r+");
	printf("根据下列广义表建立二叉树：");
	while(!feof(fp)) 
		putchar(fgetc(fp));//显示广义表
	printf("\n\n");
	rewind(fp);//使fp1重新指向文件的开头
	Create_BiTree(T,fp);
	printf("所建二叉树为：\n");
	Display_BiTree(T);//显示二叉树
	printf("\n\n");
	Count_Leaf (T);//查找叶子结点
	printf("所建二叉树的叶子结点的个数为: %d\n\n",count);
	BiTree_Depth(T,level,depth);//计算二叉树的深度
	printf("所建二叉树的深度为: %d\n\n",depth);
	printf("如果你想退出查询结点就输入#,否则请输入要查找的双亲结点（仅限于C,O,M,U,P,T,E,R,S,O,F,T,A,R,W,E）:");
	e = getchar();
	getchar();
	printf("\n");
	while(e != '#')
	{
		Locate(T,e,p);//显示与所给结点匹配结点的孩子结点
		printf("\n");
	    record = 1;
		printf("如果你想退出查询结点就输入#,否则请输入要查找的双亲结点（仅限于C,O,M,U,P,T,E,R,S,O,F,T,A,R,W,E）:");
		e = getchar();
		getchar();
		printf("\n");
	}
	fclose(fp);//关闭文件
	printf("\n");
    printf("☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
}