C_树(ADT)-树的表示和实现

程序员文章站 2024-02-27 12:36:33

...

二叉树的定义：

二叉树是一种树型结构，它的特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。

C_树(ADT)-树的表示和实现

相关术语：

节点的度：一个节点含有的子树的个数称为该节点的度；

叶节点或终端节点：度为0的节点称为叶节点；

非终端节点或分支节点：度不为0的节点；

双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；

孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；

兄弟节点：具有相同父节点的节点互称为兄弟节点；

树的度：一棵树中，最大的节点的度称为树的度；

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

树的高度或深度：树中节点的最大层次；

堂兄弟节点：双亲在同一层的节点互为堂兄弟；

节点的祖先：从根到该节点所经分支上的所有节点；

子孙：以某节点为根的子树中任一节点都称为该节点的子孙。

森林：由m（m>=0）棵互不相交的树的集合称为森林；

(相关术语来自百度百科)

二叉树的顺序存储结构

struct position{
	int level;		//结点的层 
	int order; 		//本层序号 
};

二叉树基本操作函数定义

/*构造空的二叉树T。*/
void InitBiTree(SqBiTree T)

/*按层序次序输入二叉树中结点的值，构造顺序存储的二叉树T。*/
void CreateBiTree(SqBiTree T)

/*初始条件：二叉树T存在。*/
/*操作结果：若二叉树T为空二叉树，则返回TRUE；否则返回FALSE。*/
Status BiTreeEmpty(SqBiTree T)

/*初始条件：二叉树T存在。*/
/*操作结果：返回树T的深度。*/ 
int BiTreeDepth(SqBiTree T)

/*初始条件：二叉树存在。*/
/*操作结果：当T不为空，用e返回T的根，返回OK；否则返回ERROR，e无定义。*/
Status Root(SqBiTree T,TElemType &e)

/*初始条件：二叉树存在，e是T中某个结点的位置。*/
/*操作结果：返回处于位置e层，本层序号的结点的值。*/
TElemType Value(SqBiTree T,position e)

/*初始条件：二叉树存在，e是T中某个结点的位置。*/
/*操作结果：给处于位置e层，本层序号的结点赋新值value。*/
Status Assign(SqBiTree T,position e,TElemType value)

/*初始条件：二叉树T存在，e是T中某个结点。*/
/*操作结果：若e是T的非根结点，则返回它的双亲；否则返回空。*/ 
TElemType Parent(SqBiTree T,TElemType e)


/*初始条件：二叉树T存在,e是树T中的某个结点。*/
/*操作结果：返回e的左孩子。若e无左孩子，则返回"空"。*/
TElemType LeftChild(SqBiTree T,TElemType e)

/*初始条件：二叉树T存在,e是树T中的某个结点。*/
/*操作结果：返回e的右孩子。若e无右孩子，则返回"空"。*/
TElemType RightChild(SqBiTree T,TElemType e)

/*初始条件：二叉树T存在，e是T中某个结点。*/
/*操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回"空"。*/
TElemType LeftSibling(SqBiTree T,TElemType e)

/*初始条件：二叉树T存在，e是T中某个结点。*/
/*操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回"空"。*/
TElemType RightSibling(SqBiTree T,TElemType e)

/*初始条件：二叉树T存在。*/
/*把从q的j结点开始的子树移为从T的i结点开始的子树。*/
void Move(SqBiTree q,int j,SqBiTree T,int i)

/*初始条件：二叉树存在，p是T中某个结点的值，LR为0或1，非空二叉树c与T不相交且右子树为空。*/
/*操作结果：根据LR为0或1，插入c为T中p结点的左或右子树,p结点的原有左或右子树则为c的右子树。*/ 
void InserChild(SqBiTree T,TElemType p,int LR,SqBiTree c)

/*初始条件：二叉树T存在，Visit是对结点操作的应用函数。*/
/*操作结果：层序遍历二叉树*/
void LevelOrderTraverse(SqBiTree T,void(*Visit)(TElemType))

二叉树函数定义基本实现:

·在i层结点的序号从pow(2,i-1)-1到pow(2,i)-2；

·序号为i的结点，其双亲序号为(i+1)/2-1,其左右孩子序号分别为2i+1和2i+2；

·除了根节点，序号为奇数的结点是其双亲的左孩子，它的右兄弟的序号是它的序号+1；

·除了根节点，序号为偶数的结点是其双亲的右孩子，它的左兄弟的序号是它的序号-1；

·i层的满二叉树，其结点总数为pow(2,i)-1

(1)构造空的二叉树T

/*构造空的二叉树T。*/
void InitBiTree(SqBiTree T)
{
	int i;
	for(i=0;i<MAX_TREE_SIZE;i++)
		T[i]=0;
}

在顺序存储结构中，二叉树的清空与销毁和构造空二叉树函数完全一样。

(2)输入二叉树中结点的值，构造顺序存储的二叉树T

/*按层序次序输入二叉树中结点的值，构造顺序存储的二叉树T。*/
void CreateBiTree(SqBiTree T)
{
	int i=0;
	InitBiTree(T);		//构造空二叉树T
	printf("请按层序输入结点的值，0表示空结点，输入999表示结束：\n");
	while(1)
	{
		scanf("%d",&T[i]);
		if(T[i]==999)
		{
			T[i]=0;
			break;
		}
		i++;
	}
	for(i=1;i<MAX_TREE_SIZE;i++)
		if(i!=0&&T[(i+1)/2-1]==0&&T[i]!=0)		//此结点无双亲且不是根节点
		{
			printf("出现无双亲的非根结点，程序退出!\n");
			exit(0);
		}
}

(3)判断二叉树是否为空树

/*初始条件：二叉树T存在。*/
/*操作结果：若二叉树T为空二叉树，则返回TRUE；否则返回FALSE。*/
Status BiTreeEmpty(SqBiTree T)
{
	if(T[0]==0)		//根结点为空则为空
		return TRUE;
	else
		return FALSE; 
}

(4)返回二叉树深度

/*初始条件：二叉树T存在。*/
/*操作结果：返回树T的深度。*/ 
int BiTreeDepth(SqBiTree T)
{
	int i;
	int j=-1;
	for(i=MAX_TREE_SIZE-1;i>=0;i--)			//找到最后一个结点
		if(T[i]!=0)
			break;
	i++;	//为了便于计算
	do
		j++;
	while(i>=pow(2,j));
		return j; 
}

(5)返回二叉树的根

/*初始条件：二叉树存在。*/
/*操作结果：当T不为空，用e返回T的根，返回OK；否则返回ERROR，e无定义。*/
Status Root(SqBiTree T,TElemType &e)
{
	if(BiTreeEmpty(T))			//二叉树为空树
	{
		return ERROR;
	}else{
		e=T[0];
		return OK;
	} 
}

(6)返回二叉树中某个结点位置

/*初始条件：二叉树存在，e是T中某个结点的位置。*/
/*操作结果：返回处于位置e层，本层序号的结点的值。*/
TElemType Value(SqBiTree T,position e)
{
	return T[int(pow(2,e.level-1)+e.order-2)];
}

(7)二叉树中某个结点赋新值

/*初始条件：二叉树存在，e是T中某个结点的位置。*/
/*操作结果：给处于位置e层，本层序号的结点赋新值value。*/
Status Assign(SqBiTree T,position e,TElemType value)
{
	int i=pow(2,e.level-1)+e.order-2;		//将层、本层序号转为矩阵的序号
	if(value!=0&&(T[(i+1)/2-1]==0))			//给叶子赋非空值但双亲为空
		return ERROR;
	else if(value==0&&(T[i*2+1]!=0||T[i*2+2]!=0))	//给双亲赋空值但有叶子(不空) 
		return ERROR;
	T[i]=value;
	return OK;
}

(8)返回结点双亲

/*初始条件：二叉树T存在，e是T中某个结点。*/
/*操作结果：若e是T的非根结点，则返回它的双亲；否则返回空。*/ 
TElemType Parent(SqBiTree T,TElemType e)
{
	int i;
	if(T[0]==0)			//空树
		return  0;
	for(i=1;i<=MAX_TREE_SIZE-1;i++)
		if(T[i]==e)		//找到e
			return T[(i+1)/2-1];
			
	return 0;		//没有找到e 
}

(9)返回结点孩子

返回左孩子

/*初始条件：二叉树T存在,e是树T中的某个结点。*/
/*操作结果：返回e的左孩子。若e无左孩子，则返回"空"。*/
TElemType LeftChild(SqBiTree T,TElemType e)
{
	int i;
	if(T[0]==0)			//空树
		return 0;
	for(i=0;i<=MAX_TREE_SIZE-1;i++)
		if(T[i]==e)		//找到e
			return T[i*2+1];
		return 0;
}

返回右孩子

/*初始条件：二叉树T存在,e是树T中的某个结点。*/
/*操作结果：返回e的右孩子。若e无右孩子，则返回"空"。*/
TElemType RightChild(SqBiTree T,TElemType e)
{
	int i;
	if(T[0]==0)			//空树
		return 0;
	for(i=0;i<=MAX_TREE_SIZE;i++)
		if(T[i]==e)		//找到e
			return T[i*2+2];
	return 0;			//没有找到 
}

(10)返回结点兄弟

返回左兄弟

/*初始条件：二叉树T存在，e是T中某个结点。*/
/*操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回"空"。*/
TElemType LeftSibling(SqBiTree T,TElemType e)
{
	int i;
	if(T[0]==0)			//空树
		return 0;
	for(i=1;i<=MAX_TREE_SIZE-1;i++)
		if(T[i]==e&&i%2==0)		//找到e且其序号为偶数是右孩子
			return T[i-1];
	return 0;			//没找到e 
}

返回右兄弟

/*初始条件：二叉树T存在，e是T中某个结点。*/
/*操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回"空"。*/
TElemType RightSibling(SqBiTree T,TElemType e)
{
	int i;
	if(T[0]==0)		//空树
		return 0;
	for(i=1;i<=MAX_TREE_SIZE-1;i++)
		if(T[i]==e&&i%2)		//找到e且其序号为奇数做孩子
			return T[i+1];
	return 0;			//没找到e 
}

(11)对子树的操作

/*初始条件：二叉树T存在。*/
/*把从q的j结点开始的子树移为从T的i结点开始的子树。*/
void Move(SqBiTree q,int j,SqBiTree T,int i)
{
	if(q[2*j+1]!=0)		//q的左子树不空
		Move(q,(2*j+1),T,(2*i+1));		//把q的j结点的左子树移为T的i结点的左子树
	if(q[2*j+2]!=0)		//q的右子树不空
		Move(q,(2*j+2),T,(2*i+2));		//把q的j结点右子树移为T的i结点的右子树 
	T[i]=q[j];			//把q的j结点移为T的i结点
	q[j]=0; 
}

(12)插入原有左右子树

/*初始条件：二叉树存在，p是T中某个结点的值，LR为0或1，非空二叉树c与T不相交且右子树为空。*/
/*操作结果：根据LR为0或1，插入c为T中p结点的左或右子树,p结点的原有左或右子树则为c的右子树。*/ 
void InserChild(SqBiTree T,TElemType p,int LR,SqBiTree c)
{
	int j,k,i=0;
	for(j=0;j<int(pow(2,BiTreeDepth(T)))-1;j++)		//查找p的序号
		if(T[j]==p)			//j为p的序号
			break;
	
	k=2*j+1+LR;				//k为p的左或右孩子的序号
	if(T[k]!=0)
		Move(T,k,T,2*k+2);		//把从T的k结点开始的子树移为从k结点的右子树开始的子树
	Move(c,i,T,k); 
}

(13)层次遍历二叉树

/*初始条件：二叉树T存在，Visit是对结点操作的应用函数。*/
/*操作结果：层序遍历二叉树*/
void LevelOrderTraverse(SqBiTree T,void(*Visit)(TElemType))
{
	int j;
	int i=MAX_TREE_SIZE-1;
	while(T[i]==0)
		i--;
	for(j=0;j<=i;j++)		//从根结点起，按层序遍历二叉树
		if(T[j]!=0)
			Visit(T[j]);		//只遍历非空的结点	
	printf("\n"); 
}

嗯下面就是在VC中测试

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAX_TREE_SIZE 100
#define ClearBiTree InitBiTree		//顺序存储结构中，两函数完全一样
#define DestroyBiTree InitBiTree	//顺序存储结构中，两函数完全一样 
typedef int TElemType;
typedef int Status;
typedef TElemType SqBiTree[MAX_TREE_SIZE];
struct position{
	int level;		//结点的层 
	int order; 		//本层序号 
};

void visit(TElemType e)
{
	printf("%d \n",e);
}

/*构造空的二叉树T。*/
void InitBiTree(SqBiTree T)
{
	int i;
	for(i=0;i<MAX_TREE_SIZE;i++)
		T[i]=0;
}

/*按层序次序输入二叉树中结点的值，构造顺序存储的二叉树T。*/
void CreateBiTree(SqBiTree T)
{
	int i=0;
	InitBiTree(T);		//构造空二叉树T
	printf("请按层序输入结点的值，0表示空结点，输入999表示结束：\n");
	while(1)
	{
		scanf("%d",&T[i]);
		if(T[i]==999)
		{
			T[i]=0;
			break;
		}
		i++;
	}
	for(i=1;i<MAX_TREE_SIZE;i++)
		if(i!=0&&T[(i+1)/2-1]==0&&T[i]!=0)		//此结点无双亲且不是根节点
		{
			printf("出现无双亲的非根结点，程序退出!\n");
			exit(0);
		}
} 

/*初始条件：二叉树T存在。*/
/*操作结果：若二叉树T为空二叉树，则返回TRUE；否则返回FALSE。*/
Status BiTreeEmpty(SqBiTree T)
{
	if(T[0]==0)		//根结点为空则为空
		return TRUE;
	else
		return FALSE; 
}
 
/*初始条件：二叉树T存在。*/
/*操作结果：返回树T的深度。*/ 
int BiTreeDepth(SqBiTree T)
{
	int i;
	int j=-1;
	for(i=MAX_TREE_SIZE-1;i>=0;i--)			//找到最后一个结点
		if(T[i]!=0)
			break;
	i++;	//为了便于计算
	do
		j++;
	while(i>=pow(2,j));
		return j; 
}

/*初始条件：二叉树存在。*/
/*操作结果：当T不为空，用e返回T的根，返回OK；否则返回ERROR，e无定义。*/
Status Root(SqBiTree T,TElemType &e)
{
	if(BiTreeEmpty(T))			//二叉树为空树
	{
		return ERROR;
	}else{
		e=T[0];
		return OK;
	} 
} 

/*初始条件：二叉树存在，e是T中某个结点的位置。*/
/*操作结果：返回处于位置e层，本层序号的结点的值。*/
TElemType Value(SqBiTree T,position e)
{
	return T[int(pow(2,e.level-1)+e.order-2)];
} 

/*初始条件：二叉树存在，e是T中某个结点的位置。*/
/*操作结果：给处于位置e层，本层序号的结点赋新值value。*/
Status Assign(SqBiTree T,position e,TElemType value)
{
	int i=pow(2,e.level-1)+e.order-2;		//将层、本层序号转为矩阵的序号
	if(value!=0&&(T[(i+1)/2-1]==0))			//给叶子赋非空值但双亲为空
		return ERROR;
	else if(value==0&&(T[i*2+1]!=0||T[i*2+2]!=0))	//给双亲赋空值但有叶子(不空) 
		return ERROR;
	T[i]=value;
	return OK;
}

/*初始条件：二叉树T存在，e是T中某个结点。*/
/*操作结果：若e是T的非根结点，则返回它的双亲；否则返回空。*/ 
TElemType Parent(SqBiTree T,TElemType e)
{
	int i;
	if(T[0]==0)			//空树
		return  0;
	for(i=1;i<=MAX_TREE_SIZE-1;i++)
		if(T[i]==e)		//找到e
			return T[(i+1)/2-1];
			
	return 0;		//没有找到e 
} 

/*初始条件：二叉树T存在,e是树T中的某个结点。*/
/*操作结果：返回e的左孩子。若e无左孩子，则返回"空"。*/
TElemType LeftChild(SqBiTree T,TElemType e)
{
	int i;
	if(T[0]==0)			//空树
		return 0;
	for(i=0;i<=MAX_TREE_SIZE-1;i++)
		if(T[i]==e)		//找到e
			return T[i*2+1];
		return 0;
} 

/*初始条件：二叉树T存在,e是树T中的某个结点。*/
/*操作结果：返回e的右孩子。若e无右孩子，则返回"空"。*/
TElemType RightChild(SqBiTree T,TElemType e)
{
	int i;
	if(T[0]==0)			//空树
		return 0;
	for(i=0;i<=MAX_TREE_SIZE;i++)
		if(T[i]==e)		//找到e
			return T[i*2+2];
	return 0;			//没有找到 
}

/*初始条件：二叉树T存在，e是T中某个结点。*/
/*操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回"空"。*/
TElemType LeftSibling(SqBiTree T,TElemType e)
{
	int i;
	if(T[0]==0)			//空树
		return 0;
	for(i=1;i<=MAX_TREE_SIZE-1;i++)
		if(T[i]==e&&i%2==0)		//找到e且其序号为偶数是右孩子
			return T[i-1];
	return 0;			//没找到e 
} 

/*初始条件：二叉树T存在，e是T中某个结点。*/
/*操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回"空"。*/
TElemType RightSibling(SqBiTree T,TElemType e)
{
	int i;
	if(T[0]==0)		//空树
		return 0;
	for(i=1;i<=MAX_TREE_SIZE-1;i++)
		if(T[i]==e&&i%2)		//找到e且其序号为奇数做孩子
			return T[i+1];
	return 0;			//没找到e 
} 

/*初始条件：二叉树T存在。*/
/*把从q的j结点开始的子树移为从T的i结点开始的子树。*/
void Move(SqBiTree q,int j,SqBiTree T,int i)
{
	if(q[2*j+1]!=0)		//q的左子树不空
		Move(q,(2*j+1),T,(2*i+1));		//把q的j结点的左子树移为T的i结点的左子树
	if(q[2*j+2]!=0)		//q的右子树不空
		Move(q,(2*j+2),T,(2*i+2));		//把q的j结点右子树移为T的i结点的右子树 
	T[i]=q[j];			//把q的j结点移为T的i结点
	q[j]=0; 
} 

/*初始条件：二叉树存在，p是T中某个结点的值，LR为0或1，非空二叉树c与T不相交且右子树为空。*/
/*操作结果：根据LR为0或1，插入c为T中p结点的左或右子树,p结点的原有左或右子树则为c的右子树。*/ 
void InserChild(SqBiTree T,TElemType p,int LR,SqBiTree c)
{
	int j,k,i=0;
	for(j=0;j<int(pow(2,BiTreeDepth(T)))-1;j++)		//查找p的序号
		if(T[j]==p)			//j为p的序号
			break;
	
	k=2*j+1+LR;				//k为p的左或右孩子的序号
	if(T[k]!=0)
		Move(T,k,T,2*k+2);		//把从T的k结点开始的子树移为从k结点的右子树开始的子树
	Move(c,i,T,k); 
}


/*初始条件：二叉树T存在，Visit是对结点操作的应用函数。*/
/*操作结果：层序遍历二叉树*/
void LevelOrderTraverse(SqBiTree T,void(*Visit)(TElemType))
{
	int j;
	int i=MAX_TREE_SIZE-1;
	while(T[i]==0)
		i--;
	for(j=0;j<=i;j++)		//从根结点起，按层序遍历二叉树
		if(T[j]!=0)
			Visit(T[j]);		//只遍历非空的结点	
	printf("\n"); 
}
int main()
{
	int i;
	int ch;
	position p;
	TElemType e;
	SqBiTree T,s;
	InitBiTree(T);
	printf("成功构造空二叉树\n");
	CreateBiTree(T);
	printf("********************************\n");
	printf("1、结点双亲\n2、结点孩子\n3、左右兄弟\n");
	printf("4、对树判空\n5、返回树深\n6、修改结点\n");
	printf("7、逐层遍历\n0、退出操作\n");
	printf("********************************\n");
	printf("请选择接下来的操作：");
	while(scanf("%d",&ch)&&ch!=0)
	{
		if(ch==1){
			printf("请输入要寻找双亲的结点：");
			scanf("%d",&e);
			if(Parent(T,e)){
				printf("%d结点的双亲是%d\n",e,Parent(T,e));
			}else{
				printf("输入错误!\n");
			}
		}
		if(ch==2){
			printf("请输入要查询孩子的根节点：");
			scanf("%d",&e);
			if(LeftChild(T,e)){
				printf("%d的左孩子是%d ",e,LeftChild(T,e));
			}
			if(RightChild(T,e)){
				printf("%d的右孩子是%d ",e,LeftChild(T,e));
			}
			printf("\n");
		}
		if(ch==3){
			printf("请输入要查询左右兄弟的结点：");
			scanf("%d",&e);
			if(LeftSibling(T,e)){
				printf("%d结点的左兄弟是%d ",e,LeftSibling(T,e));
			}
			if(RightSibling(T,e)){
				printf("%d结点的右兄弟是%d ",e,RightSibling(T,e));
			}
			printf("\n");
		}	
		if(ch==4){
			if(BiTreeEmpty(T)){
				printf("这是一个空树!\n");
			}else{
				printf("这是一个非空树!\n");
			}
		}
		if(ch==5){
			printf("树的深度为%d\n",BiTreeDepth(T));
		}
		if(ch==6){
			printf("请输入要修改结点的层号和本层序号：");
			scanf("%d%d",&p.level,&p.order);
			printf("请输入修改以后的值：");
			scanf("%d",&e);
			if(Assign(T,p,e))
				printf("操作成功!\n");
			else
				printf("输入错误!\n"); 
		}
		if(ch==7){
			LevelOrderTraverse(T,visit);
		}
		printf("请选择接下来的操作：");
	}
	printf("成功退出操作!\n");
	return 0;
}

上一篇： cuda学习笔记(1)

下一篇：【Launcher延伸】窗口小部件Widget及时钟实例

C_树(ADT)-树的表示和实现

C_树(ADT)-树的表示和实现

使用"函数递归"实现基于php和MySQL的动态树型菜单_PHP

python数据结构和算法,八大排序算法,二叉树的实现

使用"函数递归"实现基于php和MySQL的动态树型菜单

使用"函数递归"实现基于php和MySQL的动态树型菜单

实现基于php和MySQL的动态树型菜单

使用函数递归实现基于php和MySQL的动态树型菜单_php基础

使用函数递归实现基于php和MySQL的动态树型菜单

实现基于php和MySQL的动态树型菜单_MySQL

Java带复选框的树（Java CheckBox Tree）实现和应用