数据结构第09节：二叉树

🕗 发布于 2024-07-08 17:21 数据结构 python 算法 java 二叉树

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

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

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

原文地址：https://blog.csdn.net/hummhumm/article/details/140205457

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：外部晶振由12M变更为8M，怎么修改时钟配置
下一篇：AVIO自定义读写

Python高级编程模式和设计模式
【代码】Python高级编程模式和设计模式。
阅读更多2024-11-15
【代码随想录】刷题记录(29)-用栈实现队列
思路其实很简单，有点像那种小学益智游戏，比如那种给两个箱子，花几步把最下面的砖块搬出来的游戏。这道题其实就是类似这种动作，因为栈是遵循“先入后出”的原则，所以如果要拿出最先入栈stack_in的元素（
阅读更多2024-11-15
Jdbc学习笔记（四）--PreparedStatement对象、sql攻击（安全问题）
在需要用户输入的地方，用户输入的是SQL语句的片段，最终用户输入的SQL片段与我们DAO中写的SQL语句合成一个完整的SQL语句！例如用户在登录时输入的用户名和密码都是为SQL语句的片段！所以，建议大
阅读更多2024-11-15
Redis简介、数据结构、高性能读写、持久化机制、分布式架构
Redis简介、数据结构、高性能读写、持久化机制、分布式架构
阅读更多2024-11-15
扩散模型生成 360度场景
扩散模型生成 360度场景
阅读更多2024-11-15
css文字间距撑满横向距离
【代码】css文字间距撑满横向距离。
阅读更多2024-11-15
Python常用魔术方法（学习笔记）
Python中常用魔术方法的使用。
阅读更多2024-11-15
如何在 Ubuntu 上安装 RStudio IDE（R语言集成开发环境） ?
RStudio 是一个功能强大的 R 语言集成开发环境(IDE)，R 是一种主要用于统计计算和数据分析的编程语言。任何从事数据科学项目或任何其他涉及 R 的类似任务的人，RStudio 都可以使您的工
阅读更多2024-11-15
开源对象存储新选择：在Docker上部署MinIO并实现远程管理
开源对象存储新选择：在Docker上部署MinIO并实现远程管理
阅读更多2024-11-15
Hot100 42接雨水
根据题目描述，雨水总和就是蓝色方块加起来的总和。怎么思路很简单，为了不让水溢出，那么两边只能取最短的一截。根据当前柱子所处的位置，算出前面最高的和后面最高的柱子（因为水是流动的），这样求最小的柱子长度
阅读更多2024-11-15

数据结构第09节：二叉树

相关文章