Data Structures (五) - 二叉树Binary Tree

一、树的概念

什么是树形结构

树形结构指的是数据元素之间存在着“一对多”的树形关系的数据结构,是一类重要的非线性数据结构

树形结构是一层次的嵌套结构。 一个树形结构的外层和内层有相似的结构， 所以这种结构多可以递归的表示。经典数据结构中的各种是一种典型的树形结构：一颗树可以简单的表示为根， 左子树， 右子树。 左子树和右子树又有自己的子树。

image.png

树形结构的应用

image.png

树形结构可以大大提高查询效率

树形结构的基本概念

节点，树形结构中的每一个元素都可以称为节点，上述树形结构图中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颗互不相交的树组成的集合

二、二叉树

二叉树的特点

image.png

• 每个节点的度最大为2，即最多拥有两颗子树
• 左子树和右子树是有顺序的，即使节点只有一颗子树也要区分左子树右子树
• 二叉树是有序树

这些都是二叉树

image.png

二叉树的性质

• 非空二叉树的第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，如下图中左边是真二叉树，右边非真二叉树

image.png

满二叉树

image.png

满二叉树所有节点的度都 要么为0要么为2，且所有的叶子节点都在最后一层

满二叉树的性质，假设满二叉树的高度为h(h >= 1)，那么

• 第i层节点的数量为 2i-1
• 叶子节点的数量为 2h-1
• 总节点的数量为n，n = 2h-1，h = {log_2{(n+1)}}
• 在同样高度的二叉树中，满二叉树的叶子节点数量最多，总节点数量最多
• 满二叉树一定是真二叉树，真二叉树不一定是满二叉树

完全二叉树

叶子节点只会出现在最后2层，且最后1层的叶子节点都靠左对齐，靠左对齐，就是叶子节点只会出现在左边

image.png

• 完全二叉树从根节点至倒数第二层是一颗满二叉树
• 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

image.png

节点从上到下，从左到右排布就是完全二叉树，完全二叉树排满就是满二叉树

完全二叉树的性质

• 度为1的节点只有左子树
• 度为1的节点要么是1个要么是0个
• 同样节点数量的二叉树，完全二叉树的高度最小 假设完全二叉树的高度为h(h>=1)，那么

1. 至少有2h-1个节点
2. 最多有2h - 1 个节点 总节点数为n，则有
3. 2h-1 <= n <= 2h
4. h-1 <=
5. h = floor({log_2{n}}) + 1 plus：floor是向下取整，ceiling是向上取整

一颗有n个节点的完全二叉树(n > 0)，从上到下、从左到右对所有节点从1开始编号，对任意第i个节点

1. 如果i = 1，则i节点是根节点
2. 如果i > 1，它的父节点编号为floor（i / 2）
3. 如果2i <= n，它的左子节点编号为2i
4. 如果2i > n，则该节点无左子节点
5. 如果2i + 1 <= n，则该节点的右子节点编号为2i + 1
6. 如果2i + 1 > n，则该节点无右子节点

image.png