数据结构第09节：二叉树

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

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

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/774246.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

默安逐日实验室：XDP的应用实践

默安逐日实验室：XDP的应用实践

1. 网络数据包是如何进入进计算机的 众所周知&#xff0c;网络数据包通常需要在TCP/IP协议栈中进行处理&#xff0c;但网络数据包并不直接进入TCP/IP协议栈&#xff1b;相反&#xff0c;他们直接进入网络接口。因此&#xff0c;在数据包进入 TCP/IP 堆栈之前&#xff0c;它们已…
阅读更多...
HTML如何在图片上添加文字

HTML如何在图片上添加文字

HTML如何在图片上添加文字 当我们开发一个页面&#xff0c;插入图片时&#xff0c;需要有一组文字对图片进行描述。那么HTML中如何在图片上添加文字呢&#xff1f;这篇文章告诉你。 先让我们来看下效果图&#xff1a; 句子“这是一张夜空图片”被放置在了图片的左下角。 那么…
阅读更多...
谷粒商城学习-10-docker安装mysql

谷粒商城学习-10-docker安装mysql

文章目录 一&#xff0c;拉取MySQL镜像1&#xff0c;搜索MySQL的Docker镜像2&#xff0c;拉取MySQL镜像3&#xff0c;查看已经拉取的镜像 二&#xff0c;创建、启动MySQL容器1&#xff0c;使用docker run创建启动容器2&#xff0c;使用docker ps查看运行状态的容器3&#xff0c…
阅读更多...
属性描述符初探——Vue实现数据劫持的基础

属性描述符初探——Vue实现数据劫持的基础

目录 属性描述符——Vue实现数据劫持的基础 一、属性描述符是什么&#xff1f; ​编辑 1.1、属性描述符示例 1.2、用属性描述符定义属性及获取对象的属性描述符 1.3、带有读取器和设置器的属性描述符 二、使用属性描述符的情景 2.1、封装和数据隐藏 使用getter和setter…
阅读更多...
论文写作全攻略：Kimi辅助下的高效学术写作技巧

论文写作全攻略：Kimi辅助下的高效学术写作技巧

学境思源&#xff0c;一键生成论文初稿&#xff1a; AcademicIdeas - 学境思源AI论文写作 完成论文写作是一个多阶段的过程&#xff0c;涉及到不同的任务和技能。以下是按不同分类总结的向Kimi提问的prompt&#xff0c;以帮助你在论文写作过程中取得成功&#xff1a; 1. 选题与…
阅读更多...
使用kali Linux启动盘轻松破解Windows电脑密码

使用kali Linux启动盘轻松破解Windows电脑密码

破解分析文章仅限用于学习和研究目的&#xff1b;不得将上述内容用于商业或者非法用途&#xff0c;否则&#xff0c;一切后果请用户自负。谢谢&#xff01;&#xff01; 效果展示&#xff1a; 使用kali Linux可以轻松破解Windows用户及密码 准备阶段&#xff1a; &#xff08…
阅读更多...
RedHat9 | kickstart无人值守批量安装

RedHat9 | kickstart无人值守批量安装

一、知识补充 kickstart Kickstart是一种用于Linux系统安装的自动化工具&#xff0c;它通过一个名为ks.cfg的配置文件来定义Linux安装过程中的各种参数和设置。 kickstart的工作原理 Kickstart的工作原理是通过记录典型的安装过程中所需人工干预填写的各种参数&#xff0c;…
阅读更多...
配置基于用户认证的虚拟主机

配置基于用户认证的虚拟主机

添加账号abc [rootlocalhost conf.d]# htpasswd -c /etc/httpd/zhanghao abc New password: Re-type new password: Adding password for user abc添加账号tom [rootlocalhost conf.d]# htpasswd /etc/httpd/zhanghao tom New password: Re-type new password: Adding pa…
阅读更多...
QT中QDomDocument读写XML文件

QT中QDomDocument读写XML文件

一、XML文件 <?xml version"1.0" encoding"UTF-8"?> <Begin><Type name"zhangsan"><sex>boy</sex><school>Chengdu</school><age>18</age><special>handsome</special>&l…
阅读更多...
平安养老险蚌埠中心支公司开展“78奋力前行”健步走活动

平安养老险蚌埠中心支公司开展“78奋力前行”健步走活动

7月4日&#xff0c;平安养老保险股份有限公司&#xff08;以下简称“平安养老险”&#xff09;蚌埠中心支公司组织员工在张公山公园开展“78奋力前行”健步走活动&#xff0c;传递保险行业的正能量&#xff0c;展现平安养老险的活力与风采。 平安养老险蚌埠中心支公司员工身着…
阅读更多...
【瑞吉外卖 | day02】登录功能完善+员工信息的增改查

【瑞吉外卖 | day02】登录功能完善+员工信息的增改查

文章目录 瑞吉外卖 — day021. 完善登录功能1.1 问题分析1.2 实现 2. 新增员工功能2.1 分析2.2 程序执行过程2.3 程序执行中的异常处理 3. 员工信息分页查询3.1 程序执行过程 4. 启用/禁用员工账号4.1 需求分析4.2 程序执行过程4.3 代码修复 5. 编辑员工信息5.1 需求分析5.2 程…
阅读更多...
基于DMAIC降低气缸体水套芯磕碰伤率

基于DMAIC降低气缸体水套芯磕碰伤率

在制造业的激烈竞争中&#xff0c;产品质量的提升一直是企业追求的目标。气缸体作为汽车发动机的核心部件&#xff0c;其生产过程中的质量控制尤为重要。今天&#xff0c;深圳天行健企业管理咨询公司就来分享一下如何运用DMAIC&#xff08;定义、测量、分析、改进、控制&#x…
阅读更多...
Logstash安装插件失败的问题

Logstash安装插件失败的问题

Logstash安装插件失败的问题 安装 logstash-output-jdbc 失败 报错为&#xff1a; Unable to download data from https://rubygems.org - Net::OpenTimeout: Failed to open TCP connection to rubygems.org:443 (execution expired) (https://rubygems.org/latest_specs.4.…
阅读更多...
[GHCTF 2024 新生赛]UP+——入土为安的第一天

[GHCTF 2024 新生赛]UP+——入土为安的第一天

注意&#xff1a;这道题需要脱壳&#xff0c;而且需要改特征值&#xff0c;详细请看 [LitCTF 2024]hello_upx——入土为安的第一天-CSDN博客 脱完壳发现有256这个特殊的数&#xff0c;是rc4类型的题&#xff0c;最后有一个异或 a "9F041CEFA92386B6F56F27B96155FD42&qu…
阅读更多...
鸿蒙应用开发之Column容器

鸿蒙应用开发之Column容器

这个容器已经使用了很多次，但是还是需要来简单地学习一下，它的主要作用是沿垂直方向布局的容器。 对于布局这种容器，需要看到显示的效果才会比较明白。 先来看下面这个界面： 先在最外面建立一个Column容器，space和方框显示等显示内容都是作为一行进行排列。现在这里设置为…
阅读更多...
智能升级，监控无界——全新安全生产生态算法一体机上线

智能升级，监控无界——全新安全生产生态算法一体机上线

安全生产生态算法一体机 安全生产生态算法一体机是万物纵横推出的一款AI算法软硬一体生态产品&#xff0c;重点面向安全生产领域&#xff0c;采用BM1684强劲AI芯片&#xff0c;内置安全生产场景所需的多种专用AI算法&#xff0c;面向各场景的人员监控、规范作业、异常检测等应…
阅读更多...
maven项目启动的时候,自动启动netty

maven项目启动的时候,自动启动netty

1.写一个监听器,重开一个线程初始化,netty,一定要重开一个线程去启动,要不会阻塞的 public class StartupListener implements ServletContextListener {Overridepublic void contextInitialized(ServletContextEvent sce) {// 在Web应用启动时启动WebSocket服务器new Thread(…
阅读更多...
2024 MWC上海：Infobip引领CPaaS新纪元

2024 MWC上海：Infobip引领CPaaS新纪元

作为全球通信行业一年一度的顶级盛会&#xff0c;MWC上海2024于近日在上海盛大召开。Infobip以其前瞻性的CPaaS&#xff08;Communication Platform as a Service&#xff0c;通信平台即服务&#xff09;解决方案和广泛的合作伙伴网络&#xff0c;成为了众多参展嘉宾瞩目的焦点…
阅读更多...
Leetcode.342 4的幂

Leetcode.342 4的幂

给定一个整数&#xff0c;写一个函数来判断它是否是 4 的幂次方。如果是&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 整数 n 是 4 的幂次方需满足&#xff1a;存在整数 x 使得 n 4x 示例 1&#xff1a; 输入&#xff1a;n 16 输出&#xff1a;true示…
阅读更多...
QT的编译过程（底层逻辑）

QT的编译过程（底层逻辑）

qmake -project 用于从源代码生成项目文件&#xff0c;qmake 用于从项目文件生成 Makefile&#xff0c;而 make 用于根据 Makefile 构建项目。 详细解释&#xff1a; qmake -project 这个命令用于从源代码目录生成一个初始的 Qt 项目文件&#xff08;.pro 文件&#xff09;。它…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站