ZBLOG

#include using namespace std; typedef struct BiTNode { int weight; struct BiTNode *left,*right; }BiTNode,*BiTree; void CreateBiTree(BiTree &T) {//先序建立二叉树 int x; cin>>x; if(x==0) T=NULL; else { T=new Bi...

这段代码是用来计算二叉树的带权路径长度(Weighted Path Length,WPL)的。下面是完整的代码实现:

#include<iostream>
using namespace std;
typedef struct BiTNode
{
    int weight;
    struct BiTNode *left,*right;
}BiTNode,*BiTree;

void CreateBiTree(BiTree &T)
{//先序建立二叉树
    int x;
    cin>>x;
    if(x==0) T=NULL;
    else
    {
        T=new BiTNode;
        T->weight=x;
        CreateBiTree(T->left);
        CreateBiTree(T->right);
    }
}

int WPL(BiTree &T, int d)
{//求二叉树T的带权路径长度
    if (!T) return 0; // 空树返回0
    
    if (!T->left && !T->right) // 叶子节点,返回该节点的权值乘以深度
        return T->weight * d;
    
    // 非叶子节点,递归计算左子树和右子树的WPL并相加
    return WPL(T->left, d + 1) + WPL(T->right, d + 1);
}

int main()
{
    while(1)
    {
        BiTree T;
        CreateBiTree(T);
        if(!T) break;
        int d=0;          //调用时T指向二叉树的根结点,d为0
        cout<<WPL(T,d)<<endl;
        
        // 清理内存,避免内存泄漏
        // 这里可以自行编写一个清理二叉树的函数,释放节点内存
    }
    
    return 0;
}

该程序使用先序方式创建二叉树,并实现了递归计算带权路径长度的函数WPL。在主函数中,通过循环输入多组数据,每次计算一棵二叉树的带权路径长度并输出结果。


内容由零声教学AI助手提供,问题来源于学员提问

本站部分文章来源于网络,版权归原作者所有,如有侵权请联系站长删除。
转载请注明出处:https://golang.0voice.com/?id=9246

分享:
扫描分享到社交APP
上一篇
下一篇
发表列表
游客 游客
此处应有掌声~
评论列表

还没有评论,快来说点什么吧~

联系我们

在线咨询: 点击这里给我发消息

微信号:3007537140

上班时间: 10:30-22:30

关注我们
x

注册

已经有帐号?