(100分)四叉树几个性质的证明
发布网友
发布时间：2022-05-29 02:53
共1个回答
热心网友
时间：2024-10-21 10:29
性质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层上至多有4^(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)。
证明：由性质1深度为k的4叉树至多有
1+4+4^2+…+4^(k-1)=(4^k-1)/(4-1)=(4^k-1)/3
性质3：在一棵4叉树中，若终端结点的个数为n0，度为2结点数为n2，……度为4结点数为n4,则n0=n2+2n3+3n4+1。
证明：因为4叉树中所有结点的度数均不大于4，所以结点总数(记为n)应等于0度、1度，2度，3度和4度结点数之和：
n=n0+n1+n2+n3+n4
另一方面,1度,2度,3度,4度结点分别为有1-4个孩子，故4叉树中孩子结点总数是(包括不是任何结点的孩子的根结点，故下式右边加1)：
n=nl+2n2+3n3+4n4+1
故有n0+n1+n2+n3+n4=nl+2n2+n3+n4，即得n0=n2+2n3+3n4+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所处的层次
改写的性质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.
