树
树的概念与结构
树是⼀种⾮线性的数据结构，它是由 n（n>=0） 个有限结点组成⼀个具有层次关系的集合。把它叫做树是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，⽽叶朝下的。
PS
- 有⼀个特殊的结点，称为根结点，根结点没有前驱结点。
- 除根结点外，其余结点被分成 M(M>0) 个互不相交的集合 T1、T2、……、Tm ，其中每⼀个集合Ti(1 <= i <= m) ⼜是⼀棵结构与树类似的⼦树。每棵⼦树的根结点有且只有⼀个前驱，可以有 0 个或多个后继。因此，树是递归定义的。
注意：
- ⼦树是不相交的
- 除了根结点外，每个结点有且仅有⼀个⽗结点
- ⼀棵N个结点的树有N-1条边
- 树形结构中，⼦树之间不能有交集，否则就不是树形结构（如下图）
树的相关术语
- ⽗结点/双亲结点：若⼀个结点含有⼦结点，则这个结点称为其⼦结点的⽗结点； 如上图：A是B的⽗结点
- ⼦结点/孩⼦结点：⼀个结点含有的⼦树的根结点称为该结点的⼦结点； 如上图：B是A的孩⼦结点
- 结点的度：⼀个结点有⼏个孩⼦，他的度就是多少；⽐如A的度为6，F的度为2，K的度为0
- 树的度：⼀棵树中，最⼤的结点的度称为树的度； 如上图：树的度为 6
- 叶⼦结点/终端结点：度为 0 的结点称为叶结点； 如上图： B、C、H、I... 等结点为叶结点
- 分⽀结点/⾮终端结点：度不为 0 的结点； 如上图： D、E、F、G... 等结点为分⽀结点
- 兄弟结点：具有相同⽗结点的结点互称为兄弟结点(亲兄弟)； 如上图： 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 TreeNode* child; // 左边开始的第⼀个孩⼦结点struct TreeNode* brother; // 指向其右边的下⼀个兄弟结点int data; // 结点中的数据域};
假设我们有下图这样的二叉树，A是根节点，指向它左边的第一个孩子节点B,B在指向它右边的兄弟节点。这一层结束后，开始第三层，B再指向它的孩子节点D，D再指向它的兄弟节点E，F，E再指向它的左孩子H，H在指向它的兄弟节点I，C没有左孩子所以直接指向右孩子。
树形结构实际运⽤场景
⽂件系统是计算机存储和管理⽂件的⼀种⽅式，它利⽤树形结构来组织和管理⽂件和⽂件夹。在⽂件系统中，树结构被⼴泛应⽤，它通过⽗结点和⼦结点之间的关系来表⽰不同层级的⽂件和⽂件夹之间的关联。
