|
|
性质1:在二叉树的第i层上至多有2i-1个结点(i≥1)。
|
|
|
性质2:深度为k的二叉树至多有2k-1个结点(k≥1)。
|
|
|
性质3:对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0= n2+1。
|
|
|
性质4:具有n个结点的完全二叉树的深度为。
|
|
|
性质5:如果有n个结点的完全二叉树,对任一结点i(1
|
|
|
.如果i=1,则i为根,无双亲;若i>1,则i的双亲为。
|
|
|
|
.如果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,即。
|
|
|
(2)设含N个叶子结点的完全三叉树的高度为H,则3H-2≤N≤3H-1,即
|
|
|
|
可进一步推广,含N个结点的完全k叉树的高度为。
|
|
|