一、树的概念
什么是树形结构
树形结构指的是数据元素之间存在着“一对多”的树形关系的数据结构,是一类重要的非线性数据结构
树形结构是一层次的嵌套结构。 一个树形结构的外层和内层有相似的结构， 所以这种结构多可以递归的表示。经典数据结构中的各种是一种典型的树形结构：一颗树可以简单的表示为根， 左子树， 右子树。 左子树和右子树又有自己的子树。
树形结构的应用
树形结构可以大大提高查询效率
树形结构的基本概念
节点，树形结构中的每一个元素都可以称为节点，上述树形结构图中1、2、3、4、5....每一个元素都是这个树的节点
根节点，一棵树最多只有一个根节点，元素1就是根节点
父节点，元素1所在的节点就是元素2、3、4、5、6所在节点的父节点
子节点，元素2、3、4、5、6所在的节点是元素1所在节点的子节点
兄弟节点，元素2，3，4，5，6之间可以互称为兄弟节点，拥有同一个父节点的节点之间才是兄弟节点
以上述右边图为例
节点的度，子树的个数。 节点1的度为5，有5个子树； 节点2的度为2，有2个子树
树的度，所有节点度中最大的值
叶子节点，度为0的节点，如4、7、9、11、12、13、14、15都是叶子节点 非叶子节点则相反
层数，根节点在第一层，根节点的子节点在第二层
节点的深度，从根节点到当前节点的唯一路径上的节点总数
节点的高度，从当前节点到最远的叶子节点的路径上的节点总数
如节点2的深度是2，高度是3
树的深度，所有节点深度中的最大值
树的高度，所有节点高度中的最大值
树的深度等于高度
有序树、无序树、森林
有序树，树中任意节点的字节点之间有顺序关系
无序树，树中任意节点的字节点之间没有顺序关系，也成为自由树
森林，有m颗互不相交的树组成的集合
二、二叉树
二叉树的特点
- 每个节点的度最大为2，即最多拥有两颗子树
- 左子树和右子树是有顺序的，即使节点只有一颗子树也要区分左子树右子树
- 二叉树是有序树
这些都是二叉树
二叉树的性质
- 非空二叉树的第i层最多有2i-1个节点（i >= 1）
- 在高度为h的二叉树上最多有2h-1个节点（h >= 1）
- 对于任何一颗非空二叉树，如果叶子节点个数为n0，度为2的节点的个数为n2，那么n0 = n2 + 1
节点的度为1就有1条边，度为2就有2条边，叶子节点没有边
假设度为1的节点的个数为n1，那么二叉树节点总数为n = n0 + n1 + n2
整棵树出了根节点上没有边之外，其他每个节点上都有一条边，边数T = n1 + 2 * n2 = n - 1 = n0 + n1 + n2 - 1 => n0 = n2 + 1
真二叉树
真二叉树所有节点的度要么为0要么为2，如下图中左边是真二叉树，右边非真二叉树
满二叉树
满二叉树所有节点的度都 要么为0要么为2，且所有的叶子节点都在最后一层
满二叉树的性质，假设满二叉树的高度为h(h >= 1)，那么
- 第i层节点的数量为 2i-1
- 叶子节点的数量为 2h-1
- 总节点的数量为n，n = 2h-1，h = log2(n+1){log_2{(n+1)}}log2(n+1)
- 在同样高度的二叉树中，满二叉树的叶子节点数量最多，总节点数量最多
- 满二叉树一定是真二叉树，真二叉树不一定是满二叉树
完全二叉树
叶子节点只会出现在最后2层，且最后1层的叶子节点都靠左对齐，靠左对齐，就是叶子节点只会出现在左边
- 完全二叉树从根节点至倒数第二层是一颗满二叉树
- 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
节点从上到下，从左到右排布就是完全二叉树，完全二叉树排满就是满二叉树
完全二叉树的性质
- 度为1的节点只有左子树
- 度为1的节点要么是1个要么是0个
- 同样节点数量的二叉树，完全二叉树的高度最小 假设完全二叉树的高度为h(h>=1)，那么
- 至少有2h-1个节点
- 最多有2h - 1 个节点 总节点数为n，则有
- 2h-1 <= n <= 2h
- h-1 <= log2n{log_2{n}}log2n < h
- h = floor(log2n{log_2{n}}log2n) + 1 plus：floor是向下取整，ceiling是向上取整
一颗有n个节点的完全二叉树(n > 0)，从上到下、从左到右对所有节点从1开始编号，对任意第i个节点
- 如果i = 1，则i节点是根节点
- 如果i > 1，它的父节点编号为floor（i / 2）
- 如果2i <= n，它的左子节点编号为2i
- 如果2i > n，则该节点无左子节点
- 如果2i + 1 <= n，则该节点的右子节点编号为2i + 1
- 如果2i + 1 > n，则该节点无右子节点
