数据结构第09节:二叉树

时间:2024-07-08 20:03:15

树是一种非线性的数据结构,它由节点和边组成。每个节点可以有零个或多个子节点。在树中,没有循环,并且所有的节点都是通过边连接的。

  1. 树的基本概念:

    • 根节点:没有父节点的唯一节点。
    • 子节点:一个节点可以直接拥有零个或多个子节点。
    • 父节点:每个子节点都有一个父节点,除了根节点。
    • 叶子节点:没有任何子节点的节点。
    • 兄弟节点:具有相同父节点的节点。
    • 路径:从一个节点到另一个节点的一系列连续的边。
    • 深度:从根节点到特定节点的路径长度。
    • 高度:树中任何节点的最大深度。
  2. 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;
    }
}

在这个例子中,我们创建了一个二叉树,其中每个节点最多有两个子节点:左子节点和右子节点。我们还实现了一个添加新节点的方法,该方法会根据新值与当前节点值的大小关系,将新节点添加到左子树或右子树。

  1. 使用案例:

假设我们要创建一个学生信息的二叉搜索树,我们可以使用上面定义的二叉树类,但是我们需要修改节点类以存储学生的姓名和年龄,如下所示:

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}
    }
}

在这个例子中,我们首先创建了一个学生信息的二叉搜索树,并添加了三个学生的信息。然后,我们分别进行了前序遍历、中序遍历和后序遍历,并打印出了遍历结果。