设计程序实现通过输入先序、中序遍历序列,建立一棵二叉树,并编写求二叉树的深度、叶子结点数和结点个数的函数。测试上述各函数的正确性,测试参考结果下图。 用Java输出
时间: 2024-11-09 10:28:31 浏览: 17
在Java中,为了实现这个功能,你可以创建三个核心类:TreeNode表示二叉树的节点,BinaryTreeBuilder用于构建二叉树,以及TreeUtils提供计算深度、叶子节点数和节点总数的方法。这里是一个简化的示例:
首先,定义`TreeNode`类:
```java
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
left = null;
right = null;
}
}
```
然后,创建`BinaryTreeBuilder`类,利用先序和中序遍历重建二叉树:
```java
import java.util.List;
public class BinaryTreeBuilder {
public TreeNode buildTree(List<Integer> preorder, List<Integer> inorder) {
if (preorder == null || inorder == null || preorder.size() != inorder.size()) {
return null;
}
TreeNode root = findRoot(preorder, inorder);
TreeNode[] stack = new TreeNode[inorder.size()];
for (int i = inorder.size() - 1; i >= 0; i--) {
if (inorder.get(i) == inorder.get(root)) {
stack[i] = root;
while (!stack.isEmpty && stack[stack.length - 1].val > inorder.get(i)) {
root = stack.pop();
}
root.right = new TreeNode(inorder.get(i));
stack.push(root);
} else {
root.left = new TreeNode(inorder.get(i));
stack.push(root);
}
}
return root;
}
private TreeNode findRoot(List<Integer> preorder, List<Integer> inorder) {
for (int val : preorder) {
if (!inorder.contains(val)) {
return new TreeNode(val);
}
}
throw new IllegalArgumentException("Invalid input");
}
}
```
接下来,创建`TreeUtils`类,包含计算深度、叶子节点数和节点总数的方法:
```java
import java.util.Queue;
public class TreeUtils {
public static int depth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int level = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
level++;
}
return level;
}
public static int leafCount(TreeNode root) {
return countNodes(root, true);
}
private static int countNodes(TreeNode root, boolean isLeaf) {
if (root == null) {
return 0;
}
return isLeaf ? 1 : 1 + countNodes(root.left, false) + countNodes(root.right, false);
}
public static int totalNodeCount(TreeNode root) {
return countNodes(root, false);
}
}
```
最后,你可以编写测试案例,例如:
```java
public class Main {
public static void main(String[] args) {
// 示例数据,先序遍历:[1, 2, 4, 5, 3, 6]
// 中序遍历:[4, 2, 5, 1, 6, 3]
List<Integer> preorder = Arrays.asList(1, 2, 4, 5, 3, 6);
List<Integer> inorder = Arrays.asList(4, 2, 5, 1, 6, 3);
TreeNode root = BinaryTreeBuilder.buildTree(preorder, inorder);
System.out.println("Depth: " + TreeUtils.depth(root));
System.out.println("Leaf Count: " + TreeUtils.leafCount(root));
System.out.println("Total Node Count: " + TreeUtils.totalNodeCount(root));
// 添加更多测试用例...
}
}
```
这个示例展示了如何构建二叉树并计算其特性。你可以根据需要修改测试数据以验证函数的正确性。
阅读全文