二叉树的WPL数据结构计算程序
时间: 2023-07-07 17:33:13 浏览: 60
以下是使用数据结构(栈)计算二叉树加权路径长度的C++程序:
```c++
#include <iostream>
#include <stack>
using namespace std;
// 二叉树节点结构体
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 计算二叉树的加权路径长度
int getWPL(TreeNode* root) {
if (root == nullptr) {
return 0;
}
stack<TreeNode*> s;
TreeNode* p = root;
int wpl = 0, depth = 0;
while (p != nullptr || !s.empty()) {
if (p != nullptr) {
s.push(p);
depth++;
if (p->left == nullptr && p->right == nullptr) { // 叶子节点
wpl += p->val * depth;
}
p = p->left;
} else {
p = s.top();
if (p->right != nullptr) {
p->right->val += p->val; // 将右子节点的值累加上父节点的值
}
if (s.size() > depth) { // 回溯到上一层
wpl -= (p->val * depth);
depth--;
}
s.pop();
p = p->right;
}
}
return wpl;
}
int main() {
// 构造一棵二叉树
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
// 计算二叉树的加权路径长度
int wpl = getWPL(root);
cout << "二叉树的加权路径长度是:" << wpl << endl;
return 0;
}
```
该程序使用栈的方法计算二叉树的加权路径长度,其中变量`depth`表示当前节点的深度。当遍历到一个叶子节点时,累加其权重乘以深度的结果;当回溯到上一层时,将之前的节点权重乘以深度的结果减去。通过这样的方式,计算完成后即可得到二叉树的加权路径长度。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)