大家好，我是王有志。
今天我们要学习的是你编程生涯中不可避免的话题--树，无论是二分搜索树，红黑树，B+树，还是机器学习中的决策树和随机森林，都和树息息相关。
认识一棵树
按照惯例，我会把树的定义放上来，这次也不例外:
树是n（n≥0）个节点的有限集，当n=0时被称为空树。在任意一棵非空树中：
(1)有且仅有一个特定的节点称为根（Root）节点；
(2)当n>1时，其余节点可分为m（m>0）个互不相交的有限集T1，T2...Tn，其中每个集合本身也是一棵树，且称为根的子树（SubTree）。
定义看起来可能会有些晕，下面我们通过一张多叉树的图来理解树中的概念和定义：
一棵多叉树.png
结合定义，相信你已经理解了大部分的概念和定义，那么我们再补充一点点关于树的度的定义。
在树中节点的度指的是节点拥有的子节点的个数，例如，节点B的度是2，节点D的度是3，而树的度指的是树中度最大的节点的度。这么说可能有些拗口，通俗点讲就是，哪个节点拥有最多的子节点，它的子节点个数就是树的度。
二叉树的分类
如果我们按照树的度进行分类，那么树只有两类：二叉树和多叉树。
树的分类.png
树的度小于等于2的称为二叉树，大于2的称为多叉树。
满二叉树
对于满二叉树，国内外的定义有些许的差异：
国内定义为，一棵二叉树中，每层节点的个数都达到最大值，就是满二叉树。即深度为的二叉树，节点个数为
。
国外定义为，一棵二叉树中，非叶子节点都有两个子节点，就是满二叉树。区别在于，国内的定义要求每层节点个数都是满的。
满二叉树.png
完全二叉树
对于一棵二叉树，如果将其每个节点进行从上到下，从左到右依次编号，可以与满二叉树重合，就是完全二叉树。从定义上看，完全二叉树是满二叉树的其中一类子集。
完全二叉树.png
可以看到，完全二叉树并不要求每个非叶子节点都有两个子节点，但是要求“有序”。
平衡二叉树
平衡二叉树是左右子树高度差不超过1的二叉树。
平衡二叉树.png
如果只从结构上来看，平衡二叉树是完全二叉树。区别在于，我们在实现平衡二叉树时，会添加节点之间的排序关系，因此在构建树平衡二叉树的时候，为了保持这种平衡需要进行旋转。
斜树
当一棵树只有左/右子节点时，我们称之为左/右斜树。
左斜树.png
从结构上看，我们也可以认为链表是一种斜树。
二叉树的存储结构
像栈一样，我们也可以实现顺序结构的二叉树或者链式结构的二叉树。实际上链表也是可以通过一维数组描述--静态链表，但是没有必要。
静态结构
二叉树也可以通过一维数组描述。
静态结构.png
我们有一个存储了8个节点的二叉树，将根节点存储在下标为1的位置，记为
节点A的左子节点（节点B）：
节点A的右子节点（节点C）：
同样的我们通过计算可以访问到C的左右子节点：
节点C的左子节点（空节点）：
节点C的右子节点（节点F）：
但是你发现了吗？为了保证公式可用，即便节点C没有左子节点，我们也必须将位置空出来，造成了内存空间的浪费，显然是不够理想的方式。
链式结构
我们也可以创建类似双向链表节点的方式，创建二叉树的节点：
public class TreeNode<E> {
private E element;
private TreeNode<E> leftChild;
private TreeNode<E> rightChild;
}
实际上，这点代码已经可以构建一棵二叉树了。
链式结构.png
和链表一样，只有
TreeNode在使用起来会非常麻烦，要手动实现添加，查找等功能，增加了使用难度。我们可以将功能封装起来只提供接口，不过这不是今天的重点，我们按下不表。
结语
今天我们初步认识了树中的概念和定义，希望通这张图能够让你快速的理解，而不需要死记硬背。
接着我们一起看了4种二叉树结构，这些特殊的结构也是我们学习后面二叉树何种实现的基础。
最后介绍了二叉树的两种存储结构，对于这种动态数据结构通过一维数组的实现方式，我们了解其原理就够了。
你可能会发觉今天画了很多图，是因为我们要学习的数据结构从一维升到了二维，靠想象我已经很难在脑袋中描绘出它们了。
好了，今天就到这里了，Bye~~
网友评论