首页 > 试题广场 >

设计求T的WPL的算法

[问答题]

二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和,给定一棵二叉树T,采用二叉链表存储,节点结构为:

left

weight

right

其中叶节点的weight域保存该结点的非负权值。设root为指向T的根节点的指针,设计求T的WPL的算法。要求:

(1)给出算法的基本设计思想;

(2)使用C或C++语言,给出二叉树结点的数据类型定义;

        (3)根据设计思想,采用C或C++语言描述算法,关键之处给出注释。

(1) 算法的设计思想:
递归遍历二叉树,利用一个参数同时对深度进行计数。叶结点的带权路径长度=该结点的 weigth 值*该结点的深度。 每个叶结点的带权路径长度都可以求出, 二叉树的 WPL 值=树 全部叶结点的带权路径长度之和=根结点左子树中全部叶结点的带权路径长度之和+根结点右子树中全部叶结点的带权路径长度之和。 递归进行求和, 即可求出二叉树的带权路径长 度。

(2) 算法中使用的二叉树结点的数据类型定义如下:

typedef struct BTnode 
{ 
    unsigned int weight; //结点的非负权值 
    struct BTnode * lchild, * rchild; //左右指针 
}BTnode; 
(3) 算法实现:
int main() 
{ 
    return WPL(root,0); //初始化深度,调用 WPL 函数 
}
int WPL(BTnode * root,int d) //其中 d 为结点深度 
{ 
    if(root->lchild==NULL&&root->rchild==NULL)//root 为叶子结点 
        return (root->weight * d); //返回该叶子结点的带权路径长度 
    else 
        return(WPL(root-> lchild,d+1)+WPL(root->rchild,d+1)); 
    /*返回左右子树中全部叶结点的带权路径长度之和*/ 
}

发表于 2016-11-19 17:25:46 回复(0)
上面的代码都有点瑕疵,要么没有进行边界判定,要么是把非叶节点的也计算进去了。
上下我的代码。
public Class Tree{
    class Node{
        int weight;
        Node left,right;
    }
    
    public int getWPL(Node root, int depth){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return root.weight * depth;
        }
        
        return getWPL(root.left, depth + 1) + getWPL(root.right, depth + 1)
    }
}


发表于 2020-06-18 08:12:33 回复(0)
算法思想请看前面的人,但是反对上面那两位的代码,两个人的都无法正确运行。
下面是正确的算法代码:
typedef struct TreeNode {
    struct TreeNode *left, *right;
    int weight;
} *Tree;

int WPL(Tree tree, int depth) {
    if (tree == NULL) {
        return 0;
    }
    if (tree->left == NULL && tree->right == NULL) {
        return (tree->weight * depth);//已经到叶子结点了:返回本层的wpl
    } else {
        return (tree->weight * depth) +
               (WPL(tree->left, depth + 1) + WPL(tree->right, depth + 1));//返回本层wpl+左右子树的wpl
    }
}


编辑于 2019-11-03 16:51:25 回复(1)

(1) 算法的设计思想:
递归遍历二叉树,利用一个参数同时对深度进行计数。叶结点的带权路径长度=该结点的 weigth 值*该结点的深度。 每个叶结点的带权路径长度都可以求出, 二叉树的 WPL 值=树 中 全部叶结点的带权路径长度之和=根结点左子树中全部叶结点的带权路径长度之和+根结点右子树中全部叶结点的带权路径长度之和。 递归进行求和, 即可求出二叉树的带权路径长 度。

(2) 算法中使用的二叉树结点的数据类型定义如下:

1
2
3
4
5
typedefstructBTnode
{
    unsignedintweight;//结点的非负权值
    structBTnode * lchild, * rchild;//左右指针
}BTnode;
(3) 算法实现:
1
2
3
4
5
6
7
8
9
10
11
12
intmain()
{
    returnWPL(root,0);//初始化深度,调用 WPL 函数
}
intWPL(BTnode * root,intd)//其中 d 为结点深度
{
    if(root->lchild==NULL&&root->rchild==NULL)//root 为叶子结点
        return(root->weight * d);//返回该叶子结点的带权路径长度
    else
        return(WPL(root-> lchild,d+1)+WPL(root->rchild,d+1));
    /*返回左右子树中全部叶结点的带权路径长度之和*/
}
发表于 2017-08-27 14:36:01 回复(0)