1 二叉树的性质
（1）非空二叉树叶子节点树等于双分支节点树加1。
证明：设二叉树上叶子节点树为n0，单分支节点树为n1，双分支节点树为n2（如果没有特别指出，后面均采用这种设定），则有：
a 总节点数 n=n0+n1+n2;
b 总分支数=n1+2*n2;
c 总分支数=总节点数-1。
根据以上三式有：n1 + 2*n2 = n0 + n1 + n2 - 1
即 n0 = n2 + 1。
（2）非空二叉树上第i层上至多有2∧(i - 1)个节点(i≥1)。
（3）高度为h的二叉树至多有2∧h - 1个节点(h≥1)。
（4）对完全二叉树中编号为i的节点(1≤i≤n,n≥1,n为节点数)有：
① 若2i≤n，则编号为i的节点为分支节点，否则为叶子节点。
② 若n为奇数，则每个分支节点都既有左孩子节点，又有右孩子节点；若n为偶数，则编号最大的分支节点（编号为n/2）只有左孩子节点，其余分支节点都有左、右孩子节点。
③ 若编号为i的节点有左孩子节点，则左孩子节点的编号为2i；若编号为i的节点有右孩子节点，则右孩子节点的编号为2i + 1。
④ 除根节点外，当i为偶数时，其双亲节点的编号为i/2，它是双亲节点的左孩子节点；当i为奇数时，其双亲节点的编号为(i-1)/2，它是双亲节点的右孩子节点。
（5）具有n个(n＞0)节点的完全二叉树的高度为 log 2 (n+1) 或 log 2 n + 1。（取对数的最大整数）
