数据结构（二叉树）

前言：

在数据结构那片浩瀚无垠、仿若神秘宇宙的天地里，二叉树宛如一颗散发着独特光辉、极为耀眼的星辰。它就像一位技艺精湛的建筑师，运用独特的二叉分支结构，精心构建起层次分明、秩序井然的数据组织 “大厦”。根节点仿若大厦的坚实基石与起始点，向两侧伸展的左右子树好似大厦中对称分布的稳固支柱，有条不紊地将各类信息收纳其中。

于算法这片充满挑战与机遇的 “战场” 上，二叉搜索树好似一位行动敏捷、效率超高的 “情报员”，在数据的海洋里助力高效查找等关键 “情报任务”，而平衡二叉树则如同一位沉稳坚毅的 “守护者”，时刻确保 “战场局势” 稳定，即便面对汹涌而来的复杂数据 “敌军”，也能从容应对，游刃有余。其先序、中序、后序遍历方式，仿佛是多把神奇的 “魔法钥匙”，能够开启一扇扇通往高效数据处理与精准计算的 “智慧之门”，在众多复杂的计算任务里大显身手。

在实际应用的广阔 “舞台” 上，网络路由仿佛是依赖它搭建的超级 “交通枢纽”，精准引导数据 “车辆” 快速畅行；人工智能中的决策树好似凭借它打造的敏锐 “智慧之眼”，深入洞察数据背后隐藏的规律；就连文件系统也因它构建起如同 “智能档案库” 般的高效管理模式。接下来，就让我们满怀期待地一同深入二叉树这奇妙无比、充满无限可能的世界，尽情领略其独特魅力与巨大价值。

1 二叉树（讲解）

1. 树型结构（了解）

1.1 概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看 起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点： 有一个特殊的结点，称为根结点，根结点没有前驱结点

除根结点外，其余结点被分成M(M > 0)个互不相交的集合T1、T2、......、Tm，其中每一个集合Ti (1 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继

树是递归定义的。

注意：树形结构中，子树之间不能有交集，否则就不是树形结构

1.2 概念（重要）

假设我们有如下这棵树：

1.结点的度：一个结点含有子树的个数称为该结点的度；

在图中：

• A 的度为 3（它有三个子结点：B、C、D）。
• B 的度为 2（它有两个子结点：E 和 F）。
• C 的度为0（它没有子结点）。
• D 的度为 3（有三个子结点：G、H 和 I）。
• E、F、G、H、I 的度都为0（它们是叶子结点，没有子结点）。
• J 和 K 的度为 0（它们是叶子结点）。

2.树的度：一棵树中，所有结点度的最大值称为树的度；

根据上述树，树的度为3，因为A和D的度都是3，这是树中最大的度。

3.叶子结点或终端结点：度为0的结点称为叶结点；

在上图中，叶子结点是：C、E、F、G、H、I、J、K（这些结点都没有子结点）。

4双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；

在图中：

• A 是 B、​​C、D 的父结点。
• B 是 E、F 的父结点。
• D 是 G、H、I 的父结点。
• F 是 J、K 的父结点。

5.孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点；

在图中：

• B、C、D 是 A 的孩子结点。
• E、F是B的孩子结点。
• G、H、I 是 D 的孩子结点。
• J、K 是 F 的孩子结点。

6.根结点：一棵树中，没有双亲结点的结点；

A是根结点，因为它没有父结点。

7.结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推

在图中：

• 根结点A的层次为1。
• A的孩子结点B、C、D的层次为2。
• B 的孩子结点 E 和 F、D 的孩子结点 G、H 和 I 的层次为 3。
• F 的孩子结点 J 和 K 的层次为 4。

8.树的高度或深度：树的高度是树中结点的最大层数，或者说，从根结点到最深的叶子结点的路径的长度。

在上图中，树的高度为4，因为从根结点A到叶子结点J或K需要经过4层。

9.非终端结点或分支结点：度不为0的结点；

在上图中，非结局点是：A、B、D、F，因为这些结点都有子结点。

10.兄弟结点：具有相同父结点的结点互称为兄弟结点；

在图中：

• B 和 C 是兄弟结点，因为它们都有相同的父结点 A。
• G 和 H 是兄弟结点，因为它们都有相同的父结点 D。

11.堂兄弟结点：双亲在同一层的结点互为堂兄弟；

如上图：H和I是堂兄弟结点，因为他们的父结点D都处于同一层次，而D是A的孩子结点。

12结点的祖先：从根到该结点所经分支上的所有结点；

如上图：A 是祖先的所有结点。具体来说：

• A是B、C、D、E、F、G、H、I、J、K的祖先。
• B是E和F的祖先。
• D是G、H、I的祖先。
• F 是 J 和 K 的祖先。

13.子孙：以某结点为根的子树中任一结点都称为该结点的子孙。

如上图：所有结点都是A的子孙

• B的子孙包括E和F。
• D 的子孙包括 G、H 和 I。
• F的子孙包括J和K。

14. 森林：由m（m>=0）棵互不相交的树组成的集合称为森林

如果我们把上面的树中去掉根结点A，就可以得到一个森林。例如，去掉根结点A后，剩下的部分可以认为是独立的树，形成森林：

• 一棵树以B为根，包含E和F。
• 一棵树以D为根，包含G、H和I。
• 一棵树以F为根，包含J和K。

1.3 树的表示形式（了解）：

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：双亲表示法， 孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

2二叉树概念

2.1什么是二叉树？

二叉树（Binary Tree）是一种特殊的树形数据结构，它有以下几个基本特征：

• 每个节点最多有两个子节点（即左子节点和右子节点）。
• 树的结构是分层的，即从根节点开始，往下逐层分布。

在树结构中，节点之间的形成了层次结构。二叉树的根节点是树的起始节点，它没有父节点，而所有其他节点都是从根节点出发，逐层通过左右子节点连接起来。

二叉树的基本术语

• 根节点（Root）：二叉树的起始节点，树的最上面一个节点。
• 父节点（Parent Node）：有子节点的节点。
• 子节点（Child Node）：由父节点派生出来的节点。
• 叶节点（Leaf Node）：没有子节点的节点。
• 兄弟节点（Sibling Node）：同一个父节点下的子节点。

樹的深度和高度

• 树的深度：树中某个节点到根节点的路径长度。根节点的深度是0，根节点的子节点的深度是1，依此类推。
• 树的高度：树中从根节点到最远的叶节点的路径长度。叶节点的高度是0，其他节点的高度是其子节点的最大高度加1。

2.2 二叉树的类型：

1满二叉树（满二叉树）

满二叉树是每个非叶子节点都有两个子节点的二叉树。相反，如果一个节点有子节点，那么它必须有两个子节点。满二叉树的所有叶子节点都在同一层。

例子：

在满二叉树中，节点总数是2^h - 1，其中h是树的高度（根节点的高度为0）。

2.二叉树（完全二叉树）

二叉树是一种特殊的二叉树，除了最底层的外，其他每一层的完全节点都被填满，且最底层的节点都向左对齐。

例子：

二叉树的优点是节点的填充比较紧密，基本上实现和存储。对于一个完全有n节点的完全二叉树，它的高度为O(log n)。

3.平衡二叉树（平衡二叉树）

平衡二叉树是一种特殊的二叉树，它的左右子树的高度差的绝对值不超过1。常见的平衡二叉树有AVL树和红黑树。平衡二叉树的插入、删除和查找操作时间复杂度第一O(log n)。

例子：

平衡二叉树保证了树的高度继续保持较低，从而保证了高效的查找、增删操作。

4.二叉搜索树（二叉搜索树，BST）

二叉搜索树是一种特殊的二叉树，它满足以下条件：

• 对于任意一个节点x，节点x的左子树中所有节点的值都小于x的值。
• 节点x的右子树中所有节点的值都大于x的值。

例子：

二叉搜索树的插入、删除、查找操作的时间复杂度在一般情况下是这样O(log n)，但在最坏的情况下，如果树变成了链表（如按升序或降序插入元素），则时间复杂度为O(n)。

2.3二叉树的性质

1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 (i>0)个结点

2. 若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是 (k>=0)

3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1

4. 具有n个结点的完全二叉树的深度k为 上取整

5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i 的结点有：

若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点

若2i+1，左孩子序号：2i+1，否则无左孩子

若2i+2，右孩子序号：2i+2，否则无右孩子

2. 二叉树（实现）

       

从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。

2.1 二叉树的遍历

1.前中后序遍历

学习二叉树结构，最简单的方式就是遍历。所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结 点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题(比如：打印节点内容、节点内容加 1)。 遍历是二叉树上最重要的操作之一，是二叉树上进行其它运算之基础。     

在遍历二叉树时，如果没有进行某种约定，每个人都按照自己的方式遍历，得出的结果就比较混乱，如果按 照某种规则进行约定，则每个人对于同一棵树的遍历结果肯定是相同的。如果N代表根节点，L代表根节点的 左子树，R代表根节点的右子树，则根据遍历根节点的先后次序有以下遍历方式：

NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点--->根的左子树--->根的右子树。

LNR：中序遍历(Inorder Traversal)——根的左子树--->根节点--->根的右子树。

LRN：后序遍历(Postorder Traversal)——根的左子树--->根的右子树--->根节点。

2.前序遍历

• 递归条件：root == null当时，梯度停止。这是处理空树或子树的必要条件，避免对null节点的操作。
• 访问根节点：在前序遍历中，首先访问根节点，System.out.print(root.val + " ")打印当前节点的值。
• 遍历遍历左子树：调用preorderTraversal(root.left)来遍历当前节点的左子树。
• 遍历遍历右子树：调用preorderTraversal(root.right)来遍历当前节点的右子树。

• 前序遍历的顺序

  对于给定的二叉树，前序遍历的顺序为：根节点 → 左子树 → 右子树。依次，在遍历过程中，首先访问根节点，然后递归地访问左子树，最后递归地访问右子树。

3.中序遍历

• 递归条件：root == null流行，地铁停止。这是防止对空节点进行访问，确保不会出现代码异常。
• 遍历遍历左子树：在中序遍历中，首先遍历遍历左子树inorderTraversal(root.left)。
• 访问根节点：然后打印根节点的值System.out.print(root.val + " ")。
• 遍历遍历右子树：最后遍历遍历右子树inorderTraversal(root.right)。

• 中序遍历的顺序

  对于给定的二叉树，中序遍历的顺序为：根子树→根节点→右子树。遍历左，遍历时，首先访问左子树，访问完左子树后访问根节点，然后访问右子树子树。中序遍历常用于**二叉搜索树（BST）**中，因为它可以按升序输出节点。

4.后序遍历

• 递归条件：root == null流行，地铁停止。这是防止对空节点进行访问，确保不会出现代码异常。
• 遍历遍历左子树：首先遍历遍历左子树postorderTraversal(root.left)。
• 遍历遍历右子树：继续遍历遍历右子树postorderTraversal(root.right)。
• 访问根节点：最后打印根节点的值System.out.print(root.val + " ")，这正符合后序遍历的规则。

• 后序遍历的顺序：

  在后序遍历中，遍历的顺序为：左子树→右子树→根节点。其中，首先遍历左子树，继续遍历右子树，最后访问根节点。这种遍历方式通常用于需要先处理子树再处理根节点的场景，如删除树节点、释放内存、计算子树的结果等。

5.层序遍历

层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在 层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层 上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

public static void levelOrderTraversal(Node root) {
        if (root == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            System.out.print(cur.val + " ");
            if (cur.left!= null) {
                queue.add(cur.left);
            }
            if (cur.right!= null) {
                queue.add(cur.right);
            }
        }
    }

1. 空树判断及初始化：
   首先判断传入的二叉树的根节点 root 是否为 null，如果是 null，说明是空树，直接使用 return 结束方法，无需进行后续遍历操作。若根节点不为 null，则创建一个队列 queue（这里使用 LinkedList 来实现队列的功能），并将根节点 root 加入队列，准备开始层序遍历。
2. 层序遍历循环：
   进入一个 while 循环，循环条件是队列 queue 不为空。在每次循环中：
   • 首先通过 queue.poll() 方法取出队列的队首节点，并赋值给 cur 变量，这个节点就是当前层正在遍历的节点。
   • 然后将当前节点 cur 的值输出（这里只是简单地打印输出，可以根据实际需求进行更复杂的处理，比如将节点值收集到一个列表中等），即 System.out.print(cur.val + " ");。
   • 接着检查当前节点 cur 的左子节点，如果左子节点 cur.left 不为 null，就将其加入队列 queue，以便后续遍历到下一层时可以处理它。
   • 同样地，检查当前节点 cur 的右子节点，如果右子节点 cur.right 不为 null，也将其加入队列 queue。

2.2二叉树的操作

2.2.1 二叉树中的个数

方法一：

• 静态变量定义：
  private static int Uesize = 0; 定义了一个私有的静态整型变量 Uesize，静态变量属于类级别，所有该类的实例对象共享这个变量，在这里它被初始化为 0，用于记录树结构中节点的个数，在 size 方法的递归调用过程中会不断更新其值。
• size 方法逻辑分析：
  • 递归终止条件判断：
    方法 size(TreeNodes root) 接收一个树节点指针（或引用） root 作为参数，首先通过 if (root == null) 判断传入的根节点是否为空。如果根节点为空，意味着当前要统计的树为空树，没有节点可供统计，直接使用 return 结束当前方法调用，不再进行后续操作。
  • 节点数量统计与递归调用：
    当根节点不为空时，执行 Uesize++; 语句，这会将用于记录节点数量的静态变量 Uesize 的值加 1，表示已经访问到了一个节点，将其计入总数。然后分别递归调用 size(root.left); 和 size(root.right);，这两个调用会分别进入根节点的左子树和右子树，以同样的逻辑去统计左子树和右子树中的节点个数，如此递归下去，直到遍历完整个树的所有节点为止，最终 Uesize 变量记录的值就是整棵树的节点总数。

方法二：

• 递归终止条件判断及返回值设定（基础情况）：
  首先通过 root == null 来判断传入的根节点是否为空。如果根节点 root 为 null，意味着当前要统计的树是空树，没有节点存在，按照计算树节点个数的逻辑，此时直接返回 0，表示这棵空树的节点数量就是 0，以此作为递归的终止条件，避免无限递归下去。
• 递归计算及汇总（递归情况）：
  当根节点不为空时，也就是 root!= null 的情况，执行 size1(root.left) + size1(root.right) + 1 这部分表达式。
  • size1(root.left) 会递归地调用 size1 方法去计算根节点的左子树的节点个数。
  • size1(root.right) 则递归地调用 size1 方法去计算根节点的右子树的节点个数。
  • 最后加上 1，这 1 代表的就是当前根节点本身，因为在统计整棵树节点个数时，根节点也是树的一个节点，需要将其计入总数。然后把左子树节点个数、右子树节点个数以及根节点（也就是 1 个）相加起来，得到的结果就是以 root 为根的整棵树的节点个数，最终作为返回值返回。

2.2.2获取叶子节点的个数

方法一：

• 静态变量定义：
  public static int leafSize = 0; 定义了一个公共的静态整型变量 leafSize，由于是静态变量，它属于类级别，所有该类的实例对象都共享这个变量。初始化为 0，其作用就是用于累计树中叶子节点的个数，在后续递归遍历树的过程中会根据条件不断更新其值。
• getLeafNodeCount 方法逻辑分析：
  • 递归终止条件判断：
    方法 getLeafNodeCount(TreeNodes root) 接收树的根节点 root 作为参数，首先通过 if(root == null) 判断传入的根节点是否为空。如果根节点为空，说明当前没有树需要统计叶子节点，直接使用 return 结束方法执行，不再进行后续操作，这是递归的基础情况，避免了无限递归下去。
  • 叶子节点判断与数量统计：
    当根节点不为空时，进入 if(root.left == null && root.right == null) 条件判断，该条件用于判断当前节点是否为叶子节点，也就是检查当前节点的左子树和右子树是否都为空，如果都为空，那么当前节点就是叶子节点，此时执行 leafSize++; 语句，将用于记录叶子节点数量的静态变量 leafSize 的值加 1，表示找到了一个叶子节点并计入总数。
  • 递归调用：
    无论当前节点是否为叶子节点，都会接着执行 getLeafNodeCount(root.left); 和 getLeafNodeCount(root.right); 这两个递归调用语句，它们分别会进入根节点的左子树和右子树，以同样的逻辑去判断子树中的叶子节点并统计数量，如此递归下去，直到遍历完整个树的所有节点为止，最终 leafSize 变量所记录的值就是整棵树的叶子节点总数。

方法二：

• 递归终止条件及返回值设定（基础情况）：
  • 首先通过 if(root == null) 判断传入的根节点是否为空。若根节点 root 为 null，意味着当前要统计的树不存在（是空树），按照计算叶子节点个数的逻辑，此时直接返回 0，表示空树中叶子节点数量就是 0，这作为递归的第一个终止条件，避免陷入无限递归。
  • 接着通过 if(root.left == null && root.right == null) 判断当前节点是否为叶子节点，即检查其左子树和右子树是否都为空。若满足此条件，说明当前节点就是叶子节点，按照规则，此时返回 1，代表找到了一个叶子节点，以此作为递归的另一个终止条件，同时也为后续的递归计算提供了基本的计数单位。
• 递归计算及汇总（递归情况）：
  当根节点既不为空，也不是叶子节点时（即上述两个 if 条件都不满足的情况），执行 return getLeafNodeCount1(root.left) + getLeafNodeCount1(root.right); 语句。
  • getLeafNodeCount1(root.left) 会递归地调用本方法去计算根节点的左子树中的叶子节点个数。
  • getLeafNodeCount1(root.right) 则递归地调用本方法去计算根节点的右子树中的叶子节点个数。
  • 最后将左子树的叶子节点个数与右子树的叶子节点个数相加，得到的结果就是以当前 root 为根节点的整棵树（除去已经判断过的根节点本身，因为它不是叶子节点）的叶子节点个数，以此作为返回值返回，整个递归过程会不断深入到各层子树中，直至遇到空子树或者叶子节点，再逐步回溯并汇总各子树的叶子节点数量，最终得出整棵树的叶子节点总数。

2.2.3获取第K层节点的个数

• 递归终止条件及返回值设定（基础情况）：
  • 首先通过 if(root == null) 判断传入的根节点是否为空。若根节点 root 为 null，意味着当前没有实际的树可供操作，按照计算树某一层节点个数的逻辑，此时直接返回 0，表示空树在任何层都不存在节点，这作为第一个递归终止条件，避免陷入无限递归。
  • 接着通过 if(k == 1) 判断当前要统计的层数 k 是否为 1。若 k 等于 1，说明要统计的就是树的第一层（也就是根节点所在层），此时返回 1，因为根节点就是这一层唯一的节点，这作为第二个递归终止条件，同时也为后续的递归计算提供了基础的计数单位。
• 递归计算及汇总（递归情况）：
  当根节点不为空且要统计的层数 k 大于 1 时，执行 return getLevelNodeCount(root.left,k - 1) + getLevelNodeCount(root.right,k - 1); 语句。
  • getLevelNodeCount(root.left,k - 1) 会递归地调用本方法去计算以根节点的左子树为根的子树中第 k - 1 层的节点个数。这里将层数减 1 是因为在向下深入一层子树时，相对原树来说层数就减了 1，例如原树中第 3 层节点在左子树里对应的就是第 2 层节点（假设左子树存在）。
  • getLevelNodeCount(root.right,k - 1) 同样递归地调用本方法去计算以根节点的右子树为根的子树中第 k - 1 层的节点个数，原理与左子树的计算一致。
  • 最后将左子树中对应层的节点个数与右子树中对应层的节点个数相加，得到的结果就是以当前 root 为根节点的整棵树中第 k 层的节点个数，以此作为返回值返回。整个递归过程会持续深入到各层子树中，根据不同的 k 值和子树情况不断重复上述计算，直至达到相应的递归终止条件，然后逐步回溯并汇总各子树对应层的节点数量，最终得出整棵树第 k 层的节点总数。

2.2.4获取二叉树的高度

• 递归终止条件及返回值设定（基础情况）：
  通过 if(root == null) 判断传入的根节点是否为空。若根节点 root 为 null，这意味着当前没有实际的树存在（是空树），按照树高度的定义，空树的高度为 0，所以此时直接返回 0，以此作为递归的终止条件，避免陷入无限递归的情况。
• 递归计算及汇总（递归情况）：
  当根节点不为空时，执行 return 1 + Math.max(HeightOfTree(root.left), HeightOfTree(root.right)); 语句。
  • 首先，1 代表的是当前根节点这一层，因为在计算树的高度时，每一层都要算上一个节点，根节点所在层自然计为 1 层。
  • 然后，HeightOfTree(root.left) 会递归地调用本方法去计算根节点的左子树的高度，HeightOfTree(root.right) 则递归地调用本方法去计算根节点的右子树的高度。
  • Math.max(HeightOfTree(root.left), HeightOfTree(root.right)) 这部分是取左子树高度和右子树高度中的最大值，这是因为树的高度取决于其最深的子树路径，所以要取较长的那条子树路径高度来加上根节点这一层（也就是加 1），得到的结果就是以当前 root 为根节点的整棵树的高度，最后将其作为返回值返回。整个递归过程会不断深入到各层子树中，持续比较不同子树的高度，直至遇到空子树（返回 0），再逐步回溯并汇总各子树高度情况，最终得出整棵树的高度。

2.2.5检测值为value的元素是否存在

• 递归终止条件及返回值设定（基础情况）：
  • 首先通过 if(root == null) 判断传入的根节点是否为空。若根节点 root 为 null，意味着当前要查找的树不存在（是空树），自然不可能找到值为 val 的节点，所以此时直接返回 null，这作为递归的第一个终止条件，避免陷入无限递归的情况。
  • 接着通过 if (root.val == val) 判断当前根节点的值是否等于要查找的值 val。若相等，说明找到了目标节点，直接返回当前根节点 root，这是找到了目标值的情况，也是递归过程中一种成功返回的终止条件。
• 递归查找及返回（递归情况）：
  当根节点不为空且根节点的值不等于 val 时，进入递归查找阶段：
  • 先执行 TreeNodes leftT = getvalues(root.left,val); ，通过递归调用本方法去查找根节点的左子树中是否存在值为 val 的节点，并将返回的结果赋值给 leftT 变量。
  • 然后通过 if (leftT!= null) 判断在左子树中是否找到了目标节点。若 leftT 不为 null，说明在左子树中找到了值为 val 的节点，此时直接返回 leftT，也就是找到了目标节点后直接将其返回，结束整个查找过程。
  • 若在左子树中没找到目标节点（即 leftT 为 null），接着执行 TreeNodes rightT =getvalues(root.right,val); ，递归地调用本方法去查找根节点的右子树中是否存在值为 val 的节点，并将返回结果赋值给 rightT 变量。
  • 再通过 if (rightT!= null) 判断在右子树中是否找到了目标节点。若 rightT 不为 null，说明在右子树中找到了值为 val 的节点，此时直接返回 rightT，同样是找到目标节点后结束查找并返回该节点；若右子树中也没找到目标节点（即 rightT 为 null），则最后返回 null，表示整个树中都没有找到值为 val 的节点。

结语：

随着对二叉树的深入探究，我们仿佛在数据结构的神秘花园中完成了一次奇妙的漫步。从它那简洁而富有力量的定义与结构起始，我们见证了二叉树如何像一位优雅的舞者，以根节点为轴心，左旋右转，用左右子树编织出层次丰富的舞步，将数据的韵律演绎得淋漓尽致。

在算法的舞台上，二叉搜索树如灵动的精灵，快速穿梭于数据节点间，高效地完成查找、插入与删除的表演；平衡二叉树则似沉稳的大师，以精妙的平衡术确保每一个舞步都精准无误，使整个算法的舞台始终保持稳定与和谐。而遍历算法恰似指挥家手中的指挥棒，先序、中序、后序的不同挥动方式，引领着我们从不同的视角欣赏二叉树这场数据的盛宴，让我们领悟到其在各种复杂计算任务中所蕴含的无限可能。

当我们将目光投向现实应用的广袤天地，二叉树更是展现出其多才多艺的一面。它化身为网络世界里的智能导航仪，在错综复杂的网络路由中，精准规划数据传输的最优路径，让信息的洪流顺畅奔腾；在人工智能的智慧殿堂里，它是洞察先机的预言家，决策树借助其结构深度剖析数据，预测未来趋势，为决策提供明晰的方向；于文件系统的管理王国中，它又成为秩序井然的大管家，将文件分类整理得井井有条，方便我们随时取用知识的宝藏。

然而，我们对二叉树的探索仅仅是一个开端，数据结构的宇宙浩瀚无边，还有更多的奥秘等待我们去发现。希望此次二叉树之旅能为您点亮一盏明灯，在您继续深入数据结构与算法这片神秘领域时，给予您灵感与力量。愿您凭借在此处积累的智慧与经验，在未来的编程征程中，如勇敢的航海家一般，驾驭着数据结构的帆船，驶向更加辉煌的彼岸，解锁更多未知的精彩篇章。

原文地址：https://blog.csdn.net/eternal__day/article/details/144385841

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