🌳深度学习二叉树，掌握数据结构核心力量！

  咦咦咦，各位小可爱，我是你们的好伙伴——bug菌，今天又来给大家普及Java SE相关知识点了，别躲起来啊，听我讲干货还不快点赞，赞多了我就有动力讲得更嗨啦！所以呀，养成先点赞后阅读的好习惯，别被干货淹没了哦~

🏆本文收录于「滚雪球学Java」专栏，专业攻坚指数级提升，助你一臂之力，带你早日登顶🚀，欢迎大家关注&&收藏！持续更新中，up！up！up！！

环境说明：Windows 10 + IntelliJ IDEA 2021.3.2 + Jdk 1.8

📝 前言

嘿，朋友们！如果你对数据结构有兴趣，尤其是二叉树，那你可真是来对了！二叉树在数据结构的世界里可是个“大明星”，不管是排序、搜索还是数据存储都离不开它。今天我们就用 Java 语言带你深入理解二叉树，看完你就会发现，原来二叉树这么有趣！

📑 摘要

本文以 Java 语言为基础，带你从零开始学习二叉树。我们会从基础结构、常用方法、源码解析到实际案例一步步深入，帮助你掌握二叉树的核心。无论你是编程新手，还是资深开发者，都能从这篇文章中获得收获。准备好了吗？那就让我们一起走进二叉树的世界吧！

🧐 简介

二叉树，简单来说就是每个节点最多有两个子节点的树形结构。二叉树不仅是数据结构的基础，在很多算法和编程题中也是必不可少的考点。理解二叉树的各种操作和应用场景，不仅会提升你的算法功底，还会增强你的编程能力。

📜 概述

二叉树 的核心概念并不复杂，但在应用中会涉及到递归、栈、队列等高级操作。我们会从基本的二叉树结构入手，介绍创建节点、遍历、插入、删除等核心操作，再深入解析它在搜索树、平衡树等领域中的应用。

💻 核心源码解读

下面我们直接进入二叉树的源码解读部分，让你对二叉树的实现有更深入的理解。我们使用 Java 来演示最常见的二叉树结构和操作。

// 🌲 定义节点类
class TreeNode {
    int data;
    TreeNode left, right;

    public TreeNode(int data) {
        this.data = data;
        left = right = null;
    }
}

// 🌲 二叉树类
public class BinaryTree {
    TreeNode root;

    // 🌿 插入节点
    public TreeNode insert(TreeNode root, int data) {
        if (root == null) {
            return new TreeNode(data);
        } else {
            if (data < root.data) {
                root.left = insert(root.left, data);
            } else {
                root.right = insert(root.right, data);
            }
        }
        return root;
    }

    // 🌿 前序遍历
    public void preOrder(TreeNode node) {
        if (node != null) {
            System.out.print(node.data + " ");
            preOrder(node.left);
            preOrder(node.right);
        }
    }
}

上面的代码定义了一个简单的二叉树类 BinaryTree，包含节点插入和前序遍历的方法。通过这段代码，大家可以清楚地看到二叉树的基本实现。

代码解析：

在本次的代码演示中，我将会深入剖析每句代码，详细阐述其背后的设计思想和实现逻辑。通过这样的讲解方式，我希望能够引导同学们逐步构建起对代码的深刻理解。我会先从代码的结构开始，逐步拆解每个模块的功能和作用，并指出关键的代码段，并解释它们是如何协同运行的。通过这样的讲解和实践相结合的方式，我相信每位同学都能够对代码有更深入的理解，并能够早日将其掌握，应用到自己的学习和工作中。

接下来就让我们来逐行分析这段 Java 代码，它定义了一个简单的二叉树结构，包括节点类 TreeNode 和二叉树类 BinaryTree，实现了二叉树的插入和前序遍历操作。

🌲 定义节点类 TreeNode

class TreeNode {
    int data;
    TreeNode left, right;

    public TreeNode(int data) {
        this.data = data;
        left = right = null;
    }
}

1. 属性定义：

   • int data：存储节点的数据。
   • TreeNode left 和 TreeNode right：分别表示左子节点和右子节点。

2. 构造函数：

   • public TreeNode(int data)：接受一个整数参数 data，初始化该节点的数据，并将 left 和 right 指针初始化为 null，表示该节点初始没有子节点。

该 TreeNode 类的作用是定义二叉树的基本组成单元，每个节点可以存储一个数据并连接到其左右子节点。

🌲 二叉树类 BinaryTree

public class BinaryTree {
    TreeNode root;

• TreeNode root：定义了二叉树的根节点 root。根节点是二叉树的起始节点，二叉树的所有操作都是基于 root 开始。

🌿 插入节点方法 insert

public TreeNode insert(TreeNode root, int data) {
    if (root == null) {
        return new TreeNode(data);
    } else {
        if (data < root.data) {
            root.left = insert(root.left, data);
        } else {
            root.right = insert(root.right, data);
        }
    }
    return root;
}

1. 方法参数：

   • TreeNode root：当前节点，表示当前递归中的父节点。
   • int data：要插入的节点数据。

2. 逻辑分析：

   • 根节点为空：如果 root 为 null，表示此处可以插入新节点。创建一个包含 data 的新节点并返回，将其作为当前子树的根节点。
   • 递归插入：
     • 如果 data 小于当前 root 节点的 data，递归调用 insert 方法，将 data 插入到 root 的左子树。
     • 否则，将 data 插入到 root 的右子树。
   • 这个递归逻辑保证了二叉树的结构，所有较小的值都插入到左子树，较大的值插入到右子树，形成一个 二叉搜索树。

3. 返回值：

   • 返回插入节点后的根节点 root，确保当前子树的根节点不变。

🌿 前序遍历方法 preOrder

public void preOrder(TreeNode node) {
    if (node != null) {
        System.out.print(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }
}

1. 方法参数：

   • TreeNode node：当前遍历到的节点。

2. 前序遍历：

   • 前序遍历的顺序为：访问当前节点 -> 遍历左子树 -> 遍历右子树。
   • 在 if 判断中，首先检查 node 是否为 null，如果 node 不为空，则：
     • 打印 node.data，表示访问当前节点。
     • 递归调用 preOrder(node.left) 遍历左子树。
     • 递归调用 preOrder(node.right) 遍历右子树。

3. 递归终止条件：

   • 当 node 为 null 时，返回空，不再继续递归。

通过 preOrder 方法，我们可以按前序遍历的顺序访问二叉树中的每个节点，并依次输出数据。

总结

这段代码实现了二叉树的基本结构和操作：

• TreeNode 类是节点的定义，包含数据和指向子节点的指针。
• BinaryTree 类包含了二叉树的插入和前序遍历方法。
• insert 方法保证了二叉搜索树的特性。
• preOrder 方法按前序顺序遍历二叉树，输出节点数据。

这段代码提供了二叉树的基本操作，可以作为更复杂数据结构和算法的基础。

📝 案例分析

让我们尝试插入几个数据，看看二叉树是如何一步步构建的。假设我们插入的数据顺序为：7、4、9、1、5。插入顺序会影响树的结构，最终形成的树如下所示：

      7
     / \
    4   9
   / \
  1   5

通过这个案例，可以直观地理解二叉树的构建过程和数据的分布方式。

🌍 应用场景演示

二叉树的应用场景非常广泛，比如：

• 文件目录管理：操作系统使用树形结构管理文件和文件夹。
• 数据库索引：数据库使用二叉树（如 B 树）来提高数据查找效率。
• 表达式计算：计算器可以利用二叉树来表示和计算表达式的值。

这些场景让我们看到二叉树的强大功能。

👍 优缺点分析

• 优点：

  • 查找、插入和删除操作的效率较高。
  • 结构清晰，适合递归操作。

• 缺点：

  • 对平衡性有要求，否则可能导致性能下降。
  • 在某些情况下，空间开销较大。

📝 类代码方法介绍及演示

下面我们介绍二叉树中的一些重要方法，包括插入、遍历和查找。

🌲 插入方法

插入方法用于将新的数据节点插入到树中。插入数据的规则是：小于根节点的值放在左子树，大于的放在右子树。

🌲 遍历方法

二叉树有三种主要的遍历方式：前序、中序和后序遍历。不同遍历方式会得到不同的节点访问顺序。

✅ 测试用例

下面我们编写一个简单的 main 方法来测试插入和遍历的功能。

public class Main {
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = tree.insert(tree.root, 7);
        tree.insert(tree.root, 4);
        tree.insert(tree.root, 9);
        tree.insert(tree.root, 1);
        tree.insert(tree.root, 5);

        System.out.println("前序遍历结果：");
        tree.preOrder(tree.root);
    }
}

🧪 测试结果预期

执行上面的代码，前序遍历的预期输出应该为：

7 4 1 5 9

这样我们可以清晰地看到二叉树中节点的访问顺序。

🔍 测试代码分析

在 main 方法中，我们创建了一个 BinaryTree 实例，依次插入了 5 个节点。通过 preOrder 方法可以验证插入和前序遍历是否按预期进行。整个代码逻辑简洁，易于理解。

📌 小结

通过以上内容，我们系统地学习了 Java 语言中二叉树的基本概念和实现。二叉树是一种重要的数据结构，掌握它不仅能提高代码质量，还能帮助你在算法题中更得心应手。

🔚 总结

二叉树虽然看似简单，但其应用广泛且知识点多。我们从二叉树的基本定义出发，通过 Java 的代码示例带你逐步深入。学习数据结构不是一朝一夕的事情，需要在不断练习和实际应用中理解。希望这篇文章能为你的二叉树学习之路提供帮助！

❤️ 寄语

学习编程就像登山，每一步都很重要。加油吧，不断地探索，不断地进步，二叉树只是你编程之旅中的一个小小开始！

  …

  好啦，这期的内容就基本接近尾声啦，若你想学习更多，可以参考这篇专栏总结《「滚雪球学Java」教程导航帖》，本专栏致力打造最硬核 Java 零基础系列学习内容，🚀打造全网精品硬核专栏，带你直线超车；欢迎大家订阅持续学习。

🌴附录源码

  如上涉及所有源码均已上传同步在「Gitee」，提供给同学们一对一参考学习，辅助你更迅速的掌握。

☀️建议/推荐你

  无论你是计算机专业的学生，还是对编程有兴趣的小伙伴，都建议直接毫无顾忌的学习此专栏「滚雪球学Java」，bug菌郑重承诺，凡是学习此专栏的同学，均能获取到所需的知识和技能，全网最快速入门Java编程，就像滚雪球一样，越滚越大，指数级提升。

  最后，如果这篇文章对你有所帮助，帮忙给作者来个一键三连，关注、点赞、收藏，您的支持就是我坚持写作最大的动力。

  同时欢迎大家关注公众号:「猿圈奇妙屋」 ，以便学习更多同类型的技术文章，免费白嫖最新BAT互联网公司面试题、4000G pdf电子书籍、简历模板、技术文章Markdown文档等海量资料。

📣Who am I?

我是bug菌，CSDN | 掘金 | InfoQ | 51CTO | 华为云 | 阿里云 | 腾讯云 等社区博客专家，C站博客之星Top30，华为云2023年度十佳博主，掘金多年度人气作者Top40，掘金等各大社区平台签约作者，51CTO年度博主Top12，掘金/InfoQ/51CTO等社区优质创作者；全网粉丝合计 30w+；硬核微信公众号「猿圈奇妙屋」，欢迎你的加入！免费白嫖最新BAT互联网公司面试真题、4000G PDF电子书籍、简历模板等海量资料，你想要的我都有，关键是你不来拿哇。