tree.c

演示二叉树的生成及一些常用操作； 包括插入节点

//线索二叉树
#include<stdio.h>
#include<stdlib.h>

#define ERROR 0
#define OK 1
#define QSIZE 5							//定义按层遍历里队列的最大长度,因为同一时刻,队里最多只有四个元素所以只需五个空间					
#define TSIZE 100						//栈的最大容量(树结点的最大个数)

typedef char EType;

typedef struct T_BiTree{
	EType Data;
	struct T_BiTree *LCh;
	char Ltag;
	struct T_BiTree *RCh;
	char Rtag;
}TNode;

void MenusPrint();                      // 打印菜单
void CreateBiTree(TNode **T);
void FreeBiTree(TNode **T);				//释放树的空间
int Leaf(TNode *T);						//求树的叶子的数目
int Heigh(TNode *T);					//求树的高度
void Print(EType value);				//打印一个字符(树的结点元素)
void PreOrderprint(TNode *T, void (*visit)(EType value));		//先序(因为树为先序创建)打印树
void InOrderThreading(TNode *T);								//调用InThreading对树做中序遍历的线索化
void InThreading(TNode *T, TNode **prev);						//中序遍历的线索化
void InOrderTraverse(TNode *T, void (*visit)(EType value));		//中序遍历	
void PreOrderThreading(TNode *T);								//调用PreThreading对树做先序遍历的线索化
void PreThreading(TNode *T, TNode **prev);						//先序遍历的线索化
void PreOrderTraverse(TNode *T, void (*visit)(EType value));	//先序遍历	
void PosOrderThreading(TNode *T);								//调用PosThreading对树做后序遍历的线索化
void PosThreading(TNode *T, TNode **prev);						//后序遍历线索化
void PosOrderTraverse(TNode *T);								//后序遍历
void DeleteThreading(TNode *T);									//删除原有线索,以便进行新的线索化
void LevelOrderTraverse(TNode *T);								//按层遍历
TNode *CreateBTree(char *s, int *idx);							//用先序打印的格式输入( 如A(B(D,),C(E,F)) )创建树

void main()
{
	int choice = -1, num , i;
	char str[100] = {0};
	TNode *T = NULL;

	printf("Read the menus below and input your choice.\n");

	while (choice){
		MenusPrint();
		printf("Your choice is : ");
		scanf("%d",&choice);
		switch (choice){
		case 1:
			if (T != NULL)	FreeBiTree(&T);
			printf("Input a string to create a tree.--blank\" \" to end\n");
			scanf("\n");
			CreateBiTree(&T);
			printf("The tree your create right now is :\n");
			PreOrderprint(T, Print);
			break;

		case 2:
			num = Leaf(T);
			printf("The number of the tree's leaves are : %d\n",num);
			break;

		case 3:
			num = Heigh(T);
			printf("The heigh of the tree is : %d\n",num);
			break;

		case 4:
			DeleteThreading(T);
			PreOrderThreading(T);
			printf("(Preorder)The tree is :\n");
			PreOrderTraverse(T, Print);
			break;

		case 5:
			DeleteThreading(T);
			InOrderThreading(T);
			printf("(Inorder)The tree is :\n");
			InOrderTraverse(T, Print);
			break;

		case 6:
			DeleteThreading(T);
			PosOrderThreading(T);
			printf("(Posorder)The tree is :\n");
			PosOrderTraverse(T);
			break;

		case 7:
			DeleteThreading(T);
			printf("(Levelorder)The tree is :\n");
			LevelOrderTraverse(T);
			break;

		case 8:
			DeleteThreading(T);
			printf("\nThe threading of the tree has been deleted");
			break;

		case 9:
			FreeBiTree(&T);
			printf("\nThe tree has been deleted");
			break;

		case 10:
			FreeBiTree(&T);
			printf("please input a string as \"a(b(d,),c(e,f))\" to create a tree.\n");
			scanf("\n");
			gets(str);
			i = 0;
			T = CreateBTree(str, &i);
			printf("The tree your create right now is :\n");
			PreOrderprint(T, Print);
			break;

		case 0:
			if (T != NULL)	FreeBiTree(&T);
			break;

		default:
			printf("Error input!");
			break;
		}
		printf("\n\n");
	}
}

void MenusPrint()                       // 打印菜单
{
	printf("1:Create a tree by a string.\n");
	printf("2:Get the number of the tree's leaves.\n");
	printf("3:Get the heigh of the tree.\n");                       
    printf("4:Preorder threading the tree and Preorder traverse it.\n"); 
	printf("5:Inorder threading the tree and Inorder traverse it.\n");
    printf("6:Posorder threading the tree and Posorder traverse it.\n");
	printf("7:Levelorder traverse the tree.\n");
	printf("8:Delete the threading of the tree.\n");
	printf("9:Delete the tree.\n");
	printf("10:Preorder create the tree (Input as\"a(b(d,),c(e,f))...\")\n");
	printf("0:Exit\n");
}

void CreateBiTree(TNode **T)
{
	EType ch;
	TNode *pt;

	scanf("%c",&ch);					//输入字符

	if (ch == ' ')	*T = NULL;			//空字符控制左孩子的结束或右孩子的结束

	else{
		pt = (TNode*)calloc(1,sizeof(TNode));
		pt->Data = ch;					

		CreateBiTree(&(pt->LCh));		//创建左孩子
		CreateBiTree(&(pt->RCh));		//创建右孩子

		*T = pt;
	}
}

int Leaf(TNode *T)						//求树的叶子数
{
	if (T == NULL)	return 0;			//空树,没有叶子

	if (T->LCh == NULL && T->RCh == NULL)	return 1;		//只有一个根结点

	return Leaf(T->LCh) + Leaf(T->RCh);
}

int Heigh(TNode *T)						//求树高
{
	if (T == NULL)	return 0;			//空树,树高为零

	if (T->LCh == NULL && T->RCh == NULL)	return 1;		//只有一个根结点,树高1

	return 1 + max(Heigh(T->LCh), Heigh(T->RCh));			//树高为左,右子树中树高的最大值加1
}

void Print(EType value)
{
	printf("%c",value);
}
void PreOrderprint(TNode *T, void (*visit)(EType value))	//先序打印树
{
	if (T == NULL)	return;				//空树,直接返回

	if (T->LCh == NULL && T->RCh == NULL)	visit(T->Data);	//只有根结点,直接打印

	else{								
		visit(T->Data);					//否则,先打印根结点
		printf("(");					//打印左括号
		PreOrderprint(T->LCh, visit);	//打印左子树
		printf(",");					//打印逗号
		PreOrderprint(T->RCh, visit);	//打印右子树
		printf(")");					//打印右括号
	}	
}

void InOrderThreading(TNode *T)			//中序线索化	
{
	TNode *prev = NULL;

	if (T == NULL)	return;				//树空,直接返回			

	InThreading(T, &prev);				//中序线索化

	if (T->RCh == NULL)	T->Rtag =1;		//若右子树为空,根为最后一个输出的元素,没有后继,只需把Rtag改为1
}

void InThreading(TNode *T, TNode **prev)
{
	if (T == NULL)	return;				//树空,直接返回

	InThreading(T->LCh, prev);			//左子树线索化
	if (T->LCh == NULL){				//用空指针建立前驱
		T->Ltag = 1;
		T->LCh = *prev;
	}

	if (*prev != NULL && (*prev)->RCh == NULL){				//用空指针建立后继
		(*prev)->Rtag = 1;
		(*prev)->RCh = T;
	}

	*prev = T;

	InThreading(T->RCh, prev);			//右子树线索化
}

void InOrderTraverse(TNode *T, void (*visit)(EType value))	//中序遍历
{
	TNode *pt;

	pt = T;								//pt开始指向根结点

	while (pt != NULL){					
		while (pt->Ltag == 0)	pt = pt->LCh;				//找到最左边的叶子结点(中序遍历第一个访问的元素)

		visit(pt->Data);
		printf(" ");

		while (pt->Rtag == 1 && pt->RCh != NULL){			//若右孩子存的是后继,通过后继找到下一个要访问的结点
			pt = pt->RCh;
			visit(pt->Data);
			printf(" ");
		}

		pt = pt->RCh;					//若存的不是后继,则重新找到右孩子的最左边的叶子结点
	}
}

void PreOrderThreading(TNode *T)		//先序线索化
{
	TNode *prev = NULL;

	if (T == NULL)	return;

	PreThreading(T, &prev);
	prev->Rtag = 1;						//通过prev找到最后访问的一个结点,把其线索化

}

void PreThreading(TNode *T, TNode **prev)
{
	if (T == NULL)	return;				//空树,直接返回

	if (T->LCh == NULL){				//建立前驱
		T->Ltag = 1;
		T->LCh = *prev;
	}

	if (*prev != NULL && (*prev)->RCh == NULL){				//建立后继
		(*prev)->Rtag = 1;
		(*prev)->RCh = T;
	}

	*prev = T;

	if (T->Ltag == 0)	PreThreading(T->LCh, prev);			//左子树线索化
	if (T->Rtag == 0)	PreThreading(T->RCh, prev);			//右子树线索化
}

void PreOrderTraverse(TNode *T, void (*visit)(EType value))	//先序遍历
{
	TNode *pt;

	pt = T;								//pt开始指向树根
	while (pt != NULL){
		visit(pt->Data);				//访问结点
		printf(" ");

		if (pt->Ltag == 0)	pt = pt->LCh;					//左孩子原来不空,则通过左孩子找到直接后继
		else	pt = pt->RCh;								//否则通过右孩子找到直接后继
	}
}

void PosOrderThreading(TNode *T)		//后序线索化
{
	TNode *prev = NULL;

	if (T == NULL) return;
	PosThreading(T, &prev);				
	if (T->RCh == NULL)	T->Rtag = 1;	//若没有右子树,则根为最后一个访问的结点,没有后继,只需改Rtag为1
}

void PosThreading(TNode *T, TNode **prev)
{
	if (T == NULL) return;

	PosThreading(T->LCh, prev);			//左子树的线索化
	PosThreading(T->RCh, prev);			//右子树的线索化

	if (T->LCh == NULL){				//建立前驱
		T->Ltag = 1;					
		T->LCh = *prev;
	}

	if (*prev != NULL && (*prev)->RCh == NULL){				//建立后继
		(*prev)->Rtag = 1;
		(*prev)->RCh = T;
	}

	*prev = T;
}

void PosOrderTraverse(TNode *T)			//利用栈实现后序遍历
{
	TNode *pt;
	EType Stack[TSIZE];					//为栈申请空间
	int top = -1;						//栈的初始化

	pt = T;
	while (pt != NULL){
		Stack[++top] = pt->Data;		//压栈
		
		if (pt->Rtag == 0)	pt = pt->RCh;					//右孩子原来不空,通过右孩子可找到直接前驱
		else	pt = pt->LCh;								//否则通过左孩子找直接前驱
	}

	while (top > -1)	printf("%c ",Stack[top--]);			//出栈
}

void DeleteThreading(TNode *T)			//删除线索
{
	if (T == NULL)	return;

	if (T->Ltag == 1){					//删除前驱
		T->Ltag = 0;
		T->LCh = NULL;
	}

	if (T->Rtag == 1){					//删除后继
		T->Rtag = 0;
		T->RCh = NULL;
	}

	DeleteThreading(T->LCh);			//删除左子树的线索
	DeleteThreading(T->RCh);			//删除右子树的线索
}

void LevelOrderTraverse(TNode *T)		//利用队列实现按层遍历
{
	TNode *Queue[QSIZE];				//为队列申请空间
	int front, real;

	if (T == NULL)	return;

	front = real = 0;					//队列的初始化

	Queue[real] = T;					//根进队
	real = (real + 1) % QSIZE;

	while (front != real){
		if (Queue[front]->LCh){			//左孩子进队
			Queue[real] = Queue[front]->LCh;
			real = (real + 1) % QSIZE;
		}

		if (Queue[front]->RCh){			//右孩子进队
			Queue[real] = Queue[front]->RCh;
			real = (real + 1) % QSIZE;
		}

		printf("%c ",Queue[front]->Data);//出队
		front = (front + 1) % QSIZE;
	}
}

void FreeBiTree(TNode **T)
{
	if (*T == NULL) return;

	if ((*T)->Ltag == 0 && (*T)->LCh != NULL)	FreeBiTree(&((*T)->LCh));	//左子树不空,释放左子树
	if ((*T)->Rtag == 0 && (*T)->RCh != NULL)	FreeBiTree(&((*T)->RCh));	//右子树不空,释放右子树

	free(*T);							//释放根结点
	*T = NULL;							//把根赋空
}

TNode *CreateBTree(char *s, int *idx)	//用先序打印的格式输入( 如A(B(D,),C(E,F)) )创建树
{
	int i;
	TNode *T = NULL;

	i = *idx;
	if (s[i] == 0)	return T;			//空串,返回

	if (s[i] == ','){					
		if (s[i-1] == '(')	*idx = i+1;	//','前面是'(',则当前创建的是子树根的左子树,且左子树空右子树不空,故后挪一字符继续创建右子树
		return T;						//','前面不是'(',则当前创建的是叶子,左右子树都为空,应该返回
	}

	if (s[i] == ')'){					//当前创建根的是左子树,右括好后面不是空就根的右子树,得后挪字符继续创建
		*idx = i+1;
		return T;
	}

	T = (TNode*)calloc(1,sizeof(TNode));//申请存当前的根
	T->Data = s[i];
	i++;								//后挪字符

	if (s[i] == '(')	i++;			//左括号,表示左孩子或右孩子不空
	
	T->LCh = CreateBTree(s, &i);		//创建左孩子
	T->RCh = CreateBTree(s, &i);		//创建右孩子

	*idx = i+1;
	return T;
}