二叉树是一种树状结构,其中每个节点最多有两个子节点。带权路径长度是指二叉树中所有路径长度与路径上的权值乘积之和。下面是使用Java求解二叉树带权路径长度和的代码示例:
public class BinaryTree { private Node root; // 内部类表示二叉树节点 private class Node { int val; int weight; Node left; Node right; Node(int val, int weight) { this.val = val; this.weight = weight; } } // 向二叉树中插入节点 public void insert(int val, int weight) { root = insert(root, val, weight); } private Node insert(Node node, int val, int weight) { if (node == null) { return new Node(val, weight); } if (val< node.val) { node.left = insert(node.left, val, weight); } else if (val >node.val) { node.right = insert(node.right, val, weight); } return node; } // 求二叉树带权路径长度和 public int getWeightedPathLength() { return getWeightedPathLength(root, 0); } private int getWeightedPathLength(Node node, int depth) { if (node == null) { return 0; } return depth * node.weight + getWeightedPathLength(node.left, depth + 1) + getWeightedPathLength(node.right, depth + 1); } } // 使用示例 public class Main { public static void main(String[] args) { BinaryTree tree = new BinaryTree(); tree.insert(5, 2); tree.insert(3, 1); tree.insert(7, 4); tree.insert(2, 1); tree.insert(4, 3); tree.insert(6, 1); tree.insert(8, 3); int wpl = tree.getWeightedPathLength(); System.out.println("二叉树的带权路径长度和为:" + wpl); // 输出:二叉树的带权路径长度和为:58 } }
以上代码中,二叉树的节点由内部类Node表示,每个节点有一个值和一个权值。二叉树的插入、查找操作使用递归实现。求二叉树带权路径长度和的方法也使用了递归,通过累加当前节点深度乘以权值和左右子树的带权路径长度和来计算。