1. 啥是树
之前所讲的线性表、队列、栈，实际上都是一种一对一的结构，而树是一种一对多的结构。
树这个名字起的非常形象，所以一个树的结构可如下图所示：
也就是说每个节点下面有N个节点（N>=0），且根节点数量小于1的数据结构为树。当根节点数量为0是，是一个空树。
2. 树的相关概念
节点：上图中1-8都是节点
根节点：1是根节点，没有父节点
双亲：1是2/3/4的双亲，2是5/6的双亲
兄弟：2/3/4是兄弟，5/6是兄弟
孩子：2/3/4是1的孩子，直接下挂的节点
度：节点的度是节点拥有的孩子数，树的度是树内各节点度的最大值，例如上面的数，度为3
3. 如何用数据结构对树进行描述
第一，树是由节点组成的，所以要想弄明白怎么表示树，应该先搞懂如何表示节点。
第二，寻找节点的共同特征，节点至少有一个数据存储区域，用来保存节点的数据信息，例如上图中节点的数据区域存储了节点的编号，实际上可能会有更多信息。例如一个地理区域树，根节点是中国，子节点是各省级行政区划信息，每个节点可能保存节点行政区划编号、邮编、电话区号、人口数量等信息。
第三，每个节点有若干个子节点，也就是说若干节点与本节点有一种关联，表示是本节点的孩子，此处完全可以用指针来表示，因为子节点的数量不一定，所以指针个数也不一定。
第四，每个节点指向子节点的指针个数可能为0，也可能是1、2、3…，但是最大也就是树的度了。所以我们可以用一个数组来保存指向子节点的指针。
因为从根节点出发，可以顺着指针找到所有节点，所以只要根节点搞定了，实际上整个树的数据结构也就确定了。
综上所述：节点可以如下描述：
#define DEGREE 10 //树的度
struct TreeNode{
int data;//数据区域
int childnum;//子节点数量，最大不能超过DEGREE
struct TreeNode* children[DEGREE];//保存指向当前节点子节点的指针数组
};
4. 代码实现
接下来我们用代码来实现下刚才的树
/* * 使用数组描述子节点的普通树实现 * 作者：熊猫大大 * 时间：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; }
