数据结构—树
树的概念与结构
树是一种非线性的数据结构，它是由 n （ n>=0） 个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的 。
1.有一个特殊的结点，称为根结点，根结点没有前驱结点。
2.除根结点外，其余结点被分成 M(M>0) 个互不相交的集合 T1 、 T2 、 …… 、 Tm ，其中每一个集合Ti(1 <= i <= m) 又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以
有 0 个或多个后继。因此，树是递归定义的。
树形结构
1.子树是不相交的（如果存在相交就是图）
2.除了根结点外，每个结点有且仅有一个父结点
3.一棵N个结点的树有N-1条边
树形结构中，子树之间不能有交集，否则就不是树形结构。
非树形结构
树的相关术语
父结点/双亲结点： 若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点。
子结点/孩子结点： 一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点
结点。
度：一个结点有几个孩子，他的度就是多少；比如A的度为6，F的度为2，K的度为0。
树的度： 一棵树中，最大的结点的度称为树的度； 如上图：树的度为 6。
叶子结点/终端结点： 度为 0 的结点称为叶结点； 如上图： B 、 C 、 H 、I、K、L、M、N、P、Q 结点为叶结点。
分支结点/非终端结点： 度不为 0 的结点； 如上图： D 、 E 、 F 、 G、J结点为分支结点。
兄弟结点： 具有相同父结点的结点互称为兄弟结点(亲兄弟)； 如上图： B 、 C 是兄弟结点。
结点的层次： 从根开始定义起，根为第 1 层，根的子结点为第 2 层，以此类推。
树的高度或深度： 树中结点的最大层次； 如上图：树的高度为 4。
结点的祖先： 从根到该结点所经分支上的所有结点；如上图： A 是所有结点的祖先 。
路径： 一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列；比如A到Q的路径 为：A-E-J-Q；H到Q的路径H-D-A-E-J-Q。
子孙： 以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙。
森林： 由 m （ m>0） 棵互不相交的树的集合称为森林。
树的表示
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系。我们这里就简单的了解其中最常用的孩子兄弟表示法。
struct TreeNode
{
struct Node* child; // 左边开始的第⼀个孩⼦结点
struct Node* brother; // 指向其右边的下⼀个兄弟结点
int data; // 结点中的数据域
};
树形结构实际运用场景
文件系统是计算机存储和管理文件的一种方式，它利用树形结构来组织和管理文件和文件夹。在文件系统中，树结构被广泛应用，它通过父结点和子结点之间的关系来表示不同层级的文件和文件夹之间的关联。
