考研昨天结束了，专业课我考得不好，是408，引人注目的莫过于每年的数据结构算法题了，13分！今年是求二叉树的带权路径长度，我就写了算法思想，代码空白，因为时间来不及了，慌了，是心态的问题吧，做到最后有种天要塌下来的感觉，回来后很沮丧，因为我觉得自己是可以写出程序的，不服啊！
下面说说这道题目。树的带权路径长度定义：树中所有叶子的带权路径长度之和。比如下面这棵树，WPL就是4*2+3*1 = 11
1、深搜（前序遍历）的算法可以用递归，程序简洁，先判断当前的根是不是叶子，若是则加上该叶子的带权路径长度，叶子的深度可以作为参数传递得到，求深度是个必须解决的问题。然后对左子树、右子树递归进行。因为是递归，所以我用了全局变量来记录部分和，不知道有没有不用全局变量的方法。< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+MqGiuePL0aOosuO0zrHpwPqjqdbQtcTE0cziysfH88O/suO1xMnutsijrM7Sss6/vMHLzfW1wMrpyc+1xMvjt6ijrNPDwcvSu7j2IGxhc3QgseTBv8C0vMfCvMO/suO1xNfu09K94bXjo6zO0r71tcPV4rj2t723qLrcx8mjrNPQtePE0c/roaM8L3A+CjxwPsG9uPbL47eotcTKtc/WyOfPwqOovai1xMrHyc/D5sTHv8PK96OpPC9wPgo8cD48cHJlIGNsYXNzPQ=="brush:java;">/******************************************************************** created: 2014/01/06 created: 14:42 file base: main file ext: cpp author: Justme0 (http://blog.csdn.net/Justme0) purpose: 求二叉树的带权路径长度 *********************************************************************/ #define _CRT_SECURE_NO_WARNINGS #include
#include
#include
using namespace std; /* ** 二叉链表的结点定义 */ struct Node { Node *left; Node *right; int weight; Node() : left(NULL), right(NULL), weight(0) {} bool has_left() const { return NULL != left; } bool has_right() const { return NULL != right; } bool is_leaf() const { return !has_left() && !has_right(); } }; #pragma region 深搜 int wpl_dfs = 0; /* ** 前序遍历求树的带权路径长度（weighted path length） */ void DFS(Node *root, int depth) { if (root == NULL) { // root 为空树 return ; } if (root->is_leaf()) { wpl_dfs += root->weight * depth; } DFS(root->left, depth + 1); DFS(root->right, depth + 1); } int get_
WPL_dfs(Node *root) { DFS(root, 0); return wpl_dfs; } #pragma endregion 深搜 #pragma region 广搜 /* ** 层次遍历求树的带权路径长度（weighted path length） */ int get_WPL_bfs(Node *root) { if (root == NULL) { // root 是空树 return 0; } int wpl_bfs = 0; int depth = 0; Node *last = root; // last 为每层最右结点的地址，用于确定高度 queue
Q; Q.push(root); do { Node *p = Q.front(); Q.pop(); if (p->is_leaf()) { wpl_bfs += p->weight * depth; } else { if (p->has_left()) { Q.push(p->left); } if (p->has_right()) { Q.push(p->right); } } if (p == last && !Q.empty()) { // 此时处理到该层的最右结点 last = Q.back(); // 队尾恰好是下一层的最右结点的地址 ++depth; } } while (!Q.empty()); return wpl_bfs; } #pragma endregion 广搜 /* ** 输入前序序列动态生成树 */ void creat_tree(Node *&root) { int info; cin >> info; if (info == -1) { root = NULL; } else { root = new Node; root->weight = info; creat_tree(root->left); creat_tree(root->right); } } /* ** 后序遍历释放树 */ void free_tree(Node *&root) { if (root == NULL) { return ; } free_tree(root->left); free_tree(root->right); delete root; root = NULL; } int main(int argc, char **argv) { freopen("cin.txt", "r", stdin); Node *tree = NULL; creat_tree(tree); int dfs_wpl = get_WPL_dfs(tree); int bfs_wpl = get_WPL_bfs(tree); assert(dfs_wpl == bfs_wpl); cout << "深搜：WPL=" << dfs_wpl << endl; cout << "广搜：WPL=" << bfs_wpl << endl; free_tree(tree); return 0; } /*cin.txt 1 2 -1 4 -1 -1 3 -1 -1 */
btw，我考试时写的算法思想是广搜，然后一想到程序中得用队列，还得考虑深度，我就蒙了，只写了个函数头，希望能施舍一点分。。。