作业帮（100分）四叉树几个性质的证明第一个性质我参照2叉树马马虎虎证明出来了,剩下还有3个未完成的.后面附上2叉树类似性质的证明.请注意,很多式子中为上标,比如下面的i-1是4的平方的意思性
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/03 03:04:07
（100分）四叉树几个性质的证明第一个性质我参照2叉树马马虎虎证明出来了,剩下还有3个未完成的.后面附上2叉树类似性质的证明.请注意,很多式子中为上标,比如下面的i-1是4的平方的意思性
（100分）四叉树几个性质的证明
第一个性质我参照2叉树马马虎虎证明出来了,剩下还有3个未完成的.
后面附上2叉树类似性质的证明.请注意,很多式子中为上标,比如下面的i-1是4的平方的意思
性质1：4叉树第i层上的结点数目最多为4 (i-1) (i≥1).
证明：用数学归纳法证明：归纳基础：i=1时,有4（i-1）=1.因为第1层上只有一个根结点,所以命题成立.归纳假设：假设对所有的j(1≤jm,则结点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
（100分）四叉树几个性质的证明第一个性质我参照2叉树马马虎虎证明出来了,剩下还有3个未完成的.后面附上2叉树类似性质的证明.请注意,很多式子中为上标,比如下面的i-1是4的平方的意思性
首先指出你的精神十分可佳,能想到将二叉树的性质推广到任意叉树的情况,你的性质1的证明完全正确,性质2结论有点问题,性质4我还没能完全理会.我做了标记?,是否能表述的更清楚一点.是否编号类似二叉树从上到下从左到右进行?,我现将性质4改写了一下,不知是否符合你的原意?
性质1：4叉树第i层上的结点数目最多为4^(i-1)(i≥1).
证明：用数学归纳法证明：归纳基础：i=1时,有4^（i-1）=1.因为第1层上只有一个根结点,所以命题成立.归纳假设：假设对所有的j(1≤jm,则结点i没有直接“左孩子”；否则其直接“左孩子”结点的编号为4*i-2.(2)如果4*i-2+count>m,则结点i没有直接“右孩子”；否则其直接“右孩子”结点的编号为4*i-2+count.其中count表示为4high/2high,high为结点i所处的层次
改写的性质4如下:
性质4：在完全4叉树中,每个结点最左边的孩子称为该结点的“左孩子”,最右边的孩子称为该结点的“右孩子”.然后对完全4叉树从上到下从左到右按层进行编号,编号为i的结点(1≤i≤m,m≥1,m为结点数）的 “左、右孩子”有如下结论：(1)如果4i-2>m,则结点i没有直接“左孩子”；否则其直接“左孩子”结点的编号为4i-2.(2)如果4i+1>m,则结点i没有直接“右孩子”；否则其直接“右孩子”结点的编号为4i+1.
证明：对完全4叉树从上到下从左到右按层进行编号,不难看出编号为i的结点如果它的“左孩子”存在,则其“左孩子”的编号为4i-2,同理如果它的“右孩子”存在,则“右孩子”的编号为4i+1,如果结点数为m,则编号不会超过m,因此如果4i-2>m,则结点i没有“左孩子”,否则“左孩子”的编号应为4i-2,然而4i-2大于了m,即超过了编号的范围,矛盾,即4i-2>m时,则结点i没有“左孩子”,同理如果4i+1>m也没有“右孩子”.如果没有上面4i-2>m或4i+1>m的限制,则“左孩子”或“右孩子”存在,此时“左右孩子”的编号分别为4i-2 和4i+1.