一、二叉树
1、二叉树的概念
二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree），其次序不能任意颠倒。
2、性质
（1）若二叉树的层次从0开始，则在二叉树的第i层至多有2^i个结点(i>=0)；
（2）高度为k的二叉树最多有2^(k+1) - 1个结点(k>=-1)。 (空树的高度为-1)；
（3）对任何一棵二叉树，如果其叶子结点(度为0)数为m, 度为2的结点数为n, 则m = n + 1。
二、几种特殊的二叉树
1、满二叉树
所有叶结点同处于最底层（非底层结点均是内部结点），一个深度为k(>=-1)且有2^(k+1) - 1个结点。如图（图来源于veil的博客）：
2、完全二叉树
叶结点只能出现在最底层的两层，且最底层叶结点均处于次底层叶结点的左侧。规模为n的完全二叉树，高度为
3、平衡二叉树
平衡二叉树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci(斐波那契)数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。
对于平衡二叉树要特别注意的是，不要求非叶节点都有两个子结点，仅要求两个子树的高度差的绝对值不超过1，或者为空树。
三、存储方式
存储的方式和图一样，有链表和数组两种，用数组存访问速度快，但插入、删除节点操作就比较费时了。实际中更多的是用链来表示二叉树的。
四、遍历方式
三种遍历方式 访问节点的顺序是一致的，不同之处在于，有的遍历流程把访问到的节点暂存起来，达成某种条件后再将节点输出。约定， 根节点V, 其左孩子为L, 右孩子为R, 那么遍历顺序可以记为：
Pre-Order Traversal ： 到达一个节点后，即刻输出该节点的值，并继续遍历其左右子树。 VLR
In-Order Traversal ： 到达一个节点后，将其暂存，遍历完左子树后，再输出该节点的值，然后遍历右子树LVR
Post-Order Traversal: 到达一个节点后，将其暂存，遍历完左右子树后，再输出该节点的值。 LRV
先序遍历，中序遍历，后序遍历，这个“顺序”指的是输出父节点的顺序，不是访问的顺序，也不是简单的按照二叉树“从左往右”、“从上往下”等。
遍历结果：
