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