数据结构考研真题（三）——二叉树所有叶结点的带权路径长度之和一、问题描述二、思路分析三、代码实现

186 阅读 0 评论 123 点赞

我是靠谱客的博主发嗲电源，这篇文章主要介绍数据结构考研真题（三）——二叉树所有叶结点的带权路径长度之和一、问题描述二、思路分析三、代码实现，现在分享给大家，希望可以做个参考。

一、问题描述

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

二、思路分析

可以使用先序遍历也可以使用层次遍历，层次遍历还没看

三、代码实现

结构体定义：

typedef struct Node{
	int data;
	struct Node *left = NULL;
	struct Node *right = NULL;
	int weight;	
}*Tree;

主要代码：

int wpl = 0;
void preOrderRoad(Tree tree,int dept){
	if(tree == NULL){
		return;
	}
	if(tree->left == NULL && tree->right == NULL){
		wpl = wpl + tree->weight*dept;
		return;
	}else{
		preOrderRoad(tree->left,dept+1);
		preOrderRoad(tree->right,dept+1);
	}
}