高精度压力传感器,作文网小学,纯情犀利哥的小说
路径:一棵树中,从一个结点到另一个结点所经过的所有结点,被我们称为两个结点之间的路径,如图:
从根节点1到叶子节点4的路径:1,2,4
路径长度:在一棵树中,从一个结点到另一个结点所经过的“边”的数量,被我们称为两个结点之间的路径长度,还是上图,根节点1到叶子结点4的路径经过了2个边,也就是说,若规定根节点的层数为1,则从根节点到N层的结点的的路径长度为:N-1
结点的带权路径长度:树的每一个结点,都可以拥有自己的“权重”(Weight),权重在不同的算法当中可以起到不同的作用。结点的带权路径长度,是指树的根结点到该结点的路径长度,和该结点权重的乘积,还是上图,如结点4的权重是10,那结点4的带权路径长度就是10*2 = 20。
树的带权路径长度:在一棵树中,所有叶子结点的带权路径长度之和,被称为树的带权路径长度,也被简称为WPL。
也就是从队列中删除1和4,插入5,并且仍然保持队列的升序。
package com.data.structure.tree;
/**
* 树节点
*
* @author wangjie
* @version V1.0
* @date 2020/7/20
*/
public class Node implements Comparable<Node>{
/**
* 节点权值
*/
int value;
/**
* 指向左子结点
*/
Node left;
/**
* 指向右子节点
*/
Node right;
public Node(int value){
this.value = value;
}
/**
* 前序遍历,先输出父结点,再遍历左子树和右子树
*/
public void preOrder(){
System.out.println(this);
if(null != this.left){
this.left.preOrder();
}
if(null != this.right){
this.right.preOrder();
}
}
@Override
public int compareTo(Node o) {
return this.value - o.value;
}
@Override
public String toString(){
return "Node[value="+value+"]";
}
}
package com.data.structure.tree;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* 哈夫曼树
*
* @author wangjie
* @version V1.0
* @date 2020/7/20
*/
public class HuffmanTree {
public static void main(String[] args) {
int arr[] = {2,3,7,9,18,25};
Node root = createHuffmanTree(arr);
preOrder(root);
}
/**
* 前序遍历
* @param root
*/
public static void preOrder(Node root){
if (null != root){
root.preOrder();
}else {
System.out.println("该树为空!");
}
}
/**
* 构建哈夫曼树
* @param arr
* @return
*/
public static Node createHuffmanTree(int[] arr){
List<Node> nodes = new ArrayList<>();
for(int value : arr){
nodes.add(new Node(value));
}
while ((nodes.size() > 1)){
Collections.sort(nodes);
Node leftNode = nodes.get(0);
Node rightNode = nodes.get(1);
Node parent = new Node(leftNode.value+rightNode.value);
parent.left = leftNode;
parent.right = rightNode;
nodes.remove(leftNode);
nodes.remove(rightNode);
nodes.add(parent);
}
return nodes.get(0);
}
}
本文地址:https://blog.csdn.net/aaa_bbb_ccc_123_456/article/details/107462776
希望与广大网友互动?? 点此进行留言吧!
评论内容