【摘要】：二叉树的第i层上至多有2i-1（i≥1）个结点。若已知i-1层上结点数至多有2（i-1）-1=2i-2个，而又由于二叉树每个结点的度数最大为2，因此第i层上结点数至多为第i-1层上结点数的2倍。若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则必有n0=n2+1。具有n个结点的完全二叉树的深度为「log2n」+1。
（1）二叉树的第i层上至多有2i-1（i≥1）个结点。
证明：用归纳法。
若i=1，则结点数为2i-1＝20＝1（个）。
若已知i-1层上结点数至多有2（i-1）-1=2i-2个，而又由于二叉树每个结点的度数最大为2，因此第i层上结点数至多为第i-1层上结点数的2倍。即
2×2i-2=2i-1
证毕。
（2）深度为h的二叉树中至多含有2h-1个结点。
证明：利用性质（1）的结论可得，在深度为h的二叉树中至多含有的结点数为
证毕。
（3）若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则必有n0=n2+1。
证明：设n1为度为1的结点数，则总结点数n为：
在二叉树中，除根结点外，其他结点都有一个指针与其双亲相连，若指针数为b，则满足：
而这些指针又可以看作是由度为1和度为2的结点与它们孩子之间的联系，因此，b和n1，n2之间的关系为：(https://www.xing528.com)
由式（2）、式（3）可得：
再比较式（1）、式（4）可得：
n0=n2+1
证毕。
（4）具有n个结点的完全二叉树的深度为「log2n」+1（其中「x」表示不大于x的最大整数）。
（5）若对有n个结点的完全二叉树进行顺序编号（1≤i≤n），那么对于编号为i（i≥1）的结点：
①当i=1时，该结点为根，它无双亲结点。
②当i＞1时，该结点双亲结点的编号为「i/2」。
③若2i≤n，则有编号为2i的左孩子，否则没有左孩子。
④若2i+1≤n，则有编号为2i+1的右孩子，否则没有右孩子。
（证明略）
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
