精华内容
下载资源
问答
  • 二叉树带权路径长度(WPL) 简介:*树的带权路径长度(Weighted Path Length of Tree,简记为WPL)*二叉树的带权路径长度是每个叶子节点深度(高度)与其指定权重的乘积总和。 算法思想:对于求带权路径长度我们...

    求二叉树带权路径长度(WPL)

    简介:*树的带权路径长度(Weighted Path Length of Tree,简记为WPL)*二叉树的带权路径长度是每个叶子节点深度(高度)与其指定权重的乘积总和


    算法思想:对于求带权路径长度我们只需要找到叶子结点以及叶子结点所在的层数即可,本文将采取递归与非递归两种思路来解题

    typedef struct BiNode{
    	int weight; //权值
    	BiNode *lchild,*rchild;
    };
    
    

    递归求解:

    int wpl=0;
    int wpl_preorder(BiNode *Root,int level){
    	int wpl_=0;
    	if(!Root)
    		return 0;
    	if(Root->rchild==NULL&&Root->lchild==NULL){
    		 wpl_=Root->weight*level;
    	}
    	wpl+=wpl_preorder(Root->lchild,level+1);
    	wpl+=wpl_preorder(Root->rchild,level+1);
    	return wpl_;
    }
    

    非递归求解(使用层次遍历):

    这里的代码引用了求二叉树的高度或者求二叉树宽度的代码若有不懂请看我之前博文 传送门求二叉树高度 传送门求二叉树宽度

    int wpl_levelorder(BiNode *Root){
    	if(!Root)
    		return 0;
    	BiNode *que[MaxSize];
    	int front=-1,rear=-1;
    	int counter=0;
    	int size=0;
    	int level=0;
    	int wpl=0;
    	que[++rear]=Root;
    	counter++;
    	while(front<rear){
    		level++;
    		size=counter;
    		counter=0;
    		while(size--){
    			
    			Root=que[++front];
    			if(Root->lchild==NULL&&Root->rchild==NULL){
    				wpl+=Root->weight*level;	
    			}
    			if(Root->rchild!=NULL){
    				que[++rear]=Root->rchild;
    				counter++;
    			}
    			if(Root->lchild!=NULL){
    				que[++rear]=Root->lchild;
    				counter++;
    			}	
    		}
    	}
    	return wpl;
    
    }
    
    
    展开全文
  • 二叉树存储结构: typedef struct Tnode { char data; struct Tnode *lnode; struct Tnode *rnode; }Tnode; typedef Tnode* type; 队列的实现: struct queue { type member[max]; int tail,head...

    二叉树存储结构:

    typedef struct Tnode
    {
    	char data;
    	struct Tnode *lnode;
    	struct Tnode *rnode;
    }Tnode;
    typedef  Tnode* type;
    

    队列的实现:

    struct queue
    {
    	type member[max];
    	int tail,head;
    };
    void initqueue(queue *q)
    {
    	q->head=q->tail = 0;
    }
    void pushqueue(queue *q,type o)
    {
    	if (q->tail > 50)
    		return;
    	q->member[q->tail++] = o;
    }
    type popqueue(queue *q)
    {
    	if (q->tail == 0)
    		return NULL;
    	return q->member[q->head++];
    }
    bool isqueueemty(queue *q)
    {
    	return q->tail ==q->head? true : false;
    
    

    问题求解——递归实现:
    求二叉树带权路径长度——递归与非递归实现C语言实现代码下载

    展开全文
  • 二叉树带权路径长度: 每个叶结点的深度与权值之积德总和。 方法:先序遍历或层次遍历 结点类型定义: typedef struct BiTNode{ int weight; struct BiTNode *lchild,*rchild; }BiTNode,BiTree; 基于先序: ...

    二叉树的带权路径长度: 每个叶结点的深度与权值之积德总和。

    方法:先序遍历或层次遍历

    结点类型定义:

    typedef struct BiTNode{
        int weight;
        struct BiTNode *lchild,*rchild;
    }BiTNode,BiTree;

    基于先序

    使用static 变量 wpl记录权值,每个结点的深度作为递归函数的参数传递。具体算法如下

    1)若是叶结点,wpl=wpl+该结点的深度与权值之积;

    2)非叶结点,若左子树不空,对左子树调用递归算法;

          若右子树不空,对其调用递归算法,深度参数为本结点的深度参数加1;

    3)最后返回wpl。

    int WPL(BiTree root){
        return wpl_PreOrder(root,0);
    }
    
    int wpl_PreOrder(BiTree root,int deep){
        static wpl = 0;
        if(root->llchild == NULL && root->rchild==NULL)
            wpl+=deep*root->weight;
    
        if(root->lchild!=NULL)
            wpl_PreOrder(root->lchild,deep+1);
        if(root->rchild!=NULL)
            wpl_PreOrder(root->rchild,deep+1);
    }

    基于层次遍历

    使用队列进行层次遍历,记录当前的层数;

    1)遍历到叶结点时,累计wpl;

    2)非叶结点时,将其子树加入队列;

    3)该结点为该层最后一个结点时,层数自增1;

    4)队列空遍历结束,返回wpl;

    #define Maxsize 100 //队列最大容量
    
    int wpl_levelOrder(BiTree root){
        BiTree q[Maxsize];
        int end1,end2;
        end1=end2=0;
        int wpl=0,deep=0;
        BiTree lastNode;      //当前层最后一个结点
        BiTree newLastNode;   //下一层最后一个结点
        lastNode = root;
        newLastNode = NULL;
        q[end2++]=root;
        
        while(end1!=end2){
            BiTree t=q[end1++];
            if(t->lchild==NULL&&t->rchild==NULL)//叶结点统计wpl
                wpl+=deep*t->weight;
            if(t->lchild != NULL){
                q[end2++]=t->lchild;//非叶结点入队
                newLastNode=t->lchild;
            }
            if(t->rchild != NULL){
                q[end2++]=t->rchild;
                newLastNode=t->rchild;
            }
            if(t==lastNode){
                lastNode=newLastNode;
                deep+=1;
            }
        }
        return wpl;
    }

    展开全文
  • 二叉树带权路径长度WPL是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树,采用二叉链表存储,叶子结点的weight域为该结点的权值。请设计一个算法,求二叉树带权路径长度。 算法思想 可以使用先序遍历...

    题目描述

     二叉树的带权路径长度WPL是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树,采用二叉链表存储,叶子结点的weight域为该结点的权值。请设计一个算法,求二叉树的带权路径长度。

    算法思想

    可以使用先序遍历或层次遍历解决问题。
    <1>算法思想一:基于先序递归遍历。
    用一个static变量记录WPL,把每个结点的深度作为递归函数的一个参数传递。

    • 若该结点是叶结点,则变量WPL加上该结点的深度与权值之和。
    • 若该结点是非叶结点,则左子树不为空时,对左子树调用递归算法,右子树不为空时,对右子树调用递归算法,深度参数均为本结点的深度参数加1。

    <2>算法思想二:基于层序遍历。
    使用队列进行层次遍历,并记录当前的层数。

    • 当遍历到叶结点时,累计WPL。
    • 当遍历到非叶结点时,把该结点的子树加入队列。
    • 当某结点为该层最后一个结点时,层数自增1。
    • 队列空时遍历结束,返回WPL。

    实现代码

    <1> 算法一的函数代码实现:

    int WPL_PreOrder(BTree root, int deep){
        static int wpl = 0;
        if(root->lchild==NULL && root->rchild==NULL){ //若为叶结点,累积
            wpl += deep*root->weight;
        }
        if(root->lchild != NULL){  //若左子树不空,对左子树递归遍历
            WPL_PreOrder(root->lchild, deep+1);
        }
        if(root->rchild != NULL){  //若右子树不空,对右子树递归遍历
            WPL_PreOrder(root->rchild, deep+1);
        }
        return wpl;
    }
    

    <2>算法二的函数代码实现:

    int WPL_Level(BTree root){
        queue<BNode *> treenode; //队列
        int wpl = 0;
        int deep = 0;  //初始化深度
        BNode *lastNode; //记录当前最后一个结点
        BNode *newlastNode; //记录下一层最后一个结点
        lastNode = root;  //初始化为根结点
        newlastNode = NULL;  //初始化为空
        treenode.push(root); //根结点入队
        while(!treenode.empty()){ //栈不空时循环
            BNode *top = treenode.front(); //取出队首元素
            treenode.pop();
            if(top->lchild==NULL && top->rchild==NULL){
                wpl += deep*top->weight;
            }//若为叶结点,累加
            if(top->lchild != NULL){ //若为非叶结点则把左孩子结点入队
                treenode.push(top->lchild);
                newlastNode = top->lchild; //设置下一层最后一个结点
            }
            if(top->rchild != NULL){  //右孩子结点入队
                treenode.push(top->rchild);
                newlastNode = top->rchild;
            }
            if(top == lastNode){  //若该结点为本层最后一个结点
                lastNode = newlastNode;  //更新
                deep+=1; //深度加1
            }
        }
        return wpl;
    }
    
    展开全文
  • 3766. 二叉树带权路径长度 原题传送:AcWing 3766. 二叉树带权路径长度 二叉树带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和,也就是每个叶结点的深度与权值之积的总和。 给定一棵二叉树 TTT ,请...
  • 设计算法求二叉树带权路径长度(WPL) 二叉树带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。 队列的基本操作以严蔚敏编写的教材为准。 基于层次遍历的算法: int WPL_LevelOrder (BiTree T) { ...
  • 层次遍历(广搜),如果没有规定节点结构可以再节点里设置一个深度标记,更简单。 typedef struct{ struct BiTNode *lchild,*rchild; int weight; }BiTNode,*BiTree; int wpl(BiTree T){ ... BiTre..
  • 二叉树带权路径长度问题

    千次阅读 2019-07-02 00:39:36
    二叉树带权路径长度问题问题中的名词解释1 二叉树定义2 二叉树带权路径长度问题解决方法1 先序遍历2 层次遍历个人总结 问题中的名词解释 1 二叉树定义 二叉树是n(n>=0)个节点的有限集合: 1 或者为空...
  • 二叉树计算带权路径长度(WPL)的算法 更多内容请访问点击我的主页 题目 : 二叉树带权路径长度二叉树中所有叶子结点的带权路径长度之和。给定二叉链表的存储的结点结构为 left weight right weight...
  • 下面的先序中序后序遍历以及二叉树带权路径的解法基本可以囊括绝大多数与二叉树相关的问题,为了方便记忆,在写的时候都用了两个嵌套的while循环,省得到时候再跟while里套if else的记混~ 首先二叉树的先序、...
  • 二叉树带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为: 其中叶结点的weight域保存该结点的非负权值。设root为指向T 的根结点的指针,请设计求T的WPL...
  • 二叉树带权路径和,指的是二叉树的所有叶子节点的权值 * 其深度 之和。 本次因为是完整的程序,所以包含 1)输入前序、中序序列 创建二叉树 2)层序遍历打印出二叉树 3)计算WPL 数据结构定义 typedef struct ...
  • 第五章 二叉树的最大路径长度和最大带权路径和 1、二叉树的最大路径长度: 给定一棵二叉树,在树中一定存在两个距离最远的叶子节点。这就是二叉树的最大路径长度。 路径A: 路径经过左子树的最深节点,通过根节点,...
  • 树的带权路径长度

    千次阅读 2019-07-24 16:37:36
    从根节点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和叫做二叉树带权路径长度
  • 第五章 树和二叉树 数据结构基础代码 (严蔚敏 人邮教育出版社) 树的带权路径长度(Weighted Path Length) 定义:树中所有叶子的带权路径长度之...//求二叉树带权路径长度 #include <stdio.h> #include <...
  • 今年是求二叉树带权路径长度,我就写了算法思想,代码空白,因为时间来不及了,慌了,是心态的问题吧,做到最后有种天要塌下来的感觉,回来后很沮丧,因为我觉得自己是可以写出程序的,不服啊!  下面说说这道...
  • 带权路径长度:结点具有权值,从该结点到根之间的路径长度乘以结点的权值,就是该结点的带权路径长度。 叶子结点的带权路径长度:从叶结点到根之间的路径长度(所在层数-1)乘以叶结点的权值。 树的带权路径...
  • 哈夫曼树 和 树的带权路径长度

    万次阅读 2018-08-28 04:37:41
    树的带权路径长度(Weighted Path Length of ...哈夫曼树是一种带权路径长度最短的二叉树,也称为最优二叉树。   哈夫曼树构建教程 https://blog.csdn.net/xueba8/article/details/78477892 例:对于给定的一...
  • #define MaxSize 50 typedef enmu{false,true} bool; typedef char ElemType_c; typedef struct BitNode{ ElemType_c data; .../*求二叉树的高度,判断是否为完全二叉树,实际上都是二叉树层次...
  • 层次:从树根开始定义,树根为第一层 深度:从根开始,向下累加 高度:从叶开始,向上累加 这里定义:树的高度/深度为数中结点最大层次数。...树的带权路径长度(WPL):所有叶结点带权路径长度之和.
  • //任务:求二叉树所有叶结点的带权路径长度之和WPL(一个叶结点的带权路径长度=叶结点的权值*叶结点到根节点的路径长度(线的个数)) //算法思想:利用层次遍历记录层数,如遇到叶子结点则用叶子结点×(层数-1) int...
  • 给定n个数值{ W1,W2,…,Wn},若将它们作为n个结点的权,并以这n个结点为叶子结点构造一颗二叉树,那么就可以构造出多棵具有不同形态的二叉树,其中带权路径长度最短的那棵二叉树称为哈夫曼树,或
  • 根据网上的相关资料,通过构造哈夫曼树求解最优二叉树所有叶子结点的带权路径长度之和   # include #include #define maxsize 30; /*  霍夫曼树求解最佳二叉树  完成时间:2015-7-10 */ typedef struct ptree { ...
  • 思想: 先构建一个线性表,将树的结点存入,然后对树的结点进行升序排序,这样就保证了线性表的前两...而寻找带权路径长度可以使用递归的方法。 代码: public class Main { public static void main(String[] args) {
  • AVL树成功失败: ... 霍夫曼树(哈夫曼):每个节点要嘛没有子节点,... 带权路径长度:WPL。 WPL = 1*9 + 2*5 + 3*2 + 4*1 + 4*2 =37 另外还可以有另外一个方法,结合算法描述仔细观察发现最小带权路径长...
  • 带权路径长度有一个求法是:wpl=非叶子结点的权值之和,因此可以选择一个遍历算法,求出所有非叶子结点的权值之和即可。但是这个方法是针对huffman树的,如果不是huffman树,必须按照叶子结点的深度与权值之积总和来...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,117
精华内容 2,846
关键字:

二叉树的带权路径长度