5.3.2 二叉树的性质

二叉树具有如下性质。

（1）在二叉树中，第i层的节点总数不超过2i−1。

（2）深度为h的二叉树最少有h个节点，最多有2h−1个节点（h≥1）。

（3）对于任意一棵二叉树来说，如果叶节点数为n0，且度数为2的节点总数为n2，则n0=n2+1。

（4）有n个节点的完全二叉树的深度为int(log2n)+1。

（5）存在一棵有n个节点的完全二叉树，如果各节点以顺序方式存储，那么节点之间有如下关系。

① 如果i=1，则节点i为根，无父节点；如果i＞1，则父节点编号为trunc(n/2)。

② 如果2i≤n，则左儿子（即左子树的根节点）的节点编号为2i；如果2i＞n，则无左儿子。

③ 如果2i+1≤n，则右儿子的节点编号为2i+1；如果2i+1＞n，则无右儿子。

（6）假设有n个节点，能构成h(n)种不同的二叉树，则h(n)为卡特兰数的第n项，h(n)=C(n,2n)/(n+1)。