进行二叉树类的设计并实现,包括以下功能: (1) 实现二叉树的建树; (2) 实现二叉树的前序、中序、后序遍历; (3) 能够求解二叉树的结点总数和叶子结点总数; (4) 能够求解二叉树的高度; (5) 在图形界面类上编写一个测试该类的程序。
时间: 2024-12-15 10:04:22 浏览: 7
为了设计一个简单的二叉树类,我们可以按照以下步骤进行:
1. **定义二叉树节点**:
```java
class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
```
2. **创建二叉树类**:
```java
public class BinaryTree {
private TreeNode root;
// 构造函数
public BinaryTree() {
root = null;
}
// 插入节点
public void insert(int val) {
if (root == null) {
root = new TreeNode(val);
} else {
insertNode(root, val);
}
}
private void insertNode(TreeNode node, int val) {
if (val < node.val) {
if (node.left == null) {
node.left = new TreeNode(val);
} else {
insertNode(node.left, val);
}
} else {
if (node.right == null) {
node.right = new TreeNode(val);
} else {
insertNode(node.right, val);
}
}
}
// 遍历方法(前序、中序、后序)
public List<Integer> preOrderTraversal(TreeNode node) {
if (node == null) return Collections.emptyList();
return Stream.concat(
Arrays.asList(node.val).stream(),
preOrderTraversal(node.left).stream(),
preOrderTraversal(node.right).stream()
).collect(Collectors.toList());
}
// ... 同理可以添加中序遍历和后序遍历方法
// 计算节点总数
public int countNodes(TreeNode node) {
if (node == null) return 0;
return 1 + countNodes(node.left) + countNodes(node.right);
}
// 计算叶子结点总数
public int countLeaves(TreeNode node) {
if (node == null) return 0;
return node.left == null && node.right == null ? 1 : countLeaves(node.left) + countLeaves(node.right);
}
// 计算高度
public int height(TreeNode node) {
if (node == null) return 0;
int leftHeight = height(node.left);
int rightHeight = height(node.right);
return Math.max(leftHeight, rightHeight) + 1;
}
}
```
3. **图形界面测试类**:
这个部分需要依赖于一个GUI库(如Swing或JavaFX),这里仅给出基本框架:
```java
import javax.swing.JFrame;
import java.awt.*;
public class BinaryTreeUI extends JFrame {
private BinaryTree tree;
private JButton insertBtn, traverseBtn, leafCountBtn, heightBtn;
public BinaryTreeUI(BinaryTree tree) {
this.tree = tree;
// 添加按钮和事件监听...
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree(); // 初始化二叉树
BinaryTreeUI ui = new BinaryTreeUI(tree);
ui.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
ui.setSize(400, 300);
ui.setVisible(true);
}
}
```
在这个类中,你需要将每个操作关联到对应的按钮点击事件,并调用相应的二叉树方法。
阅读全文