### 定义 二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2i-1个结点；深度为k的二叉树至多有2k-1个结点；对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。 ### 图示 :-:  ### 性质 1. 在非空二叉树中，第i层的结点总数不超过2i-1, i>=1。 2. 深度为h的二叉树最多有2h-1个结点(h>=1)，最少有h个结点。 3. 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1。 4. 具有n个结点的完全二叉树的深度为log2(n+1)。 5. 有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系： * [ ] 若I为结点编号则 如果I>1，则其父结点的编号为I/2； * [ ] 如果2I<=N，则其左儿子（即左子树的根结点）的编号为2I；若2I>N，则无左儿子； * [ ] 如果2I+1<=N，则其右儿子的结点编号为2I+1；若2I+1>N，则无右儿子。 6. 给定N个节点，能构成h(N)种不同的二叉树，其中h(N)为卡特兰数的第N项，h(n)=C(2*n, n)/(n+1)。 7. 设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i。 ### 特殊的二叉树 * 斜树：所有的结点都只有左子树或右子树，特点是结点的个数与二叉树的深度相同 * 满二叉树：所有的分支结点(非叶子)都存在左子树和右子树，并且所有的叶子都在同一层(完全对称，非叶子结点的度一定是2，结点数是2^n - 1) * 完全二叉树：允许在满二叉树中去掉若干个最后的结点，但是存在的结点序号一定与满二叉树位置一致(比满二叉树要求低一点，所以满二叉树一定是完全二叉树，反之则不成立。如果某结点的度为1，则该结点只有左孩子) ### 二叉树的存储结构 1) 顺序存储：根据二叉树概念第8点，可以知道完全二叉树的父结点和孩子结点是有算术关系的，所以用一维数组存储很方便。但是对于一般的二叉树则会耗费很多存储空间(如有5层的斜树，只有1，2，4，8，16这几个索引值是存了值的，其他空间都没有作用) 2) 二叉链表：一个结点用(左孩子指针, 右孩子指针, 数据域)来表示，如果没有孩子结点，则指针域指向空即可，可以节省很多空间(当然如果有必要指向父结点，也可以构造三叉链表，略)