二叉树BinaryTree.java类实现以下方法:输出所有直径及其路径长度 public static<T> void diameterAll(BinaryTree<T> bitree)
时间: 2024-04-08 10:33:34 浏览: 66
以下是一个简单的二叉树实现的Java代码,包含了输出所有直径及其路径长度的方法:
```java
public class BinaryTree<T> {
private Node<T> root;
// 构造函数
public BinaryTree(Node<T> root) {
this.root = root;
}
// 节点类
private static class Node<T> {
private T data;
private Node<T> left;
private Node<T> right;
public Node(T data) {
this.data = data;
this.left = null;
this.right = null;
}
}
// 输出所有直径及其路径长度
public static <T> void diameterAll(BinaryTree<T> bitree) {
if (bitree.root == null) {
System.out.println("Binary tree is empty.");
return;
}
List<List<Node<T>>> paths = new ArrayList<>();
List<Integer> diameters = new ArrayList<>();
findPaths(bitree.root, paths, new ArrayList<>());
calculateDiameters(bitree.root, paths, diameters);
for (int i = 0; i < diameters.size(); i++) {
System.out.println("Diameter: " + diameters.get(i) + ", Path: ");
for (Node<T> node : paths.get(i)) {
System.out.print(node.data + " ");
}
System.out.println();
}
}
// 查找所有路径
private static <T> void findPaths(Node<T> node, List<List<Node<T>>> paths, List<Node<T>> path) {
if (node == null) {
return;
}
path.add(node);
if (node.left == null && node.right == null) {
paths.add(new ArrayList<>(path));
} else {
findPaths(node.left, paths, path);
findPaths(node.right, paths, path);
}
path.remove(path.size() - 1);
}
// 计算直径
private static <T> int calculateDiameters(Node<T> node, List<List<Node<T>>> paths, List<Integer> diameters) {
if (node == null) {
return 0;
}
int leftHeight = calculateDiameters(node.left, paths, diameters);
int rightHeight = calculateDiameters(node.right, paths, diameters);
int diameter = leftHeight + rightHeight;
diameters.add(diameter);
return Math.max(leftHeight, rightHeight) + 1;
}
public static void main(String[] args) {
// 创建二叉树示例
Node<Integer> node1 = new Node<>(1);
Node<Integer> node2 = new Node<>(2);
Node<Integer> node3 = new Node<>(3);
Node<Integer> node4 = new Node<>(4);
Node<Integer> node5 = new Node<>(5);
node1.left = node2;
node1.right = node3;
node2.left = node4;
node3.right = node5;
BinaryTree<Integer> bitree = new BinaryTree<>(node1);
// 输出所有直径及其路径长度
diameterAll(bitree);
}
}
```
这段代码使用了二叉树的先序遍历来查找所有路径,然后计算每个路径的直径。最后,输出每个直径及其路径长度。以上是一个简单的实现,你可以根据自己的需求进行修改和扩展。
阅读全文