408计算机考研树大题

2014年

2014-41

【2014年题41】（13 分）二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树 T，采用二叉链表存储，结点结构如下：

其中叶结点的 weight 域保存该结点的非负权值。设 root 为指向 T 的根结点的指针，请设计求 T 的 WPL 的算法，要求：

1）给出算法的基本设计思想。

2）使用 C 或 C++语言，给出二叉树结点的数据类型定义。

3）根据设计思想，采用 C 或 C++语言描述算法，关键之处给出注释。

解析：

1）算法基本设计思想

二叉树的带权路径长度WPL = 所有叶子结点的权值 × 该叶子到根的路径长度之和。对二叉树进行 递归先序遍历 ，遍历的时候维护当前结点的路径深度（路径长度）：

1. 如果当前结点是叶子结点（left==null && right==null），把 weight × depth 累加到总WPL；
2. 如果不是叶子，则递归遍历左子树、右子树，递归时深度+1；
3. 空树直接返回0。

2）结点类型定义（C语言）

c
typedef struct BiTNode {
    struct BiTNode *left;
    int weight;
    struct BiTNode *right;
} BiTNode, *BiTree;

3）算法代码