选择一种树的存储结构,可以是顺序存储结构(数组)或链式存储结构(链表),设计程序实现树的建立、插入节点、删除节点等基本操作。实现树的中序遍历,输出节点值。 (1)插入节点:50,30,70,20,40,60,80 (2)删除节点:20
时间: 2024-10-19 17:17:46 浏览: 11
在Java中,我们可以使用链式存储结构,比如二叉搜索树(Binary Search Tree, BST),来实现树的存储结构。这里我将演示如何创建一个简单的二叉搜索树,并实现插入节点、删除节点以及中序遍历的功能。
首先,我们定义一个`Node`类,用于表示树中的每个节点:
```java
public class Node {
int data;
Node left;
Node right;
public Node(int value) {
data = value;
left = null;
right = null;
}
}
```
接下来,我们创建一个`BST`类,包含插入、删除和中序遍历的方法:
```java
import java.util.ArrayList;
import java.util.List;
public class BinarySearchTree {
private Node root;
// 插入节点方法
public void insert(int value) {
root = insertRecursive(root, value);
}
private Node insertRecursive(Node node, int value) {
if (node == null) {
return new Node(value);
}
if (value < node.data) {
node.left = insertRecursive(node.left, value);
} else if (value > node.data) {
node.right = insertRecursive(node.right, value);
}
return node;
}
// 删除节点方法(这里简化处理了只有一个子节点的情况)
public void delete(int value) {
root = deleteRecursive(root, value);
}
private Node deleteRecursive(Node node, int value) {
if (node == null) {
return null;
}
if (value < node.data) {
node.left = deleteRecursive(node.left, value);
} else if (value > node.data) {
node.right = deleteRecursive(node.right, value);
} else {
if (node.left == null && node.right == null) { // 叶子节点
node = null; // 或者简单地返回null替换当前节点
} else if (node.left == null) { // 只有右子节点
node = node.right;
} else if (node.right == null) { // 只有左子节点
node = node.left;
} else { // 有两个子节点
Node temp = findMinValueNode(node.right); // 找到右子树最小值节点
node.data = temp.data;
node.right = deleteRecursive(node.right, temp.data);
}
}
return node;
}
// 中序遍历并打印节点值
public List<Integer> inorderTraversal() {
List<Integer> result = new ArrayList<>();
inorderTraversalHelper(root, result);
return result;
}
private void inorderTraversalHelper(Node node, List<Integer> list) {
if (node != null) {
inorderTraversalHelper(node.left, list);
list.add(node.data);
inorderTraversalHelper(node.right, list);
}
}
// 辅助方法,找到最小值节点
private Node findMinValueNode(Node node) {
while (node.left != null) {
node = node.left;
}
return node;
}
}
```
现在你可以使用这个`BinarySearchTree`类来完成以下操作:
```java
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
// 插入节点
for (int value : new int[]{50, 30, 70, 20, 40, 60, 80}) {
bst.insert(value);
}
// 输出中序遍历结果
System.out.println("Inorder traversal: " + bst.inorderTraversal());
// 删除节点
bst.delete(20);
// 再次输出中序遍历结果
System.out.println("After deleting 20: " + bst.inorderTraversal());
}
```
阅读全文