【数据结构】（二叉树）求二叉树带权路径长度（WPL）递归&&非递归

迷南。 2021-11-10 23:36 492阅读 0赞

## 求二叉树带权路径长度（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_;
    }

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

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

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;
    
    }

[Link 1]: https://blog.csdn.net/qq_41934478/article/details/97959086
[Link 2]: https://blog.csdn.net/qq_41934478/article/details/98236928