树结构中，结点总数（包括根和叶子）=边数（等于度）+1
1.二叉树 性质1：对任何一颗二叉树T，如果其终端节点数为n0,度为2的节点数为n2，则n0 = n2+1; 性质2：具有n个结点的完全二叉树的深度为|log2 (n)|+1
二叉树进行层次遍历，应借助一个队列，二叉树的先序、中序、后序的非递归遍历需要用到栈。
（1）完全二叉树 一、叶子结点只可能在最大的两层上出现,对任意结点，若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次必为L 或 L+1；
完全二叉树的存储结构通常采用顺序存储结构。 完全二叉树中，非叶子结点顶多没有右孩子，没有左孩子的话，就表示没有子节点。
对完全二叉树的编号是由上而下，由左而右进行的，所以若某节点无左孩子，则必然无右孩子。即为叶子结点。 二、出于简便起见,完全二叉树通常采用数组而不是链表存储,其存储结构如下:
var tree:array[1..n]of longint;{n:integer;n>=1}
对于tree[i]，有如下特点：
（1）若i为奇数且i>1，那么tree[i]的左兄弟为tree[i-1]；
（2）若i为偶数且i<n，那么tree[i]的右兄弟为tree[i+1]；
（3）若i>1，tree[i]的双亲为tree[i div 2]；
（4）若2*i<=n，那么tree[i]的左孩子为tree[2*i]；若2*i+1<=n，那么tree[i]的右孩子为tree[2*i+1]；
（5）若i>n div 2,那么tree[i]为叶子结点（对应于（3））；
（6）若i<(n-1) div 2.那么tree[i]必有两个孩子（对应于（4））。
特别地：满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
完全二叉树叶子节点的算法
如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应，这棵二叉树称为完全二叉树。
可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可 知：n0＝n2＋1，则n= n0＋n1＋n2（其中n为完全二叉树的结点总数），由上述公式把n2消去得：n= 2n0+n1－1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0＝（n＋1）/2或n0＝n/2，合并成一个公式：n0＝（n＋1） /2 ，就可根据完全二叉树的结点总数计算出叶子结点数。
哈夫曼树是一种最优二叉树，利用哈夫曼树寻找一颗最佳判定树，即总的比较次数最少的判定树。 所以，哈夫曼树中不存在结点度为1的结点。 哈夫曼树不是满二叉树，是正则二叉树（也叫正规二叉树），其中只有度为0和度为2的结点，因为n0 = n2 + 1，所以n个叶子的正则二叉树自然只有2n-1个结点。至于满二叉树当然也是正则二叉树的特例。
二叉链表 性质1：在n个结点的二叉链表中，有n+1个空指针域 利用中序遍历，并结合先序遍历或后序遍历就能重新构造二叉树（单一遍历序列无法构造 二叉树）。
2.AVL平衡二叉树 定义：平衡二叉树或为空树,或为如下性质的二叉排序树:
（1）左右子树深度之差的绝对值不超过1;
（2）左右子树仍然为平衡二叉树.
平衡因子BF=左子树深度－右子树深度.
平衡二叉树每个结点的平衡因子只能是1，0，-1。若其绝对值超过1，则该二叉排序树就是不平衡的。
构造与调整方法平衡二叉树的常用算法有红黑树、AVL、Treap、伸展等。最小平衡二叉树的节点公式如下：F(n) = F(n-1)+F(n-2)+1.
平衡二叉树的缺点： 插入和删除运算变得复杂化，从而降低了他们的运算速度。
平衡二叉树的时间复杂度是log(n)，如果二叉树的元素个数为n，那么不管是对树进行插入节点、查找、删除节点都是log(n)次循环调用就可以了。它的时间复杂度相对于其他数据结构如数组等是最优的。 3.RBT红黑树 AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多；
红黑是弱平衡的，用非严格的平衡来换取增删节点时候旋转次数的降低；
所以简单说，搜索的次数远远大于插入和删除，那么选择AVL树，如果搜索，插入删除次数几乎差不多，应该选择RB树。
红黑树上每个结点内含五个域，color，key，left，right，p。如果相应的指针域没有，则设为NIL。
一般的，红黑树，满足以下性质，即只有满足以下全部性质的树，我们才称之为红黑树：
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
红黑树插入操作的平均时间复杂度为O（logn）,最坏时间复杂度为O（logn）;
4.B-树
是一种平衡多路搜索树（并不是二叉的）：
1.定义任意非叶子结点最多只有M个儿子；且M>2；
2.根结点的儿子数为[2, M]；
3.除根结点以外的非叶子结点的儿子数为[M/2, M]；
4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
5.非叶子结点的关键字个数=指向儿子的指针个数-1；
6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的
子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
8.所有叶子结点位于同一层；
5.B+树
B+树是B-树的变体，也是一种多路搜索树：
1.其定义基本与B-树同，除了：
2.非叶子结点的子树指针与关键字个数相同；
3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树
（B-树是开区间）；
5.为所有叶子结点增加一个链指针；
6.所有关键字都在叶子结点出现；
如：（M=3）
B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在
非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；
B+的特性：
1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好
是有序的；
2.不可能在非叶子结点命中；
3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储
（关键字）数据的数据层；
4.更适合文件索引系统；比如对已经建立索引的数据库记录，查找10<=id<=20，那么只要通过根节点搜索到id=10的叶节点，之后只要根据叶节点的链表找到第一个大于20的就行了，比B-树在查找10到20内的每一个时每次都从根节点出发查找提高了不少效率。
B+树插入操作的平均时间复杂度O（logn）,最坏时间复杂度为O（logn）;