在日常生活中或者开发中我们经常会用到一些树形结构(例如：二叉树、多叉树见 附图1)。为什么要用到树结构呢，是因为使用树形结构可以很快速、清晰的去对应的树节点内去查找需要的数据，这样就大大的提高了效率。
二叉树 、多叉树
附图1:
tree.jpg
树结构中的元素概念
附图2:
tree_demo.jpg
节点：
树上的每个分叉点的元素。
「附图2 」中的 1、2、...... 14、15 都是节点
根节点 ：
一棵树最多只有一个根结点，即最开始分叉的节点。
「附图2 」中的 1节点是其他节点的根节点
注意：
- 一棵树可以没有任何节点，称之为
空树- 一棵树可以只有一个节点，也就是
根节点
父节点 ：
树中分叉的那一个节点
例子：
「附图2 」中的 1节点是 2节点和 3节点的父节点； 2节点是 4节点和 5节点的父节点
子节点 ：
树中某一个节点分叉出去的下一级节点
例子：
「附图2 」中的 2节点和 3节点是 1节点的子节点；4节点和 5节点是 2节点的子节点
兄弟节点 ：
树中某一个节点分叉出去的下一级节点中的同一级的节点，即同一级的节点有 相同的父节点
例子：
「附图2 」中的 2节点和 3节点是 相互的兄弟节点； 4节点和 5节点是 相互的兄弟节点
注意 : 8节点和 10节点是 相互的兄弟节点, 因为8节点和 10节点没有相同的父节点
子树 ：
树中某一个节点分叉出去的下一级节点上的某一个节点下的所有节点组成的树
例子：
「附图2 」中的 2节点和其 往下的所有节点 就是1 节点的子树（2、4、5、8、9、10、11这些节点组成的树是 1节点的一个子树）
3节点和其 往下的所有节点 就是1 节点的子树（3、6、7、12、13、14、15这些节点组成的树是 1节点的子树）
4节点和其 往下的所有节点 就是2节点的子树（ 4、8、9、这些节点组成的树是 2节点的一个子树）
5节点和其 往下的所有节点 就是2节点的子树（ 5、10、11、这些节点组成的树是 2节点的另一个子树）
左子树 ：
树中某一个节点分叉出去的下一级节点上的左侧的一个节点下的所有节点组成的树
例子：
「附图2 」中的 2节点和其 往下的所有节点 就是1 节点的左子树（2、4、5、8、9、10、11这些节点组成的树是 1节点的左子树）
4节点和其 往下的所有节点 就是2 节点的左子树（4、8、9、这些节点组成的树是 2节点的左子树）
右子树 ：
树中某一个节点分叉出去的下一级节点上的右侧的一个节点下的所有节点组成的树
例子：
「附图2 」中的 3节点和其 往下的所有节点 就是1 节点的右子树（3、6、7、12、13、14、15这些节点组成的树是 1节点的右子树）
5节点和其 往下的所有节点 就是2节点的右子树（ 5、10、11、这些节点组成的树是 2节点的右子树）
附图3:
tree_02.jpg
节点的度（degree） ：
子树的个数
例子：
「附图3 」中的 B(2)节点的度为2 ；K(11)节点的度为3；E(5)节点的度为0
树的度（degree） ：
所有节点度 中的最大值
例子：
「附图3 」中的 A(1)节点的度为5 是所有节点中拥有最大的度，所以树的度就是5
叶子节点 ：
度为0的节点
例子：
「附图3 」中 的E(5)、J(10)、L(12)、P(16)、Q(17)节点 的度为0就是叶子节点
非叶子节点 ：
度不为0的节点
边数 ：
当前节点到下一个字节点的路径
根节点没有边
例子：
「附图3 」中 的A(1)节点到B(2)节点的路径是一条边；B(2)节点到H(7)节点的路径是一条边
层数 ：
每一个节点和其子节点所在的位置层级。根结点在第一层，根结点的子节点在第二层，依次类推（也有的是从0层开始计算的）
例子:
「附图3 」中 的A(1)节点 是第一层；A(1) 的子节点B(2)、C(3)、D(4)、E(5)、F(6)节点是第二层; H(7)、I(9)、J(10)、K(11)、L(12)、M(13)、N(14)节点是第三层; O(15)、P(16)、Q(17)、R(18)、S(19)、T(20)节点是第四层; 所以这棵树共有四层
节点的深度 ：
从根节点到当前节点的最短的唯一直达路径上的节点总数
例子:
「附图3 」中 的B(2)节点深度是2，即（从A(1)根节点到B(2)节点的唯一直达路径上的节点只有A(1) 、B(2)共计2个节点，总数为2）；
C(3)节点深度是2，即（从A(1)根节点到C(3)节点的唯一直达路径上的节点只有A(1) 、C(3)共计2个节点，总数为2）；
O(15)节点深度是4，即（从A(1)根节点到O(15)节点的唯一直达路径上的节点有：A(1) 、B(2)、H(7) 、O(15)共计4个节点）；
节点的高度 ：
从当前节点到其子树上最远的叶子节点的最短的唯一直达路径上的节点总数
例子：
「附图3 」中 的C(3)节点高度是3，即从C(3)节点到其子树上最远的Q(17)叶子节点的最短路径上的节点有C(3)、I(9)、Q(17)共计3个节点；J(10)、Q(17)都是叶子节点。
D(4)节点高度是3，即从D(4)节点到其子树上最远的R(18)叶子节点的最短路径上的节点有D(4)、K(11)、R(18)共计3个节点; L(12)、R(18)、S(19)、T(20)都是叶子节点，R(18)、S(19)、T(20)三个叶子节点是同一层级。
注意：
- 深度和高度的区别
深度是 从根节点到当前节点的路径上的节点总数；高度是 从当前节点到其子树上最远的叶子节点路径上的节点总数
树的深度 ：
所有节点深度中的最大值
例子
「附图3 」中 的O(15)节点深度是4， 是这棵树最大的深度值，所以这棵树的深度是4
树的高度 ：
所有节点高度中的最大值
例子
「附图3 」中 的A(1)根节点高度是4， 是这棵树最大的高度值，所以这棵树的高度是4
树的深度 等于 树的高度
有序树：
树的任意节点下的子节点之间都是有顺序关系的。（如下附图4）
tree_oeder.jpg
无序树、自由树：
树的任意节点下的子节点之间都是没有顺序关系的。（如下附图5）
tree_no_order.jpg
森林：
由 m（m ≥ 0）颗互不想交的树组成的集合。
网友评论