数据结构 之 树

1. 定义：

树是一种非线性的数据结构，，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的；

它具有以下的特点：

< 1 > 他有一个特殊的节点，称为根节点，根节点没有前驱节点；

< 2 > 除根结点外，其余结点被分成M(M > 0)个互不相交的集合T1、T2、......、Tm，其中每一个集合Ti (1 <= i <= m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继

类似于这样，A是根节点，A有三个分支B，C，D；这三个分支有可以看作三个互不相交的树；

同时，每一棵子树有且仅有一个前驱，但是却可以有多个后继，例如B有两个子树，C有一个子树，D有三个子树；

< 3 > 树是递归定义的。

注意：树形结构中的子树是不能有交集的，否则不能称为树形结构！！！

例如这两个结构，左边的可以称为树，而右边的则不行，因为节点C和节点F相连接，两棵树之间产生了交集，故不能被称为树形结构；

2. 概念（重要）：

二叉树中有许多重要的概念，对以后我们理解树形结构有重要的作用：

< 1 > 节点的度： 一个节点含有子树的个数称为该节点的度，如上图，A节点的度为5，B节点的度为0，E节点的度为3；

< 2 > 树的度： 一棵树中，所有节点的度的最大值，称为树的度，如上图，树的度为5；

< 3 > 叶子节点或者终端节点： 度为0的节点，称为叶子节点或者终端节点，如上图，B，G，H，L，M，J，K，F都是叶子节点；

< 4 > 双亲结点或者父节点： 若一个节点含有子节点，则这个节点称为其子节点的父节点，如上图，A为BDCDEF的父节点；

< 5 > 孩子节点或子节点： 一个节点含有的子树的根节点称为该节点的子节点， 如上图：BCDEF为A的子节点；

< 6 > 根节点： 一棵树中，没有双亲节点的结点；如上图，A为根节点；

< 7 > 节点的层次： 从根开始定义起，根为第1层，根的子节点为第2层，以此类推，如上图，A为第一层，BCDEF节点为第二层，LM节点为第四层；

< 8 > 树的高度或深度： 树中节点的最大层次，如上图：该树的节点最大层次为4，故该树的高度为4；

< 9 > 非终端节点或分支节点： 度不为0的节点，即非叶子节点的节点都是非终端节点；如上图，ACDE都为分支节点；

< 10 > 兄弟节点： 具有相同父结点的节点互称为兄弟节点，如上图：L节点和M节点为兄弟节点；

< 11 > 堂兄弟节点： 双亲在同一层的节点互为堂兄弟，如上图：GHIJK都互为堂兄弟节点；

< 12 > 节点的祖先： 从根到该结点所经分支上的所有结点，如上图：节点G的祖先为C节点和A节点；

< 13 > 子孙： 以某结点为根的子树中任一结点都称为该结点的子孙，如上图：该树的除A之外的所有节点都是节点A的子孙；

< 14 > 森林： 由m（m>=0）棵互不相交的树组成的集合称为森林，例如这棵树可以被称为森林；

3. 树的表示形式：

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：双亲表示法， 孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

class Node {
    int value;            //存放节点的值              
    Node firstChild;      //第一个孩子节点的地址
    Node nextBrother;     //下一个兄弟节点的地址
}

4. 树的应用：

在我们日常中，最常见的树的应用就是我们的文件资源管理器；

例如我们的电脑中有很多的盘，例如C盘，D盘，我们可以把每一个盘都看成一棵树，当我们点进C盘的时候，有会有很多的文件夹，这些文件夹就是C盘这个根节点的子树，以此类推，这就是树形结构在实际中的应用；

以上就是树的全部内容，感谢观看！！！！！！