🎁个人主页：我们的五年
🔍系列专栏：数据结构课程学习
🎉欢迎大家点赞👍评论📝收藏⭐文章
🚗1.树的概念：
树是一种非线性的数据结构，有n个有限节点组成一个有层次的集合。它的结构看起来像一颗倒挂的树，根在上面，叶子和枝干朝下。
●最上面的节点为根节点，根节点没有前驱节点。
●树是递归定义的。
●树形结构中，子树是不能相交的，否则就不构成树，也就是除根节点以外，其他的节点只有一个父节点。
●n个节点的树，有n-1条线。
🚗2.树的相关概念：
树里面的基本名词的意思：
●节点的度：一个节点的子树称为节点的度，也就是看该节点有几个子节点。A节点的度为6，B节点的度为0，F节点的度为3。
●叶节点或终端节点：度为0的节点为叶节点，也就是像叶子一样没有分支。B，C，H，I，P，Q，K，L，M，N全部都是叶节点。
●父节点：一个节点含有子节点，那么称该该节点是此子节点的父节点。A是B的父节点。
●子节点：一个含有子树的根节点，该子树的节点为根节点的子节点。P为J的子节点。
●兄弟节点：有相同父节点的节点为兄弟节点。B，C为兄弟节点。
●树的度：树里面最大节点的度为树的度。A的度为6，其他的都小于6，所以树的度为6。
●节点的层次：根为第一层，根的子节点是第二层。下图中有四层。
●树的高度或深度：树中节点的最大层次，节点的最大层次为4，所以树的高度为4。
●根节点是所以节点的祖先，所以节点是根节点的子孙。
●堂兄弟节点：父节点在同一层的节点为兄弟节点。K和N为堂兄弟节点。
●森林：由两棵以上互不相加的树的集合组成森林。
🚗3.树的表示：
根据之前我们学的数据结构，实现任何一种数据结构，最起码也要有存储数据，并且能找到每个节点这两个基本的功能。
⛷方法一：
因为前面有树的度这一个概念，也就是说，假如一棵树的度为N，任何一个节点的子节点最多有N个，所以我们定义节点结构的时候，就只需要定义一个指针数组，指针数组的大小为N，把指向这个节点的所以子节点的指针存在指针数组里面。虽然这样可以实现树，但是会存在空间浪费，在有些情况下，空间浪费会非常大，如下图：树的度为4，但是除了E节点以外，其他节点里面的指针数组都是空的，但是也为他们开辟了N个指针大小的空间，这样就浪费空间了，如果节点更多，那么浪费的空间该是多么大啊！
⛷方法二（左孩子右兄弟法）：
也就是说，一个节点里面，一个指针存着子节点的最左边的子节点，一个指针存着右兄弟的指针。左孩子可以在节点的层中移动，右兄弟可以在同一层遍历，这样就可以找到每一个节点，这种方法也不会存在空间浪费，每个节点一直都是两个指针，也不像第一种方法一样，定义一个指针数组。
typedef int DataType;
struct Node
{
struct Node* firstChild1; // 第一个孩子结点
struct Node* pNextBrother; // 指向其下一个兄弟结点
DataType data; // 结点中的数据域
};
🚗4. 树在实际中的运用（表示文件系统的目录树结构）
太好玩了，爱玩！