爱华网（2）深度为m的二叉树最多有2m-1个结点，最少有m个结点；
（3）对于任意一棵二叉树，度为0的结点（即叶子结点）总是比度为2的结点多一个；即如果其叶子结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
（4）具有n个结点的二叉树，其深度至少为[log2n]+1,其中[log2n]+1表示取log2n的整数部分；
（5）给定N个节点，能构成h(N)种不同的二叉树；h(N)为卡特兰数的第N项。h(n)=C(n,2*n)/(n+1)。
（6）具有n个结点的完全二叉树的深度为[log2n]+1；
（7）设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，….n给结点进行编号（k=1,2….n），有以下结论：
①若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为INT(k/2)；
②若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（也无右子结点）；
③若2k+1≤n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。
性质1在二叉树的第i层上至多有2i-1个结点(i>=1)。
证明采用归纳法证明此性质。
当i=1时，只有一个根结点，2i-1=20=1,命题成立。
现在假定对所有的j，1<=j<i,命题成立，即第j层上至多有2j-2个结点，
那么可以证明j＝i时命题也成立。由归纳假设可知，第i－1层上至多有2i-2个结点。
由于二叉树每个结点的度最大为2，故在第i层上最大结点数为第i－1
层上最大结点数的二倍，即2×（2i-2）＝2i-1。
性质2深度为k的二叉树至多有2k－1个结点（k>=1)。
证明第i层的结点数为xi（1≤i≤k），深度为k的二叉树的结点数为M，xi最多为2i-1，则有：
性质3对于一棵非空的二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有n0＝n2＋1。
证明设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，所以有：
N＝n0＋n1＋n2(5-1)
再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数，则有：
N＝B＋1。
由于这些分支都是由度为1和2的结点发出的，所以有：
B＝n1+2*n2
N＝B＋1＝n1＋2×n2＋1(5-2)
由式(5-1)和(5-2)得到：
n0＋n1＋n2=n1＋2×n2＋1
n0＝n2＋1
性质4具有n个结点的完全二叉树的深度k为。
证明设所求完全二叉树的深度为k,根据完全二叉树的定义和性质2可知，k-1层满二叉树的结点个数为n时，有
2k－1－1<n≤2k-1
即2k－1≤n<2k
对不等式取对数，有
k－1≤log2n<k
由于k是整数，所以有k-1＝，k=,结论成立。
性质5如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第+1层，每层从左到右),则对任一结点i（1<=i<=n),有：
（1）如果i＝1，则结点i无双亲，是二叉树的根；如果i>1，则其双亲是结点。
（2）如果2i>n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。
（3）如果2i＋1>n，则结点i无右孩子；否则，其右孩子是结点2i＋1。
此外，若对二叉树的根结点从0开始编号，则相应的i号结点的双亲结点的编号为（i－1）/2，左孩子的编号为2i＋1，右孩子的编号为2i＋2。
此性质可采用数学归纳法证明。证明略。
这个性质是一般二叉树顺序存储的重要基础。
下面介绍两种特殊形态的二叉树：满二叉树和完全二叉树。
一棵深度为k且由2k-1个结点的二叉树称为满二叉树。图5-3（a）就是一棵满二叉树，对结点进行了顺序编号。图5-3（b）图则不是满二叉树，因为，虽然其所有结点要么是含有左右子树的分支结点，要么是叶子结点，但由于其叶子未在同一层上，故不是满二叉树。
(a)一棵满二叉树(b)一棵非满二叉树
图5-3满二叉树和非满二叉树示意图
一棵深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。如图5-4（a）所示为一棵完全二叉树，图5-4（b）为一棵非完全二叉树。
(a)一棵完全二叉树(b)一棵非完全二叉树
图5-4完全二叉树和非完全二叉树示意图
二叉树的遍历
（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树；
（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树；
（3）后序遍历（LRD），首先遍历左子树，然后遍历右子树，最后访问根结点。
完全二叉树的定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。
特点：叶子结点只可能在层次最大的两层上出现；对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l或l+1
满二叉树：一棵深度为k，且有2的(k)次方－1个节点的二叉树
特点：每一层上的结点数都是最大结点数
满二叉树肯定是完全二叉树
完全二叉树不一定是满二叉树
满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。
完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。
二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。
