c语言计算二叉树的带权路径长度之和（WPL）

1.WPL：树中全部叶节点的带权路径之和

2.代码中所画的树为：

3.求上述WPL：

WPL=0*1+1*2+1*3+2*4+2*5=23

4.主要代码为：

int wpl(Node *ROOT,int high){
	int n=0;
	if(ROOT!=NULL){
		n=ROOT->weight*high;
		n=n+wpl(ROOT->lchild,high+1);
		n=n+wpl(ROOT->rchild,high+1); 
	}
	return n;
}

5.完整代码为：

#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
	int weight;
	struct Node *lchild,*rchild;
}Node;
int wpl(Node *ROOT,int high){
	int n=0;
	if(ROOT!=NULL){
		n=ROOT->weight*high;
		n=n+wpl(ROOT->lchild,high+1);
		n=n+wpl(ROOT->rchild,high+1); 
	}
	return n;
}
int main() {
	Node *ROOT=(Node *)malloc(sizeof(Node));
	ROOT->weight=1;
	ROOT->lchild=NULL;
	ROOT->rchild=NULL;
	Node *m=(Node *)malloc(sizeof(Node));
	m->weight=2;
	m->lchild=NULL;
	m->rchild=NULL;
	ROOT->lchild=m;
	Node *n=(Node *)malloc(sizeof(Node));
	n->weight=4;
	n->lchild=NULL;
	n->rchild=NULL;
	m->rchild=n;
	Node *a=(Node *)malloc(sizeof(Node));
	a->weight=3;
	a->lchild=NULL;
	a->rchild=NULL;
	ROOT->rchild=a;
	Node *b=(Node *)malloc(sizeof(Node));
	b->weight=5;
	b->lchild=NULL;
	b->rchild=NULL;
	a->rchild=b;
	printf("WPL为：%d",wpl(ROOT,0));
}

6.执行结果为：