手记

C语言数据结构(10)--使用数组描述子节点的普通树实现

啥是树

之前所讲的线性表、队列、栈,实际上都是一种一对一的结构,而树是一种一对多的结构。

树这个名字起的非常形象,所以一个树的结构可如下图所示:

也就是说每个节点下面有N个节点(N>=0),且根节点数量小于1的数据结构为树。当根节点数量为0是,是一个空树。

相关概念

  • 节点:上图中1-8都是节点
  • 根节点:1是根节点,没有父节点
  • 双亲:1是2/3/4的双亲,2是5/6的双亲
  • 兄弟:2/3/4是兄弟,5/6是兄弟
  • 孩子:2/3/4是1的孩子,直接下挂的节点
  • 度:节点的度是节点拥有的孩子数,树的度是树内各节点度的最大值,例如上面的数,度为3

如何用数据结构对树进行描述

第一,树是由节点组成的,所以要想弄明白怎么表示树,应该先搞懂如何表示节点。

第二,寻找节点的共同特征,节点至少有一个数据存储区域,用来保存节点的数据信息,例如上图中节点的数据区域存储了节点的编号,实际上可能会有更多信息。例如一个地理区域树,根节点是中国,子节点是各省级行政区划信息,每个节点可能保存节点行政区划编号、邮编、电话区号、人口数量等信息。

第三,每个节点有若干个子节点,也就是说若干节点与本节点有一种关联,表示是本节点的孩子,此处完全可以用指针来表示,因为子节点的数量不一定,所以指针个数也不一定。

第四,每个节点指向子节点的指针个数可能为0,也可能是1、2、3…,但是最大也就是树的度了。所以我们可以用一个数组来保存指向子节点的指针。

因为从根节点出发,可以顺着指针找到所有节点,所以只要根节点搞定了,实际上整个树的数据结构也就确定了。

综上所述:节点可以如下描述:

#define DEGREE 10 //树的度
struct TreeNode{
	int data;//数据区域
	int childnum;//子节点数量,最大不能超过DEGREE
	struct TreeNode* children[DEGREE];//保存指向当前节点子节点的指针数组
};

代码实现

接下来我们用代码来实现下刚才的树

/*
* 使用数组描述子节点的普通树实现
* 作者:熊猫大大
* 时间:2019-10-13
*/
#include<stdio.h>
#define DEGREE 3 //树的度

struct TreeNode {
	int data;//数据区域
	int childnum;//子节点数量,最大不能超过DEGREE
	struct TreeNode* children[DEGREE];//保存指向当前节点子节点的指针数组
};

//添加当前节点子节点
int addChild(struct TreeNode* curNode, int data) 
{
	if (curNode->childnum >= DEGREE) //超过最大度数
	{
		return 0;
	}
	curNode->children[curNode->childnum]= (struct TreeNode*)malloc(sizeof(struct TreeNode));//添加子节点
	curNode->children[curNode->childnum]->data = data;//子节点数据
	curNode->children[curNode->childnum]->childnum = 0;//子节点的孩子数量初始化为0
	curNode->childnum++;//当前节点孩子数量+1
	return 1;
}

//遍历当前节点与子节点
void printTree(struct TreeNode *node) 
{
	int i = 0;
	printf("父:");
	printf("%d ---- ",node->data);
	if (node->childnum == 0) 
	{
		printf("无子节点");
	}

	for (i = 0 ; i < node->childnum; i++)
	{
		printf("子:");
		printf("%d  ", node->children[i]->data);
	}
	printf("\n");
	for (i = 0; i < node->childnum; i++)
	{
		printTree(node->children[i]);
	}
}

int main()
{
	//设定根节点
	struct TreeNode root;
	root.data = 1;
	root.childnum = 0;
	//为当前节点添加3个子节点
	addChild(&root,2);
	addChild(&root, 3);
	addChild(&root, 4);
	printf("添加2/3/4节点后:\n");
	printTree(&root);
	//为节点2添加子节点5,6
	addChild(root.children[0], 5);
	addChild(root.children[0], 6);
	//为节点3添加子节点7
	addChild(root.children[1], 7);
	//为节点4添加子节点8
	addChild(root.children[2], 8);
	printf("添加5/6/7/8节点后:\n");
	printTree(&root);
	return 1;
}

输出效果,还是相当清晰滴:

0人推荐
随时随地看视频
慕课网APP