bitree.cpp

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

#include"stdio.h"
#include"stdlib.h"
#include"malloc.h"
#define Maxsize 100
#define STACKINCREMENT 10
#define STACK_INIT_SIZE 100
#define OVERFLOW 0
#define OK 1
#define error 0

typedef  struct  BiTNode
{
   char data ;
   struct  BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

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(")");
		}
	}
}
int visit(BiTree T)
{
	if(T)
	{
		printf("%c",T->data);
		return 0;
	}
	else return 1;
}

void PreorderTraverse(BiTree T)
{// 先序遍历以T为根指针的二叉树
	if(T)
	{// T=NULL时，二叉树为空树，不做任何操作
		visit(T); // 通过函数指针 *visit 访问根结点
		PreorderTraverse(T->lchild);// 先序遍历左子树
		PreorderTraverse(T->rchild);// 先序遍历右子树
	}
}
void InOrderTraverse(BiTree T)
{
	if (T)
	{
		InOrderTraverse(T->lchild);// 先序遍历左子树
		visit(T);
		InOrderTraverse(T->rchild);
	}
}

void PostOrderTraverse(BiTree T)
{
	if (T)
	{
		PostOrderTraverse(T->lchild);// 先序遍历左子树
		PostOrderTraverse(T->rchild);
		visit(T);
	}
}

void main()
{
	FILE *fp;
	//sqstack s;
	BiTree T,p = NULL;
	//InitStack(&s);
	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");
	printf("先序遍历请按1，中序遍历请按2，后序遍历请按3，退出遍历请按#:");
	e = getchar();
	getchar();
	printf("\n");
	while(e != '#')
	{
		switch(e)
		{
		case '1':PreorderTraverse(T);
				 printf("\n\n");
				 break;
		case '2':InOrderTraverse(T);
				 printf("\n\n");
				 break;
		case '3':PostOrderTraverse(T);
				 printf("\n\n");
				 break;
		}
		printf("先序遍历请按1，中序遍历请按2，后序遍历请按3，退出遍历请按#:");
		e = getchar();
		getchar();
		printf("\n");
	}
	fclose(fp);//关闭文件
	printf("\n");
    printf("☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n");
}