跳转至

数据结构第六章作业

第一题

设某二叉树的先序遍历序列为: ABCDEFGHI，中序遍历序列为: BCAEDGHFI。 (1) 试画出该二叉树对应的后序线索二叉树； (2) 将（1）所得的二叉树转化为对应的树或森林；

解:

  1. image-20250530085045841
  2. image-20250530085510649

第二题

试编写算法，判断两颗棵以二叉链表表示的二叉树p和q是否相似。

解：

bool Similar(BiTree p, BiTree q) {
    if (p == NULL && q != NULL) return false;
    if (q == NULL && p != NULL) return false;
    if (p == NULL && q == NULL) return true;
    return Similar(p->lc, q->lc) && Similar(p->rc, q->rc);
}

第三题

编写算法判断一棵以二叉链表表示的二叉树是否为完全二叉树。

解：

const int MAX_NODE_SIZE = 100000;
bool JudgeComplete(BiTree root) {
    if (root == NULL) return true;
    BiTree* queue = (BiTree*) malloc(MAX_NODE_SIZE * sizeof(BiTree));
    if (queue == NULL) exit(EXIT_FAILURE);
    int front = 0, back = 0; // [front, back)
    queue[back++] = root;
    bool have_null = false;
    while (front < back) {
        BiTree now = queue[front++];
        if (now == NULL) {
            have_null = true;
            continue;
        } else if (have_null) {
            free(queue);
            return false;
        }
        queue[back++] = now->lc;
        queue[back++] = now->rc;
    }
    free(queue);
    return true;
}

第四题

设计算法求孩子兄弟链表表示的树的度。

解：

int degree(CSTree root) {
    if (root == NULL) return 0;
    int deg = 0, max_deg = 0;
    CSTree p = root->firstchild;
    while (p != NULL) {
        int tmp_deg = degree(p);
        if (tmp_deg > max_deg) max_deg = tmp_deg; 
        p = p->nextsibling;
    }
    if (max_deg > deg) deg = max_deg;
    return deg;
}

第五题

试编写算法，对一棵以孩子-兄弟链表表示的树统计叶子的个数。

解：

int Count(CSTree root) {
    if (root == NULL) return 0;
    if (root->firstchild == NULL) return 1;
    CSTree p = root->firstchild;
    int leaves = 0;
    while (p != NULL) {
        leaves += Count(p);
        p = p->nextsibling;
    }
    return leaves;
}

第六题

一个深度为L的满K叉树有以下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树，如果按层次顺序从1开始对全部结点进行编号，求： 1）各层的结点的数目是多少？ 2）编号为n的结点的双亲结点（若存在）的编号是多少？ 3）编号为n的结点的第i个孩子结点（若存在）的编号是多少？ 4）编号为n的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？ 请给出计算和推导过程。

解：

  1. 设第 \(i\) 层的结点数目为 \(cnt_i\)。则 \(cnt_{1}=1, \space cnt_{i}=K \cdot cnt_{i-1}\)。因此 \(cnt_i=K^{i-1}\)。

  2. 假设编号为 \(n\) 的双亲结点是 \(p\)。每个结点按照编号顺序各自拥有 \(K\) 个孩子，从而 \(p\) 的孩子结点编号 \(n\) 满足： $$ (p-1)\cdot K + 2 \leq n \leq p \cdot K + 1 $$ ​ 从而， $$ p-1 \leq \frac{n-2}{K} < p $$ ​ 即 $$ p=\lfloor \frac{n-2}{K} \rfloor + 1 $$

  3. 编号为 \(n\) 的结点之前有 \(n-1\) 个结点，\((n-1)\cdot K\) 个除根之外的结点+孩子，因此结点 \(n\) 的第 \(i\) 个孩子编号为 \((n-1) \cdot K + 1 + i\)。

  4. 只要不是每个结点最右侧的孩子都有右兄弟。即 \(n \in \set{i | 1\leq i \leq \frac{1-K^L}{1-K} \and i \not= tK+1, \forall t \in N}\)。

第七题

试证明：同一棵二叉树的所有叶子结点，在先序序列、中序序列以及后序序列中都按相同的相对位置出现（即先后顺序相同）。

证明：

记任意两枚叶子结点分别为 \(i\) 和 \(j\)。我们只需说明：在先序、中序、后序三种遍历中，\(i\) 与 \(j\) 的先后关系不会改变。

设 \(u=\mathrm{lca}(i,j)\) 为 \(i\) 与 \(j\) 在这棵树中的最近公共祖先。由于 \(i,j\) 均为叶子，必有 \(u\neq i\) 且 \(u\neq j\)，且 \(i,j\) 分别位于 \(u\) 的两个不同子树中。

不妨设 \(i\) 在 \(u\) 的左子树中，\(j\) 在 \(u\) 的右子树中。

以 \(u\) 为根的子树，先序顺序必先访问根 \(u\)，然后完整遍历其左子树（其中包含叶子 \(i\)），最后遍历其右子树（包含叶子 \(j\)）。因此在先序序列中，\(i\) 肯定出现在 \(j\) 之前。

以 \(u\) 为根的子树，中序顺序先遍历左子树（遇到 \(i\)），再访问根 \(u\)，最后遍历右子树（遇到 \(j\)）。显然仍有 \(i\) 在 \(j\) 之前。

以 \(u\) 为根的子树，后序顺序先遍历左子树（遇到 \(i\)），再遍历右子树（遇到 \(j\)），最后访问根 \(u\)。故在后序序列中，仍是 \(i\) 在 \(j\) 之前。

综上，对任意两叶子结点 \(i,j\)，三种遍历均保持了它们之间的相对先后关系。\(\boxed{}\)

第八题

试给出下列有关并查集的操作序列的运算结果： merge(1,2), merge(3,4), merge(3,5), merge(1,7), merge(3,6), merge(8,9), merge(1,8), merge(3,10), merge(3,11), merge(3,12), merge(3,13), merge(14,15), merge(16,0), merge(14,16), merge(1,3), merge(1,14).

要求：

  1. 对于merge(i,j), 以i作为j的双亲；
  2. 按i和j为根的树的高度实现merge(i,j), 高度大者为高度小者的双亲；
  3. 按i和j为根的树的结点个数实现merge(i,j), 结点个数大者为结点个数小者的双亲。

解：

  1. image-20250530082900094
  2. image-20250530082906784
  3. image-20250530082915505

第九题

设T是一棵二叉树，除叶子结点外，其它结点的度数皆为2， 若T中有6个叶结点，试问：

  1. T树的最大深度Kmax=? 最小可能深度Kmin=?
  2. T树中共有多少非叶结点？
  3. 若叶结点的权值分别为1,2,3,4,5,6。请构造一棵哈曼夫树， 并计算该哈曼夫树的带权路径长度wpl。

解：

  1. Kmax=6，Kmin=4。

  2. 由二叉树的性质知 \(n_2=n_1-1=5\)，又由于非叶结点度数皆为 \(2\)，因此非叶节点个数为\(5\)。

  3. \(wpl = 1 \times 4 + 2 \times 4 + 3 \times 3 + 4 \times 2 + 5 \times 2 + 6 \times 2 = 51\)。