|
|
(1)二叉树第i层上的节点数目最多为2i-1(i≥1)个。
|
|
|
(2)深度为k的二叉树至多有2k-1(k≥1)个节点。
|
|
|
(3)在任意一棵二叉树中,若终端节点数为n0,度为2的节点数为n2,则n0=n2+1。
|
|
|
(4)具有n个节点的完全二叉树的深度为[log2n]+1。
|
|
|
(5)对一棵有n个节点的完全二叉树的节点按层次自左至右进行编号,则对任意节点i有以下性质。
|
|
|
.若i=1,则节点i是二叉树的根,无双亲;若i>1,则其双亲为。
|
|
|
.若2i>n,则节点i无左孩子;否则其左孩子为2i。
|
|
|
.若2i+1>n,则节点i无右孩子;否则其右孩子为2i+1。
|
|
|
若深度为k的二叉树有2k-1个节点,则称其为满二叉树。
|
|
|
深度为k、有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树编号从1至n的节点一一对应时,称之为完全二叉树。
|
|
|