计算机学科专业基础2014 真题档案

【答案】

（1）算法基本设计思想
方法一：基于先序递归遍历。定义递归函数，将当前结点的深度作为参数传递。若结点为叶子结点，则累加 深度 * 权值 到结果；否则，递归遍历其左右子树，并将深度参数加1。
方法二：基于层次遍历（BFS）。使用队列实现层次遍历，并记录当前层数 deep。利用指针 lastNode 标记当前层最后一个结点。当遍历到叶子结点时，累加 deep * 权值。每当处理完 lastNode 结点，就更新 lastNode 为下一层的最后一个结点，并将 deep 加1。

（2）二叉树结点的数据类型定义（C语言）

typedef struct BiTNode {
    int weight;                     // 存储权值
    struct BiTNode *lchild, *rchild; // 左、右孩子指针
} BiTNode, *BiTree;

（3）算法描述（C语言）
方法一：先序递归

int wpl_PreOrder(BiTree root, int deep);
int wpl_LevelOrder(BiTree root);

int WPL(BiTree root) {
    return wpl_PreOrder(root, 0); // 基于先序遍历
    // 如需使用层次遍历，可改为：return wpl_LevelOrder(root);
}

int wpl_PreOrder(BiTree root, int deep) {
    if (root == NULL) return 0; // 空树返回0
    if (root->lchild == NULL && root->rchild == NULL)
        return deep * root->weight;
    return wpl_PreOrder(root->lchild, deep + 1)
         + wpl_PreOrder(root->rchild, deep + 1);
}

方法二：层次遍历

int wpl_LevelOrder(BiTree root) {
    BiTree q[MaxSize]; // 声明队列，end1为头指针，end2为尾指针
    int end1, end2 = 0;
    end1 = end2 = 0;
    int wpl = 0, deep = 0;
    BiTree lastNode;
    BiTree newlastNode;
    lastNode = root;
    newlastNode = NULL;
    q[end2++] = root;
    while (end1 != end2) {
        BiTree t = q[end1++];
        if (t->lchild == NULL && t->rchild == NULL) {
            wpl += deep * t->weight;
        }
        if (t->lchild != NULL) {
            q[end2++] = t->lchild;
            newlastNode = t->lchild;
        }
        if (t->rchild != NULL) {
            q[end2++] = t->rchild;
            newlastNode = t->rchild;
        }
        if (t == lastNode) {
            lastNode = newlastNode;
            deep += 1;
        }
    }
    return wpl; // 返回wpl
}