树是一种非线性的数据结构，它由节点和边组成。每个节点可以有零个或多个子节点。在树中，没有循环，并且所有的节点都是通过边连接的。
-
树的基本概念：
- 根节点：没有父节点的唯一节点。
- 子节点：一个节点可以直接拥有零个或多个子节点。
- 父节点：每个子节点都有一个父节点，除了根节点。
- 叶子节点：没有任何子节点的节点。
- 兄弟节点：具有相同父节点的节点。
- 路径：从一个节点到另一个节点的一系列连续的边。
- 深度：从根节点到特定节点的路径长度。
- 高度：树中任何节点的最大深度。
-
Java中的树实现：
下面是一个简单的二叉树的例子：
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class BinaryTree {
TreeNode root;
public BinaryTree() {
root = null;
}
public void add(int value) {
root = addRecursive(root, value);
}
private TreeNode addRecursive(TreeNode current, int value) {
if (current == null) {
return new TreeNode(value);
}
if (value < current.val) {
current.left = addRecursive(current.left, value);
} else if (value > current.val) {
current.right = addRecursive(current.right, value);
}
return current;
}
}
在这个例子中，我们创建了一个二叉树，其中每个节点最多有两个子节点：左子节点和右子节点。我们还实现了一个添加新节点的方法，该方法会根据新值与当前节点值的大小关系，将新节点添加到左子树或右子树。
- 使用案例：
假设我们要创建一个学生信息的二叉搜索树，我们可以使用上面定义的二叉树类，但是我们需要修改节点类以存储学生的姓名和年龄，如下所示：
public class StudentNode {
String name;
int age;
StudentNode left;
StudentNode right;
StudentNode(String name, int age) {
this.name = name;
this.age = age;
}
}
然后，我们可以创建一个新的二叉树，并添加学生信息：
public class StudentTree {
StudentNode root;
public StudentTree() {
root = null;
}
public void addStudent(String name, int age) {
root = addStudentRecursive(root, name, age);
}
private StudentNode addStudentRecursive(StudentNode current, String name, int age) {
if (current == null) {
return new StudentNode(name, age);
}
if (age < current.age) {
current.left = addStudentRecursive(current.left, name, age);
} else if (age > current.age) {
current.right = addStudentRecursive(current.right, name, age);
}
return current;
}
}
在这个例子中，我们创建了一个新的二叉树，用于存储学生的信息。我们使用学生的年龄作为比较标准，将学生信息添加到树中。
让我们继续扩展上述的学生信息二叉搜索树的案例，这次我们将添加查找学生信息的功能。
首先，我们需要在StudentNode类中添加一个toString()方法，以便我们可以打印出学生的信息：
public class StudentNode {
String name;
int age;
StudentNode left;
StudentNode right;
StudentNode(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "StudentNode{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
}
然后，在StudentTree类中，我们可以添加一个查找学生信息的方法：
public class StudentTree {
// ...
public StudentNode findStudent(int age) {
return findStudentRecursive(root, age);
}
private StudentNode findStudentRecursive(StudentNode current, int age) {
if (current == null) {
return null;
}
if (age == current.age) {
return current;
}
if (age < current.age) {
return findStudentRecursive(current.left, age);
} else {
return findStudentRecursive(current.right, age);
}
}
}
这个findStudent()方法会返回指定年龄的学生信息，如果找不到，则返回null。
现在，我们可以创建一个main()方法来测试我们的二叉搜索树：
public class Main {
public static void main(String[] args) {
StudentTree tree = new StudentTree();
tree.addStudent("Alice", 20);
tree.addStudent("Bob", 22);
tree.addStudent("Charlie", 18);
System.out.println(tree.findStudent(20)); // 输出: StudentNode{name='Alice', age=20}
System.out.println(tree.findStudent(22)); // 输出: StudentNode{name='Bob', age=22}
System.out.println(tree.findStudent(18)); // 输出: StudentNode{name='Charlie', age=18}
System.out.println(tree.findStudent(25)); // 输出: null
}
}
在这个例子中，我们首先创建了一个学生信息的二叉搜索树，并添加了三个学生的信息。然后，我们使用findStudent()方法查找并打印出学生的信息。
接下来，我们可以在StudentTree类中添加删除学生信息的功能。
首先，我们创建一个删除学生信息的方法，这可能比添加和查找更复杂，因为我们需要处理三种情况：删除的节点是叶子节点、删除的节点有一个子节点、删除的节点有两个子节点。
public class StudentTree {
// ...
public void deleteStudent(int age) {
root = deleteStudentRecursive(root, age);
}
private StudentNode deleteStudentRecursive(StudentNode current, int age) {
if (current == null) {
return null;
}
if (age == current.age) {
if (current.left == null && current.right == null) {
return null;
}
if (current.right == null) {
return current.left;
}
if (current.left == null) {
return current.right;
}
int smallestValue = findMin(current.right);
current.age = smallestValue;
current.right = deleteStudentRecursive(current.right, smallestValue);
return current;
}
if (age < current.age) {
current.left = deleteStudentRecursive(current.left, age);
return current;
}
current.right = deleteStudentRecursive(current.right, age);
return current;
}
private int findMin(StudentNode node) {
return node.left == null ? node.age : findMin(node.left);
}
}
在这个例子中，deleteStudent()方法会删除指定年龄的学生信息。如果要删除的节点是叶子节点或者只有一个子节点，那么我们直接删除该节点即可。如果要删除的节点有两个子节点，我们找到其右子树中的最小节点（即下一个最大的节点），用它替换要删除的节点，然后删除这个最小节点。
最后，我们可以在Main类中测试一下删除功能：
public class Main {
public static void main(String[] args) {
StudentTree tree = new StudentTree();
tree.addStudent("Alice", 20);
tree.addStudent("Bob", 22);
tree.addStudent("Charlie", 18);
System.out.println(tree.findStudent(20)); // 输出: StudentNode{name='Alice', age=20}
tree.deleteStudent(20);
System.out.println(tree.findStudent(20)); // 输出: null
System.out.println(tree.findStudent(22)); // 输出: StudentNode{name='Bob', age=22}
tree.deleteStudent(22);
System.out.println(tree.findStudent(22)); // 输出: null
System.out.println(tree.findStudent(18)); // 输出: StudentNode{name='Charlie', age=18}
tree.deleteStudent(18);
System.out.println(tree.findStudent(18)); // 输出: null
}
}
在这个例子中，我们首先创建了一个学生信息的二叉搜索树，并添加了三个学生的信息。然后，我们使用deleteStudent()方法删除学生信息，再使用findStudent()方法验证是否删除成功。
在上一节中，我们已经实现了二叉搜索树的添加、查找和删除操作。接下来，我们将实现遍历操作。二叉树的遍历主要有三种方式：前序遍历、中序遍历和后序遍历。
前序遍历的顺序是：先访问根节点，然后递归地进行左子树的前序遍历，最后递归地进行右子树的前序遍历。
中序遍历的顺序是：先递归地进行左子树的中序遍历，然后访问根节点，最后递归地进行右子树的中序遍历。
后序遍历的顺序是：先递归地进行左子树的后序遍历，然后递归地进行右子树的后序遍历，最后访问根节点。
我们将在StudentTree类中添加这些遍历方法：
public class StudentTree {
// ...
public void preOrderTraversal() {
preOrderTraversalRecursive(root);
}
private void preOrderTraversalRecursive(StudentNode node) {
if (node != null) {
System.out.print(node + " ");
preOrderTraversalRecursive(node.left);
preOrderTraversalRecursive(node.right);
}
}
public void inOrderTraversal() {
inOrderTraversalRecursive(root);
}
private void inOrderTraversalRecursive(StudentNode node) {
if (node != null) {
inOrderTraversalRecursive(node.left);
System.out.print(node + " ");
inOrderTraversalRecursive(node.right);
}
}
public void postOrderTraversal() {
postOrderTraversalRecursive(root);
}
private void postOrderTraversalRecursive(StudentNode node) {
if (node != null) {
postOrderTraversalRecursive(node.left);
postOrderTraversalRecursive(node.right);
System.out.print(node + " ");
}
}
}
然后，我们可以在Main类中测试一下遍历功能：
public class Main {
public static void main(String[] args) {
StudentTree tree = new StudentTree();
tree.addStudent("Alice", 20);
tree.addStudent("Bob", 22);
tree.addStudent("Charlie", 18);
System.out.println("Pre-order traversal:");
tree.preOrderTraversal(); // 输出: StudentNode{name='Charlie', age=18} StudentNode{name='Alice', age=20} StudentNode{name='Bob', age=22}
System.out.println("\nIn-order traversal:");
tree.inOrderTraversal(); // 输出: StudentNode{name='Charlie', age=18} StudentNode{name='Alice', age=20} StudentNode{name='Bob', age=22}
System.out.println("\nPost-order traversal:");
tree.postOrderTraversal(); // 输出: StudentNode{name='Charlie', age=18} StudentNode{name='Bob', age=22} StudentNode{name='Alice', age=20}
}
}
在这个例子中，我们首先创建了一个学生信息的二叉搜索树，并添加了三个学生的信息。然后，我们分别进行了前序遍历、中序遍历和后序遍历，并打印出了遍历结果。