二叉树

树的基本定义：

数是由(n  – 1 )  >=  1 个有限的结点组成的有层次关系的集合

树具有的特点：

• 每个结点都会有零或多个子结点
• 没有父节点的结点是根结点
• 每一个非根结点只有一个父结点
• 每个结点及其后代结点整体可以看作成一棵树，称为当前结点的父结点的一颗子树

树的相关术语：

结点的度：

一个结点含有的子节点的数量称为结点的度

叶节点：

度为0的节点称为叶结点， 也可以叫做终端结点

分支节点：

度不为0的结点称为分支结点，也可以叫做非终端结点

结点的层次：

从根节点开始根的层次是1，以此类推

结点的层次序号：

将树中的结点，按照从上往下，同层按照从左往右的次序排成一个线性序列，排成连续的自然数

树的度：

树中所有结点中度最大值

树的深度(高度)

树中结点的最大层次

森林：

m(m >= 0)个不相交的树的集合，将一颗空树的根结点删除，树就变成了一个森林，给森林同一加一个根结点，森林就变成了树

满二叉树(2^n-1)：

如果一个二叉树的每层的结点都达到最大值，这个二叉树就是满二叉树

完全二叉树：
叶结点只能出现在最下层或者次下层，并且最下面的的结点都集中在最左边的若干位置的二进制

插入put方法的实现：

如果当前树没有结点，就将新加入的结点作为根结点

如果插入的结点的键小于根结点的键，则成为左子结点

如果插入的结点的键大于根节点的键，则成为右子结点

如果插入的结点的键大于根结点或者小于根结点的键并且已经有了一个键相同的元素，则替换原子节点