|
|
| 性质1在二叉树的第i层上至多有2i-1个节点（i≥1）。
|
|
|
| 性质2深度为k的二叉树至多有2k-1个节点（k≥1）。
|
|
|
| 性质3对任何一棵二叉树T，如果其终端节点数为n0，度为2的节点数为n2，则n0=n2+1。
|
|
|
| 性质4具有n个节点的完全二叉树的深度为[log2n]+1。
|
|
|
| 性质5如果有n个节点的完全二叉树，对任一节点i（1<i≤n）满足：
|
|
|
| .如果i=1，则i为根，无双亲；若i>1，则i的双亲为[i/2]。
|
|
|
|
|
| .如果2i+1>n，则无右孩子，否则右孩子为2i+1。
|
|
|
| 二叉树的有关性质可推广到k叉树，如：一棵含有n个节点的二叉树共含有n+1个空指针；而一棵含有n个节点的三叉树共含有2n+1个空指针。推而广之，一棵含有n个节点的k叉树共含有（k-1）n+1个空指针。
|
|
|
| 不难看出，在k叉树的第i层上至多有ki-1个节点（i≥1）；深度为H的k叉树至多有（kH-1）/（k-1）个节点（H≥1）。
|
|
|
| 同理，可得到含N个节点和N个叶子节点的完全三叉树的高度分别为：
|
|
|
|
|
|
|
| （1）设含N个节点的完全三叉树的高度为H，则1+3+…+3H-2+1≤N≤1+3+…+3H-1, 3H-1≤2N-1≤3H-2，即H=[log32N-1]+1。
|
|
|
| （2）设含N个叶子节点的完全三叉树的高度为H，则3H-2≤N≤3H-1，即
|
|
|
|
|
|
|
|
|
