带权路径长度C语言代码
时间: 2023-06-17 12:07:05 浏览: 50
带权路径长度(weighted path length)是一种二叉树的平衡性度量指标,是指所有叶子节点深度的加权和,其中每个叶子节点的权值为该节点的深度。下面是一份用C语言实现计算带权路径长度的代码:
```C
#include <stdio.h>
#include <stdlib.h>
/* define a tree node */
struct node {
int data;
struct node* left;
struct node* right;
};
/* create a new node */
struct node* new_node(int data) {
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
/* insert a new node into the tree */
void insert_node(struct node** root, int data) {
if (*root == NULL) {
*root = new_node(data);
return;
}
if (data < (*root)->data) {
insert_node(&((*root)->left), data);
} else {
insert_node(&((*root)->right), data);
}
}
/* calculate the depth of a node */
int depth(struct node* node) {
if (node == NULL) {
return 0;
} else {
int left_depth = depth(node->left);
int right_depth = depth(node->right);
if (left_depth > right_depth) {
return left_depth + 1;
} else {
return right_depth + 1;
}
}
}
/* calculate the weighted path length of a tree */
int weighted_path_length(struct node* root) {
if (root == NULL) {
return 0;
} else {
return depth(root) + weighted_path_length(root->left) + weighted_path_length(root->right);
}
}
int main() {
struct node* root = NULL;
/* insert some nodes into the tree */
insert_node(&root, 50);
insert_node(&root, 30);
insert_node(&root, 20);
insert_node(&root, 40);
insert_node(&root, 70);
insert_node(&root, 60);
insert_node(&root, 80);
/* calculate the weighted path length of the tree */
int wpl = weighted_path_length(root);
printf("Weighted path length: %d\n", wpl);
return 0;
}
```
在这个代码中,我们定义了一个二叉树的节点结构体,并实现了插入节点、计算节点深度和计算带权路径长度的函数。在主函数中,我们插入了一些节点,并输出了计算结果。