Question

数据结构习题5

写出二叉树性质的证明

Answer 1

第一个性质我参照2叉树马马虎虎证明出来了，剩下还有3个未完成的。
后面附上2叉树类似性质的证明。请注意，很多式子中为上标，比如下面的i-1是4的平方的意思

性质1：4叉树第i层上的结点数目最多为4 (i-1) (i≥1)。
证明：用数学归纳法证明：归纳基础：i=1时，有4（i-1）=1。因为第1层上只有一个根结点，所以命题成立。 归纳假设：假设对所有的j(1≤j<i)命题成立，即第j层上至多有4（j-1）个结点，证明j=i时命题亦成立。 归纳步骤：根据归纳假设，第i-1层上至多有2（i-2）个结点。由于四叉树的每个结点至多有4个孩子，故第i层上的结点数至多是第i-1层上的最大结点数的4倍。即j=i时，该层上至多有4×4（i-2）=4（i-1）个结点，故命题成立。
性质2：深度为k的4叉树至多有4(k-1)/3个结点(k≥1) 。
性质3：在一棵4叉树中，若终端结点的个数为m0，度为2结点数为m2，……度为4结点数为m4,则m0=m2+2m3+3m4+1。
性质4：在完全4叉树中，如果将其每一层中的数据依据分块映射为二叉树中同一层的数据结构形式，那么我们同样可以类似定义完全4叉树的“左、右孩子”。其中，完全4叉树经过映射后，每一个根结点的左边部分的第一个结点为其直接“左孩子”，对应右边部分的第一个结点为其直接“右孩子”。 完全4叉树中编号为i的结点(1≤i≤m，m≥1,m为结点数）的直接“左、右孩子”有如下结论：(1)如果4*i-2>m，则结点i没有直接“左孩子”；否则其直接“左孩子”结点的编号为4*i-2。(2)如果4*i-2+count>m，则结点i没有直接“右孩子”；否则其直接“右孩子”结点的编号为4*i-2+count。其中count表示为4high/2high,high为结点i所处的层次

二叉树具有以下重要性质：
性质1 二叉树第i层上的结点数目最多为2i-1(i≥1)。
证明：用数学归纳法证明：
归纳基础：i=1时，有2i-1=20=1。因为第1层上只有一个根结点，所以命题成立。
归纳假设：假设对所有的j(1≤j<i)命题成立，即第j层上至多有2j-1个结点，证明j=i时命题亦成立。
归纳步骤：根据归纳假设，第i-1层上至多有2i-2个结点。由于二叉树的每个结点至多有两个孩子，故第i层上的结点数至多是第i-1层上的最大结点数的2倍。即j=i时，该层上至多有2×2i-2=2i-1个结点，故命题成立。
2 二叉树的性质
性质2 深度为k的二叉树至多有2k-1个结点(k≥1)。
证明：在具有相同深度的二叉树中，仅当每一层都含有最大结点数时，其树中结点数最多。因此利用性质1可得，深度为k的二叉树的结点数至多为：
20+21+…+2k-1=2k-1
故命题正确。
3 二叉树的性质
性质3 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。
证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)应等于0度结点数、1度结点(记为n1)和2度结点数之和：
n=no+n1+n2 (式子1)
另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：
nl+2n2
树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为：
n=n1+2n2+1 (式子2)
由式子1和式子2得到：
no=n2+1

Answer 2

上面的就是百度的，网址如下： http://student.zjzk.cn/course_ware/data_structure/web/shu/shu6.2.2.htm这里更全