树需要掌握的基本概念

1、节点、根节点、父节点、子节点、兄弟节点
2、一棵树可以没有任何节点，称为空树
3、一棵树可以只有一个节点，这个时候这棵树只有根节点
4、子树，左子树、右子树是二叉树里面的概念
5、节点的度:子树的个数
6、叶子节点:度为0的节点
7、非叶子节点:度不为0的节点
8、层数:根节点在第一层，根节点的子节点在第二层，依此类推
9、节点的高度:从当前节点到最远叶子节点的路径上的节点总数
10、树的高度:所有节点高度中的最大值

二叉树

基本特点

1、每个节点的度最大为2(即一个节点最多拥有两棵子树
2、左子树和右子树是有固定顺序的（区别于有序树是相对顺序，有序树只有一个子节点时，是没有顺序的，其顺序是两个子节点中其中一个相对于另一个子节点的顺序）
3、非空二叉树的第i层，最多有2^(i-1)个节点
4、在高度为h的二叉树上最多有2^h - 1个节点

满二叉树

最后一层节点的度都为0，其他层节点度都为2。
在同样高度的二叉树中，满二叉树的叶子节点数量最多，总节点数量最多。

在这里插入图片描述

性质

假设满二文树的高度为h，
那么第i层的节点数量:2^(i-1)
叶子节点数量:2 ^（h - 1）
总节点数量n=2^h - 1
树高为：h=log(n+1)

完全二叉树

在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。
叶子节点只会出现在最后两层，且最后一层的叶子节点都从左向右填充。
若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。
注：满二叉树就是一个完全二叉树
在这里插入图片描述

性质

假设完全二叉树的高度为h，
那么至少有2^(h-1)个节点
最多有2^h - 1个节点 (满只叉树)
总结点数量为n
2 ^ (h-1) <= n < 2 ^ h - 1
h-1 <= log n < h
h = floor(log n)+1

二叉搜索树（二叉排序树）Binary Search Tree(BST)

二叉搜索树是一个有序树

性质

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树；

如图所示，两棵都是二叉排序树；

如图所示，也是二叉搜索树。
对于二叉搜索树的详细介绍与实现请看我的二叉搜索树（BST）详解这一篇博客。

平衡二叉树

又被称为AVL（Adelson-Velsky and Landis）树

性质

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
在这里插入图片描述
对于平衡二叉树的详细介绍与实现请看我的平衡二叉树详解

红黑树

红黑树是一颗二叉搜索树，它在每个结点上增加了一个存储位来表示结点的颜色，可以是红色或者黑色。
通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是近似平衡的。

五大性质

1、结点必须是红色或者黑色。
2、根节点是黑色。
3、叶子结点（外部结点、空结点，不是传统上认为的那种叶子结点，如图中的那些NIL结点）都是黑色
4、红色结点的子结点都是黑色
于是有推论：
4.1、红色结点的父结点都是黑色
4.2、从根结点到叶子结点的所有路径上不能有两个连续的红色结点
5、从任一结点到叶子结点（外部结点、空结点，不是传统上认为的那种叶子结点，如图中的那些NIL结点）的所有路径都包含相同数目的黑色结点
如图所示：
在这里插入图片描述
对于红黑树的详细介绍与实现请看我的红黑树理论详解与Java实现

B树

B树是为磁盘或其他直接存取的辅助存储设备而设计的一种平衡搜索树。
B树类似于红黑树，但它们在降低磁盘 I/O 操作数方面要更好一些。
许多数据库系统使用 B树或者 B树的变种来存储信息。
B树与红黑树的不同之处在于 B树的结点可以有很多孩子，从数个到数千个。也就是说，一个 B树的“分支因子”可以相当大，尽管它通常依赖于所使用的磁盘单元的特性。
B树类似于红黑树，就是每棵含有n个结点的 B树的高度为 O(lgn)。然而，一棵 B树的严格高度可能比一棵红黑树的高度要小许多，这是因为它的分支因子，也就是表示高度的对数的底数可以非常大。因此，我们也可以使用 B树在时间 O(lgn)内完成一些动态集合的操作。

如示例：
3阶B树：子节点最多为3个
在这里插入图片描述
对于B树的详细介绍与实现请看我的B树（B-tree、B-树）理论详解

二叉树的存储方式

使用指针实现链式存储；
使用数组实现顺序存储；

链式存储

在这里插入图片描述

顺序存储

在这里插入图片描述
对于上图所示的顺序存储：如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i* 2 + 2。
注意：考虑另一种实现方式，0号数组下标不存储，从1号数组下标开始存储树节点，如果父节点的数组下标是 i，那么它的左孩子就是 i * 2，右孩子就是 i* 2 + 1，这种方式更加常用。
在使用时，一定注意数组下标从什么位置开始存储。