|
|
|
性质1：二叉树第i层（i≥1）上至多有2i-1个结点。
|
|
|
|
|
|
性质2：深度为k的二叉树至多有2k-1个结点（k≥1）。
|
|
|
由性质1，每一层的结点数都取最大值即得 ，因此性质2得证。
|
|
|
|
性质3：对任何一棵二叉树，若其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
|
|
|
|
对二叉树中结点的度求总和也就是分支的数目，而二叉树中结点总数恰好比分支数目多1，因此性质3得证。
|
|
|
性质4：具有n个结点的完全二叉树的深度为 。
|
|
|
|
若深度为k的二叉树有2k-1个结点，则称其为满二叉树。可以对满二叉树中的结点进行连续编号，约定编号从根结点起，自上而下、自左至右依次进行。即根结点的编号为1，其左孩子结点编号为2，右孩子结点编号为3，以此类推，编号为i的结点的左孩子编号为2i、右孩子编号为2i+1。
|
|
|
|
当深度为k、有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应时，称之为完全二叉树。高度为3的满二叉树和完全二叉树如下图（a）~（d）所示，显然，满二叉树也是完全二叉树。
|
|
|
|
|
|
|
|
在一个高度为h的完全二叉树中，除了第h层（即最后一层），其余各层都是满的。在第h层上的结点必须从左到右依次放置，不能留空。下图所示的高度为3的二叉树都不是完全二叉树，其中，（a）中4号结点、（b）中5号结点、（c）中6号结点的左边有空结点。
|
|
|
|
|
|
|
显然，具有n个结点的完全二叉树的高度为 。
|
|
|
