【408DS算法题】036基础-14年真题_求二叉树的WPL

本文主要是介绍【408DS算法题】036基础-14年真题_求二叉树的WPL，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

真题题目

二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T ,采用二叉链表存储， 结点结构如下：
其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针， 请设计求T的WPL的算法， 要求：
1 - 给出算法的基本设计思想。
2 - 使用C或C++语言， 给出二叉树结点的数据类型定义。
3 - 根据设计思想，采用C或 C++语言描述算法，关键之处给出注释。

---

（本文重点关注算法实现及思路分析，不含具体答题表述）

分析实现

对于WPL的计算，首先想到是与结点深度有关的，那么在计算时就需要考虑将深度作为参数进行传递。

有了深度参数后，对二叉树进行遍历就可以轻松计算出WPL，此处采用后续遍历，具体实现如下：

// 计算WPL的辅助函数
int calWPLUtil(BTNode *root, int depth){if(root==NULL)return 0;if(root->left==NULL && root->right==NULL)return root->weight*depth;return calWPLUtil(root->left, depth+1)+ calWPLUtil(root->right, depth+1);
}// 计算WPL
int calWPL(BTNode *root){return calWPLUtil(root, 0);
}

---

总结

以上就是通过后序遍历计算二叉树的WPL的实现。

类似于二叉树转中缀表达式（传递深度）和判断顺序存储二叉树是否是BST（传递前驱元素），本题在实现的过程中也构建了辅助工具函数来传递额外的参数，这种思想在二叉树的递归中非常常用。

这篇关于【408DS算法题】036基础-14年真题_求二叉树的WPL的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---