63二叉树 性质6.含有N个结点的二叉链表中,有N+1个空链域。 证明:设二叉树中度为的结点数为ni,二叉树中总结点数为N,因为二叉 树中所有结点均小于或等于2,所以有: N=n0+n1+n2 又由二叉树的链式存储结构定义可知,度为1的结点的空链域个数为1,度 为2的结点的空链域个数为0,度为0的结点的空链域个数为2,设含有N个结 点的二叉树的二叉链表中空链域的个数为M,则有: M=2*n0+1*n1+0*n2=2米n0+n1 又因为:n0=n2+1③ 由①、②、③可得: M=2*n0+n1 n0+n1+n0 n0+n1+n2+1 =N+1 命题得证。6.3 二叉树 性质6. 含有N个结点的二叉链表中，有N+1个空链域。 证明：设二叉树中度为i的结点数为ni，二叉树中总结点数为N，因为二叉 树中所有结点均小于或等于2，所以有： N＝n0＋n1＋n2 ① 又由二叉树的链式存储结构定义可知，度为1的结点的空链域个数为1，度 为2的结点的空链域个数为0，度为0的结点的空链域个数为2，设含有N个结 点的二叉树的二叉链表中空链域的个数为M，则有： M＝2* n0＋1*n1＋0*n2= 2* n0＋n1 ② 又因为： n0＝n2＋1 ③ 由①、②、③ 可得： M＝2* n0＋n1 ＝n0+n1+n0 ＝n0+n1+n2+1 ＝N+1 命题得证