性质1 在二叉树的第i层上至多有2i-1个结点（i≥1）

证明：归纳法 i=1时，命题显然成立，2i-1=20=1 假设所有的1≤j<i都成立，那么证明当j=i时命题也成立： 由假设知，第i-1层上的结点个数为2i-2,而在二叉树中第i层上结点的个数最多是上一层结点数的2倍，即为 2×2i-2=2i-1

 

性质2  深度为k的二叉树至多有2k-1个结点，（k≥1）

 

性质3  对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1

满二叉树：一棵深度为k且有2k-1个结点的二叉树

完全二叉树：深度为k有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，成为完全二叉树。

 

性质4  具有n个结点的完全二叉树的深度为

[log2n]+1

 

性质5 如果对一棵有n个结点的完全二叉树（其深度为 层，每层从左到右），则对任一结点i(1≤i≤n),有：

(1) 如果i＝1，则结点i是二叉树的根，无双亲；若i>1,则其双亲parent(i)是结点 (2) 如果2i>n,则结点i无左孩子(结点i为叶子结点)；否则其左孩子LCHILD(i)是结点2i. (3) 如果2i+1>n,则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i+1.

 

 

 FROM: