二叉树的特殊形态
满二叉树（Full Binary Tree）一棵深度为k且有k个结点的二叉树
特点二叉树的所有分支结点都存在左子树和右子树
特点二叉树的所有叶子结点都在同一层上
完全二叉树（Complete Binary Tree）深度为k的有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从至n的结点一一对应
特点叶子结点只可能在层次最大的两层上出现
特点对任一结点若其右分支下的子孙的最大层次为L则其左分支下的子孙的最大层次必为 L 或 L+
二叉树的性质
性质 在二叉树的第i层上至多有i个结点（i≥）
证明归纳法
i=时只有一个根结点显然i==是对的
现在假定对所有的j≤j＜i命题成立即第j层上至多有j个结点那么可以证明j=i时命题也成立
由归纳假设第i层上至多有i个结点由于二叉树的每个结点的度至多为故在第i层上的最大结点数为第i层上的最大结点数的倍即×i= i
性质 深度为k的二叉树至多有k个结点（k≥）
证明
由性质可见深度为k的二叉树的最大结点数为
性质 对任何一棵二叉树T如果其终端结点数为n度为的结点数为n则
n=n＋
证明:
设n为二叉树T中度为的结点数
∵ 二叉树中所有结点的度均小于或等于
∴ n=n+n+n()
设B为分支总数则n=B+
∵ 这些分支是由度为或的结点射出的
∴ B=n+n
∴ n=n+n+()
由式()和()得
n=n+
性质 具有n个结点的完全二叉树的深度为「logn」+
证明:
假设深度为k则根据性质和完全二叉树的定义有
k≤n＜k
∴ k≤logn＜k
∵ k是整数
∴ k=「logn」+
性质 如果对一棵有n个结点的完全二叉树（其深度为「logn」+）的结点按层
序编号（从第层到第「logn」+层每层从左到右）则对任一结点i
（≤i≤n）有
１如果 i=则结点i是二叉树的根无双亲如果 i＞则其双亲PARENT(i)是结点「i/」
２如果i＞n则结点i无左孩子（结点i为叶子结点）否则其左孩子LCHILD(i)是结点i
３如果i+＞n则结点i无右孩子否则其右孩子RCHILD(i)是结点i+
