输出所有直径及其路径长度 public static<T> void diameterAll(BinaryTree<T> bitree)
时间: 2024-04-08 10:33:33 浏览: 56
java输出二叉树直径与路径长度
要输出二叉树的所有直径及其路径长度,可以使用递归的方式来实现。下面是一个示例的Java代码:
```java
import java.util.ArrayList;
import java.util.List;
public class BinaryTree<T> {
private Node<T> root;
private static class Node<T> {
private T data;
private Node<T> left;
private Node<T> right;
Node(T data) {
this.data = data;
this.left = null;
this.right = null;
}
}
public void diameterAll() {
List<Integer> diameters = new ArrayList<>();
diameterHelper(root, diameters);
// 输出直径及其路径长度
for (int i = 0; i < diameters.size(); i++) {
System.out.println("直径 " + (i + 1) + ": " + diameters.get(i));
}
}
private int diameterHelper(Node<T> node, List<Integer> diameters) {
if (node == null) {
return 0;
}
// 计算左子树和右子树的高度
int leftHeight = height(node.left);
int rightHeight = height(node.right);
// 计算当前节点的直径
int diameter = leftHeight + rightHeight + 1;
// 将直径添加到列表中
diameters.add(diameter);
// 递归计算左子树和右子树的直径
int leftDiameter = diameterHelper(node.left, diameters);
int rightDiameter = diameterHelper(node.right, diameters);
// 返回左子树、右子树和当前节点直径中的最大值
return Math.max(diameter, Math.max(leftDiameter, rightDiameter));
}
private int height(Node<T> node) {
if (node == null) {
return 0;
}
// 递归计算左子树和右子树的高度
int leftHeight = height(node.left);
int rightHeight = height(node.right);
// 返回左子树和右子树中较大的高度加上当前节点的高度
return Math.max(leftHeight, rightHeight) + 1;
}
public static void main(String[] args) {
// 创建一个二叉树的示例
BinaryTree<Integer> bitree = new BinaryTree<>();
bitree.root = new Node<>(1);
bitree.root.left = new Node<>(2);
bitree.root.right = new Node<>(3);
bitree.root.left.left = new Node<>(4);
bitree.root.left.right = new Node<>(5);
bitree.root.right.left = new Node<>(6);
bitree.root.right.right = new Node<>(7);
// 输出所有直径及其路径长度
bitree.diameterAll();
}
}
```
以上代码定义了一个`BinaryTree`类,其中包含一个`diameterAll`方法用于输出二叉树的所有直径及其路径长度。在`diameterAll`方法中,使用`diameterHelper`方法来递归计算每个节点的直径,并将直径添加到一个列表中。最后,遍历列表并输出直径及其路径长度。
在`main`方法中创建了一个二叉树的示例,并调用`diameterAll`方法输出所有直径及其路径长度。
请注意,这只是一个示例实现,具体的二叉树结构和数据类型可以根据实际需求进行修改。
阅读全文