第5章：树 - 编程导航 | 一线开发者编程经验和技术实战分享

5.1 树结构基础与特性

什么是树？相信每个人对现实生活中的树都会非常熟悉，树通常有一个根，连接着根的是树干，树干往上还会分叉成树枝，树枝进一步分叉成更细的树枝，最后在树枝上生长的是树叶。专家们对树的结构进行抽象，发现树可以模拟生活中的很多场景。

5.1.1 树的定义与现实案例

那么生活中都有哪些现实案例，能看到模拟树结构的影子呢？从熟悉的场景出发，我们可以进行大量有意义的延伸。例如，你电脑中的文件系统就是一棵最直观的树。C:或/目录就是根节点，里面的文件夹是树枝（内部节点），而一个个文件就是树叶（叶子节点）。这种层次结构让我们能高效地组织和查找信息。再比如，一个公司的组织架构图，总经理是根节点，下设各个部门作为子树，部门下面再管理各具体工作，最终到基层员工（叶子节点），公司组织架构如图5-1所示。这体现了树的另一个强大特性：清晰地表示从属关系与层级。

图5-1 公司的组织架构

我们再将各个现实案例里面的数据移除，仅仅抽象出来结构，那么就是我们要学习的树结构，树结构对应的抽象内容如图5-2所示。

图5-2 树结构抽象

5.1.2 树的优点（与数组、链表、哈希表对比）

我们之前已经学习了多种数据结构来保存数据，为什么要使用树结构来保存数据呢？树结构和数组、链表，哈希表的对比有什么优点呢？抱着这样的疑问去探索树，我们更能意识到树结构对应的应用场景以及不可替代的地方。

数组的主要优点是根据下标值访问效率会很高，但是如果我们希望根据元素来查找对应的位置呢？比较好的方式是先对数组进行排序，再进行二分查找。需要先对数组进行排序，生成有序数组之后，才能提高查找效率也是数组的限制与缺点，另外数组在插入和删除数据时，需要有大量的位移操作（插入到首位或者中间位置的时候），效率很低。

链表的插入和删除操作效率都很高，但查找效率很低，需要从头开始依次访问链表中的每个数据项，直到找到。而且即使插入和删除操作效率很高，但是如果要插入和删除中间位置的数据，还是需要重头先找到对应的数据。

而在上一章所学习的哈希表，插入、查询，删除效率都是非常高的，但是哈希表也有很多缺点，例如空间利用率不高，底层所使用的是数组，并且为了防止出现聚集效应导致的性能损失，某些单元是没有被利用的。且哈希表中的元素是无序的，不能按照固定的顺序来遍历哈希表中的元素，更不能快速的找出哈希表中的最大值或者最小值这些特殊的值。

那么树结构呢？我们不能说树结构比其他结构都要好，因为每种数据结构都有自己特定的应用场景。但是树确实也综合了上面的数据结构的优点（当然优点不足于盖过其他数据结构，例如效率一般情况下没有哈希表高），并且也弥补了上面数据结构的缺点，在综合表现能力上会更好，例如树结构的空间利用率不错，元素可以是有序的，能够快速找出最大值或者最小值等等。

而且为了模拟某些场景，我们使用树结构会更加方便。因为树结构的非线性的，可以表示一对多的关系，例如文件的目录结构。

5.1.3 树的术语解析

在描述树的各个部分的时候有很多术语，为了让介绍的内容更容易理解，需要知道一些树的术语，不过大部分术语都与真实世界的树相关，或者和家庭关系相关(如父节点和子节点)，所以它们比较容易理解。

树是由 n（n≥0）个节点构成的有限集合。当 n=0 时，它是一棵空树，这是树的边界情况；对于任意一棵非空树（n>0），其结构则具备鲜明的层次与递归特性：其中存在且仅有一个被称为根节点（Root）的特殊节点（用r表示），作为整个结构的起点与祖先；而其余节点则被逻辑地划分为 m（m>0）个互不相交的有限子集，其中每一个子集本身又是一棵树，并被称为原树的子树（SubTree）。树结构说明如图5-3所示。

图5-3 树结构说明

图5-3 树结构说明

子树的严格定义是：在一棵非空树T中，由某个节点x及其全部后代节点（包括子节点、孙节点等）构成的，满足树结构定义的、具有唯一根节点的子结构，称为树T的一棵子树。所以在图中以A往下的任意节点及其全部后代节点都可以构成一棵子树，例如{B、D、E、H}，或者以{D、H}都可以，这两个案例分别是以B和D两节点作为子树的根节点。还有一点是很有意思的，叶子节点能构成子树吗？答案是可以的，单个叶子节点本身就是一棵树，我们称之为 “单节点树”，一棵只有根节点一个节点的子树。

树之中的称呼都是相对的概念，以图5-3为例，B既是B和E的父节点，但B同时也是A的子节点，他们之间的关系就像家谱中的关系网一样，例如表妹不是固定具体的一个人，而是相对于“我”而言的一种关系定位。在中国过年去亲戚家拜访总是需要称呼的，例如舅舅好，舅妈好等等，需要有一个称呼来打招呼，而在树结构中也需要有对应的名词来称呼彼此之间的关系，常见树的术语如表5-1所示。

表5-1 树的术语

类别	术语	定义与描述	备注与拓展
节点属性	节点的度 (Degree)	节点的子树个数（即直接子节点的数量）。	度是节点分支能力的直接体现。在二叉树中，节点的度最大为2。
	叶子节点 (Leaf)	度为0的节点，也称为叶子节点。	叶子节点是树的“终点”，没有后继节点，是数据存储的常见位置。
节点关系	父节点 (Parent)	拥有子树的节点，是其子树根节点的父节点。	关系是相对的。一个节点是其子节点的父节点，同时也是其父节点的子节点。
	子节点 (Child)	一个节点是另一个节点的子节点，则后者是前者的父节点。	也称为孩子节点。父子关系定义了树的层次和走向。
	兄弟节点 (Sibling)	具有相同父节点的各个节点，彼此互为兄弟节点。	兄弟节点处于树的同一层级，是并行关系。
路径与层级	路径 (Path)	从节点n₁到nₖ的一个节点序列，其中nᵢ是nᵢ₊₁的父节点。	路径描述了树中从一个节点到达另一个节点的唯一通路。
	路径长度 (Path Length)	路径上所包含的边的数量。	从根到某节点的路径长度，即为该节点的深度。
	节点的层次 (Level)	节点在树中的层级。规定根节点在第1层，其余节点层数为其父节点层数加1。	层次也称为“深度”(Depth)，但注意与下面“树的深度”定义可能因教材而异（有的从0开始，有的从1开始）。
树整体属性	树的度 (Degree of Tree)	树中所有节点的度的最大值。	它决定了树的最大分支能力。度为2的树即为二叉树。
	节点的深度 (Depth)	从根节点到该节点的唯一路径的长度（边的个数）。根的深度为0。	深度描述的是节点到根的距离，是从顶向下的度量。
	节点的高度 (Height)	从该节点到其最远叶子节点的最长路径长度。所有叶子节点的高度为0。	高度描述的是节点到最远叶子的距离，是从底向上的度量。树的高度即为根节点的高度。
	树的深度/高度 (Depth/Height of Tree)	树中所有节点的深度的最大值，也等于根节点的高度。	这描述了树的整体规模或最大层级。注意：树的深度 = 树的高度。

除了常见的称呼之外，还有祖先节点、后代节点这种不常用但见名知意的节点关系称呼，例如祖先节点是从某个节点到根节点的路径上经过的所有节点，而后代节点是某个节点下面的所有节点。

5.2 树的表示方法与二叉树

5.2.1 树的常见表示方法

树有3种常见的表示方法，普通表示法如图5-4所示，儿子-兄弟表示法如图5-5所示，儿子-兄弟表示法旋转如图5-6所示。

最符合直觉的是普通表示法（或称“子节点列表法”）。这种方法直接模拟了我们绘制树形图的方式：每个节点存储自身的数据，并维护一个指向其所有直接子节点的列表。例如，对于一个拥有三个子节点的根节点，其结构就包含一个包含三个元素的子节点列表。这种方法虽然直观，但在处理动态变化或需要深度遍历的树时，由于每个节点的子节点数量不定，可能导致存储效率和处理性能上的挑战。普通表示法如图5-4所示。

图5-4 树-普通表示方式

为了克服普通表示法的局限性，计算机科学家引入了极为巧妙的儿子-兄弟表示法（又称“左孩子右兄弟法”）。这种方法的核心洞察在于：任何复杂的树结构都可以被统一地转化为一棵二叉树。它不再记录一个节点的所有子节点，而是仅为每个节点设置两个指针：一个指向其第一个儿子，另一个指向其紧邻的下一个兄弟。通过这种方式，一个拥有多个分支的树被巧妙地“压扁”成了一个多层的链表结构。比如，一个节点及其三个子节点，在内存中就被表示为：父节点指向第一个儿子，第一个儿子指向第二个儿子，第二个儿子再指向第三个儿子。这种表示法统一了存储单元，使得每个节点无论有多少子代，都只占用固定的空间，为实现高效的树遍历算法奠定了基础。儿子-兄弟表示法如图5-5所示。

图5-5 树-儿子_兄弟表示法

当我们使用儿子-兄弟表示法后，树在逻辑上已经等价于一棵二叉树。为了更直观地理解这种等价关系，我们可以通过“旋转”来进行可视化。具体来说，就是将这棵隐含的二叉树进行约45°的顺时针旋转——此时，原树中“第一个儿子”的指针变成了二叉树的“左孩子”指针，而“下一个兄弟”的指针则变成了二叉树的“右孩子”指针。旋转视图之后，以K作为起始点，展现了树结构本质上都可以映射为二叉树，这也解释了为什么二叉树在理论和实践中都占据着至关重要的地位（非常重要，本章核心讲解的就是二叉树），因为它足以作为所有树形结构的通用表示和操作基础。儿子-兄弟表示法旋转如图5-6所示。

图5-6 树-儿子_兄弟表示法旋转

我们研究这些不同的树结构表示方法的目的在于：计算机的存储模型与我们的逻辑思维模型之间存在差异。我们脑中想象的树是立体的、多叉的，但计算机的内存是线性的、顺序的。这些表示法的核心目的，就是在这两者之间搭建一座桥梁：将直观的、多叉的层次结构，转化为计算机可以高效存储和处理的线性或二元结构。

不同的表示法在代码中的写法都不同，3种表示法对应的代码写法如下：

（1）普通表示法：每个节点包含一个 children 数组，直接存储所有子节点。

（2）儿子-兄弟表示法：每个节点包含 firstChild 和 nextSibling 指针，将多叉树转化为链表结构。

（3）二叉树表示法：儿子-兄弟表示法旋转后的结果，使用标准的二叉树 left 和 right 指针。

▼
ts
复制代码
// 1. 普通表示法 (子节点列表法)
interface NormalTreeNode extends TreeNodeBase {
  children: NormalTreeNode[]; // 存储所有直接子节点的数组
}

// 2. 儿子-兄弟表示法
interface ChildSiblingTreeNode extends TreeNodeBase {
  firstChild: ChildSiblingTreeNode | null; // 指向第一个儿子
  nextSibling: ChildSiblingTreeNode | null; // 指向下一个兄弟
}

// 3. 二叉树表示法 (儿子-兄弟表示法旋转后的结果)
interface BinaryTreeNode extends TreeNodeBase {
  left: BinaryTreeNode | null;  // 相当于原树的第一个儿子 (旋转后变为左孩子)
  right: BinaryTreeNode | null; // 相当于原树的下一个兄弟 (旋转后变为右孩子)
}

5.2.2 二叉树的概念与特性

通过树的常见表示方法之后，我们意识到二叉树的重要性，不仅仅是因为简单，也因为几乎上所有的树都可以表示成二叉树的形式。而如果树中每个节点最多只能有两个子节点，这样的树就称为"二叉树"。

从严格定义的角度来看，二叉树是一个递归定义的有限节点集合，它要么为空（空树），要么由一个根节点和两个互不相交的二叉树组成，这两个子树被严格区分为左子树和右子树，且每个节点最多只能拥有这两个直接后代，即使只有一个子节点也必须明确其左右位置。概述下来，主要为以下2点：

（1）二叉树可以为空，也就是没有节点。

（2）若不为空，则它是由根节点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。

二叉树虽然结构多样，但其基本形态严格遵循其定义规律，可以归纳为五种基本形式。第一种是空树，这是所有二叉树的起点和递归定义的基准情形。在此基础上，第二种形态是仅包含根节点的树，其左右子树均为空。当树开始生长时，便衍生出另外三种形态：第三种是根节点拥有左子树而右子树为空；第四种是根节点拥有右子树而左子树为空；第五种则是根节点同时拥有非空的左子树和右子树。这五种形态完整地描述了二叉树的所有可能结构——从最简单的空树和单节点树，到具有明确左右子树区分的不完全二叉树，再到最完整的左右子树兼备的形态。理解这五种基本形态对于掌握二叉树的遍历、构建和算法分析至关重要，因为任何复杂的二叉树都可以视为这些基本形态通过不同方式的组合与嵌套。二叉树的5种形态如图5-7所示。

图5-7 二叉树的5种形态

二叉树还有3个比较重要的特性，在笔试题中较为常见：

（1）一颗二叉树第 i 层的最大节点数为：2^(i-1)，i >= 1。

（2）深度为k的二叉树有最大节点总数为： 2^k - 1，k >= 1。

（3）对任何非空二叉树T，若n₀表示叶子节点的个数、n₂是度为2的非叶子节点个数，那么两者满足关系n₀ = n₂ + 1 。

如图5-8所示的二叉树，根节点A是第1层，最大节点数即2的0次方为1；节点B是第2层，最大节点数即2的1次方为2，往后规律依次，每一层的节点数都符合最大节点数被称为满二叉树。对于这棵深度为4的二叉树，最大节点数为2的4次方-1，即最大节点数为15。

第3个重要特性又是什么意思？如图5-8所示的二叉树，叶子节点（度为0的节点）是D、J、K和H，因此叶子节点个数n₀ = 4；度为2的节点（拥有两个子节点的非叶子节点）是A、B和E，因此度为2的节点个数n₂ = 3，这刚好符合了n₀ = n₂ + 1的规律（4=3+1）。对于任何非空二叉树，叶子节点个数总是等于度为2的节点个数加1。这个关系源于二叉树的边数计算和节点度数之和的平衡，无论树的具体形态如何变化，该等式恒成立。

图5-8 二叉树的三个重要特性

这个等式的推导过程非常精妙，其核心逻辑建立在连接节点与节点的“边”之上。我们可以从两个不同的角度来计算二叉树的总边数，并使其相等，从而建立关系。首先，在任意一棵非空二叉树中，除了根节点外，每个节点都有且仅有一条“入边”与其父节点相连，因此，总边数 E 等于节点总数 n 减去 1，即 E = n - 1。

另一方面，我们从节点的“出度”或“贡献”的角度来计算总边数。叶子节点（度为0）贡献0条边，度为1的节点贡献1条边，度为2的节点贡献2条边。如果设 n0, n1, n2 分别代表三类节点的数量，那么总边数 E 也等于 E = 0 * n0 + 1 * n1 + 2 * n2。

现在，我们让两个关于总边数 E 的表达式相等：n - 1 = n1 + 2n2。同时，节点总数 n 又可以表示为 n = n0 + n1 + n2。将第二个公式代入第一个公式，得到 (n0 + n1 + n2) - 1 = n1 + 2n2。接下来，我们消去等式两边的 n1，并进行移项：n0 + n2 - 1 = 2n2，最终得到 n0 = n2 + 1。这个推导过程清晰地表明，无论树的形态如何变化，无论度为1的节点 n1 有多少，叶子节点与度为2的节点之间这种此消彼长、恒久不变的数量关系都必然成立。

5.2.3 完美二叉树与完全二叉树

完美二叉树(Perfect Binary Tree) ，也称为满二叉树(Full Binary Tree），在二叉树中，除了最下一层的叶子节点外，每层节点都有2个子节点，就构成了满二叉树。完美二叉树如图5-9所示。

图5-9 完美二叉树

在实际情况中，完美二叉树在各种案例中是少有出现的。但除了完美二叉树之外，有一个常见的二叉树被称为完全二叉树，完美二叉树和完全二叉树的区别是什么？完全二叉树（Complete Binary Tree）是除二叉树最后一层外，其他各层的节点数都达到最大个数，且最后一层从左向右的叶子节点连续存在，只缺右侧若干节点的二叉树。因此我们称完美二叉树是特殊的完全二叉树。

如图5-10所示的二叉树不是完全二叉树，因为D节点还没有右节点，但是E节点就有了左右节点，没有满足最后一层的叶子节点必须从左到右的连续存在。像后续第9章所学的堆，本质上就是一棵完全二叉树，可以直接放入数组中，不用节点封装。

图5-10 不是完全二叉树

5.3 树的存储方式

二叉树常见的存储方式是数组和链表，是因为它们分别对应二叉树在不同形态下的优势。当二叉树是完全或接近完全时，节点的位置具有明确的下标关系，用数组存储可以通过公式快速计算父子节点的位置，不需要指针，访问效率高，实现也简单。

当二叉树结构不完整、分布不规则时，更适合使用链表来存储。链表节点直接保存左右孩子指针，能够自然表现树的结构，不会浪费空间，也便于插入、删除等结构调整。因此，数组适合规则、紧凑的树（如堆），链表适合一般、不规则或动态变化的二叉树结构。

5.3.1 数组存储方式

在使用数组存储二叉树时，如果是完全二叉树，可以直接按照“从上到下、从左到右”的顺序依次放入数组下标中。这种方式简单高效，因为完全二叉树不存在中间节点缺失的情况，节点之间的位置关系可以直接用数组下标计算得到（例如：下标 i 的左孩子是 2i，右孩子是 2i+1）。完全二叉树的数组存储方案如图5-11所示。

图5-11 完全二叉树（数组存储）

但如果是一棵非完全二叉树，由于节点分布可能不连续，若直接使用相同的方式存入数组，会出现很多空洞位置。例如某层缺少左子节点，就必须跳过数组中的那个位置，导致浪费大量存储空间。因此，通常需要先将非完全二叉树补齐为完全二叉树后再存储，但这种补齐过程会增加许多实际不存在的“空节点”，从而造成空间浪费。非完全二叉树的数组存储方案如图5-12所示。

图5-12 非完全二叉树（数组存储）

5.3.2 链表存储方式

二叉树最常见的存储方式是使用链式结构，即将每个节点封装成一个 Node 对象。Node 中通常包含三部分内容：节点存储的数据、指向左子节点的引用、以及指向右子节点的引用。通过这种指针（引用）形式，一个节点就能直接定位到它的左右孩子，从而自然地形成树的层级关系。链式存储适用于任意形态的二叉树，不会因为节点缺失而造成空间浪费，也方便执行插入、删除等结构调整操作。二叉树的链表存储方案如图5-13所示。

图5-13 二叉树（链表存储）

5.4 二叉搜索树基础

二叉搜索树是在二叉树基础上的一种“有序二叉树”。它要求任意节点都必须满足：左子树所有节点的值都小于该节点值，右子树所有节点的值都大于该节点值，并且左右子树本身也要符合这一规则。因此，BST 不仅有二叉树的结构特性，还有明确的排序特性，使其能支持高效的查找、插入和删除。

5.4.1 二叉搜索树的定义与特性

二叉搜索树（BST，Binary Search Tree），也称二叉排序树或二叉查找树。二叉搜索树本质上依旧是一棵二叉树，可以为空（允许没有任何节点），即整棵树不存在根节点，本质上就是一棵空树。允许空树（没有任何节点）主要有以下2点考虑：

（1）BST的性质要求左右子树是BST，如果不允许“空树也算 BST”，就无法成立递归定义。因为当某节点不存在左或右子树时，需要将“该子树为空”视为一种合法BST。

（2）在实际程序中，很多操作（如插入、查找、树构建）都会遇到初始树还没有节点或者某个叶子节点的左右指针为null，此时如果将这些情况视为“合法 BST 的空状态”，算法才能正常书写。

那么，如果二叉搜索树不为空，则需要满足以下3点性质：

（1）非空左子树的所有键值小于其根节点的键值。

（2）非空右子树的所有键值大于其根节点的键值。

（3）左、右子树本身也都是二叉搜索树。

了解了二叉搜索树的定义之后，我们发现二叉搜索树不为空的性质非常有顺序规律，非常适合检索，也许这就是它被称为"有序二叉树"的原因。那么如图5-14所示的哪些是二叉搜索树，哪些不是？

第一棵不是二叉搜索树，因为10的右子树的键值5小于10这一根节点的键值。第二第三棵符合二叉搜索树条件。

图5-14 二叉搜索树区分

其实二叉搜索树是非常容易区分的，沿着非空左子树一路到底，数字一定越来越小，沿着非空右子树一路到底，数字一定越来越大，从任何一个节点去看都是如此。甚至我们可以将二叉搜索树逆时针旋转45°，数值从左往右变大，从上往下变小。

因此我们得出二叉搜索树的特点就是相对较小的值总是保存在左节点上，相对较大的值总是保存在右节点上，那么利用这个特点，我们可以做什么事情呢？

例如在图 5-14 的第三棵二叉搜索树中查找键值 8，搜索过程会从根节点 6 开始。由于 8 大于 6，所以进入其右子树，找到节点 9；接着 8 小于 9，于是继续进入 9 的左子树，到达节点 7；再判断 8 大于 7，进入其右子树，最终找到目标节点 8。这个查找过程每一步都根据大小关系选择左或右子树，路径不断折半缩小查找范围，因此二叉搜索树与二分查找的思想十分相似，查找效率非常高。

如图5-15所示依旧是一棵二叉搜索树，继续试着查找一下值为10的节点，方式与步骤与在图5-14的第三棵二叉搜索树中查找键值 8思路一致。

图5-15 二叉搜索树（寻找10）

查找值为10的节点的过程步骤如图5-16所示，再次印证二分查找的思想。总结的规律如下2点：

（1）查找所需的最大次数等于二叉搜索树的深度。

（2）插入节点时，也利用类似的方法，一层层比较大小，找到新节点合适的位置。

图5-15 二叉搜索树（寻找10的过程）

5.4.2 二叉搜索树的封装

如果我们要封装二叉搜索树（本章的代码部分以二叉搜索树作为示例），我们像封装其他数据结构一样，先来封装一个BSTree类（Binary Search Tree的缩写）。那么二叉搜索树需要包含哪些东西呢？最少的情况下可以连根节点都没有（空树）；而处于非空情况下，有一个根节点也就足够了，后续的左右子树都由根节点迭代而来。这很像是现实中的树一开始也是颗种子，我们有种子就足够了。

在封装BSTree类之前，我们还需要封装节点的类，一个存储数据的节点，和我们在实现链表时是类似的思路。

▼
ts
复制代码
// types/Node文件
class Node<T> {
  value: T
  constructor(value: T) {
    this.value = value
  }
}

export default Node

在基础的Node类上继承实现属于树的TreeNode类（用于构建二叉树结构的节点），即节点所应具备的左子节点和右子节点，且允许为空，在5.4.1小节开头说明了允许空树（没有任何节点）的2点考虑。

基于TreeNode类实现我们的BSTree类（二叉搜索树），也是允许为空。

▼
ts
复制代码
import Node from "../types/Node"

class TreeNode<T> extends Node<T> {
  left: TreeNode<T> | null = null
  right: TreeNode<T> | null = null
} 

class BSTree<T> {
  private root: TreeNode<T> | null = null
}

export {}

5.5 二叉搜索树操作 - 插入与遍历

那么二叉搜索树有哪些常见的操作呢？这决定了我们需要封装哪些二叉搜索树的方法。主要分为插入操作、查找操作、遍历操作以及删除操作。二叉搜索树常见操作如表5-2所示。

表5-2 二叉搜索树常见操作

分类	操作	功能说明
插入操作	insert(value)	向树中插入一个新的数据。
查找操作	search(value)	在树中查找一个数据，如果节点存在返回 true，否则返回 false。
	min	返回树中最小的值/数据。
	max	返回树中最大的值/数据。
遍历操作	inOrderTraverse	通过中序遍历方式遍历所有节点。
	preOrderTraverse	通过先序遍历方式遍历所有节点。
	postOrderTraverse	通过后序遍历方式遍历所有节点。
	levelOrderTraverse	通过层序遍历方式遍历所有节点。
删除操作	remove(value)	从树中移除某个数据（操作稍微复杂）。

5.5.1 插入操作实现

二叉搜索树的插入操作如何实现？二叉搜索树结构如图5-16所示。从root根节点开始插入数据，而后续插入数据就需要判断插入数据与当前节点数据的大小，从而决定是往左子树插入还是往右子树插入，插入之前还需要再次判断左右子树是否有值，无值则创建节点并插入数据，有值则需要重复上述大小判断，然后继续前往下一层左右子树。

图5-16 二叉搜索树结构

首先插入数据insert()方法接收一个value参数，该方法会将传入的数据插入到二叉搜索树中，但实际一开始并不是插入，因为一开始二叉搜索树是空树，没有根节点更没有其他节点可供我们插入，因此一开始需要先创建根节点然后在插入value。因此插入数据分两种情况：

（1）第一次插入，直接修改根节点。

（2）其他插入，需要通过相关比较来决定插入位置。

根据以上插入数据思路分析，我们需要分两部分来完成插入功能：

（1）insert()方法：初始化二叉树并决定插入的第一个数据。

（2）insertNode()方法：第一次插入之外的其余次插入数据到二叉搜索树的情况。

insert()方法思路为以下3步：

（1）创建新节点（第一次创建为根节点）并传入数据。

（2）判断是否有根节点，无根节点则新节点作为根节点，并记录根节点属性已经存在。

（3）判断是否有根节点，有根节点则调用另一方法，传入需要插入的数据，由该方法决定插入的正确位置并插入。

▼
ts
复制代码
/** 插入数据的操作 */
insert(value: T) {
  // 1.根据传入value创建Node(TreeNode)节点
  const newNode = new TreeNode(value)

  // 2.判断当前是否已经有了根节点
  if (!this.root) { // 当前树为空
    this.root = newNode
  } else {
    // 树中已经有其他值。 最好调用insertNode()方法，防止逻辑耦合
  }
}

insert()方法主要创建了第一个根节点，并插入数据。但由于第一次插入之外的其他插入需要实现对二叉搜索树的比较逻辑，为了防止逻辑耦合（可读性更好）以及后续有可能复用比较逻辑，因此寻找插入位置最好另外实现成insertNode()方法，然后在insert()方法中的其他插入情境使用。

insertNode()方法需要是一个内部方法，它是其余方法的组成部分，是建立在一定条件上去使用的，而非独立功能的个体（残缺），所以不应该开放给用户使用，例如往空树调用insertNode()方法就会报错。

insertNode()方法思路为以下4步：

（1）对传入数据与当前节点数据的大小进行比对。

（2）传入数据小于当前节点数据：判断当前节点的左子树是否有值，无值则将传入数据（newNode）插入左子树。

（3）传入数据大于当前节点数据：判断当前节点的右子树是否有值，无值则将传入数据（newNode）插入右子树。

（4）如果左右子树中相应方向已有节点，则说明当前位置不能插入，需要将该子节点作为新的“当前节点”，继续递归调用 insertNode()方法。随着递归深入，判断会沿着树向下推进，直到找到一个为空的位置并完成插入。

根据insertNode()方法思路，我们需要两个参数：node（当前节点），newNode（插入的节点）。插入的节点一直不变，但当前节点随着一层层寻找二叉搜索树的插入位置要不断变换，最终找到位置插入newNode。

▼
ts
复制代码
private insertNode(node: TreeNode<T>, newNode: TreeNode<T>) {
  if (newNode.value < node.value) { // 去左边继续查找空白位置
    if (node.left === null) { // node节点的左边已经是空白
      node.left = newNode
    } else {
      this.insertNode(node.left, newNode)
    }
  } else { // 去右边继续查找空白位置
    if (node.right === null) {
      node.right = newNode
    } else {
      this.insertNode(node.right, newNode)
    }
  }
}

为了能够打印出二叉搜索树的可视化效果（方便测试反馈），我们npm安装第三方库hy-algokit，使用其中的btPrint()方法，该方法需要一个节点，会以该节点为打印效果的根节点将后续内容以可视化形式打印出来。由于root是私立属性，只能在BSTree类的内部使用，所以要么我们去除root属性的private前缀，要么在BSTree类的内部再封装一个方法，我们选择后者，不会破坏原有立意。

▼
ts
复制代码
import { btPrint } from 'hy-algokit'

print() {
  btPrint(this.root)
}

完整代码如下（包含测试用例）：

▼
ts
复制代码
import Node from "../types/Node"

import { btPrint } from 'hy-algokit'

class TreeNode<T> extends Node<T> {
  left: TreeNode<T> | null = null
  right: TreeNode<T> | null = null
} 

class BSTree<T> {
  private root: TreeNode<T> | null = null

  print() {
    btPrint(this.root)
  }

  /** 插入数据的操作 */
  insert(value: T) {
    // 1.根据传入value创建Node(TreeNode)节点
    const newNode = new TreeNode(value)

    // 2.判断当前是否已经有了根节点
    if (!this.root) { // 当前树为空
      this.root = newNode
    } else { // 树中已经有其他值
      this.insertNode(this.root, newNode)
    }
  }

  private insertNode(node: TreeNode<T>, newNode: TreeNode<T>) {
    if (newNode.value < node.value) { // 去左边继续查找空白位置
      if (node.left === null) { // node节点的左边已经是空白
        node.left = newNode
      } else {
        this.insertNode(node.left, newNode)
      }
    } else { // 去右边继续查找空白位置
      if (node.right === null) {
        node.right = newNode
      } else {
        this.insertNode(node.right, newNode)
      }
    }
  }
}

const bst = new BSTree<number>()
bst.insert(11)
bst.insert(7)
bst.insert(15)
bst.insert(5)
bst.insert(3)
bst.insert(9)
bst.insert(8)
bst.insert(10)
bst.insert(13)
bst.insert(12)
bst.insert(14)
bst.insert(20)
bst.insert(18)
bst.insert(25)
bst.insert(6)

bst.print() // 打印二叉搜索树

export {}

二叉搜索树插入效果打印如图5-17所示，我们后续的操作（例如先序遍历）都基于这次二叉搜索树的数据去实现。

图5-17 二叉搜索树插入效果打印

通过第三方库 hy-algokit，我们可以直接将二叉搜索树结构打印出来，但这只是利用现成工具。如果我们自己来实现二叉树的遍历，就需要思考——遍历一棵树到底意味着什么？

遍历树的含义很简单：访问树中的每一个节点。但是树与线性结构不同。在线性结构（如数组、链表）里，节点天然是一条线，我们只需要从头到尾顺序访问即可。而树的结构则呈分叉形态：

从哪个方向开始？
是先访问父节点还是子节点？
遇到分支从左子树开始还是右子树开始？

正因为树结构具有分支、层级、方向等特点，因此在漫长的算法演化过程中，人们形成了多种遍历方式以适应不同需求。树的访问顺序由节点间的层级关系决定，而树中每个节点都最多有左右两个分支。于是根据 “父节点的访问时机”，发展出了三种经典的深度优先遍历（DFS）方式：

（1）先序遍历（Pre-order）：先访问节点，再访问子树。

（2）中序遍历（In-order）：左子树 → 节点 → 右子树，是二叉搜索树中最常用的遍历（能得到有序结果）。

（3）后序遍历（Post-order）：先访问子树，再访问节点。

除此之外，还有一种以“层级”为主导的遍历方式：

（4）层序遍历（Level-order）：按从上到下、从左到右的顺序访问每一层节点。

不同遍历方式的出现并不是随意命名，而是随着算法需求不断演化，4种遍历方式能够运用在所有二叉树上（包括了二叉搜索树），二叉树4种遍历方式对应的需求如表5-3所示。

表5-3 二叉树四种遍历方式对应的需求

需求	最适合的遍历
按功能顺序构建或拷贝树	先序遍历
获取二叉搜索树的有序结果	中序遍历
释放内存、删除节点（先删叶子）	后序遍历
层次结构输出、打印树结构	层序遍历

像第三方库 hy-algokit的btPrint()方法就是基于层序遍历实现的，只不过额外做了4点操作：

（1）使用二维数组记录每一层的节点结果。

（2）计算打印宽度。

（3）为每层绘制节点之间的连接线（如 ┌ ┐ └ ┘ ┴ ─ 等）。

（4）最终把树形结构按层输出出来。

但想要可视化的画出一棵好看的树并不简单，层序遍历是实现的原理，但仅仅做到层序遍历是画不出树的，具体实现可去看btPrint()方法的源码。

5.5.2 先序遍历（递归与非递归）

如果我们想实现一个先序遍历，分3步骤：

（1）访问根节点。

（2）先序遍历其左子树。

（3）先序遍历其右子树。

二叉树的先序遍历顺序如图5-18所示。在这棵树中，我们先访问最顶端的节点A，然后进入它的左子树，从B开始继续重复同样的规则。访问完B后，再进入它的左孩子D。左子树全部走完之后，才返回去访问B的右子树，例如F以及F的左孩子E。当左子树全部遍历完后，再进入A的右子树，从C开始继续按照“根 → 左 → 右”的方式依次访问 G、H、I。最终形成的先序遍历结果就是：A B D F E C G H I。

图5-18 二叉树的先序遍历顺序

根据图中 5–18 的访问顺序，我们可以把先序遍历的执行过程细化为这样一种理解：

先序遍历的核心规则是 “根 → 左 → 右”。因此，我们首先访问根节点，然后进入左子树。接下来，把当前左子树的根节点继续当作新的根，再重复同样的过程——仍然优先进入它的左子树。这个过程会一路向左深入，直到某个节点已经没有左子树可走为止。此时才开始回溯，转而访问右子树；但一旦遇到新的左子树，又会优先进入新的左子树继续遍历。

也就是说，在先序遍历中：只要还有未访问的左子树，总是优先访问左子树，直到彻底遍历干净，再返回向右方向展开。

因此再回头看先序遍历步骤中的两句话就很容易理解：

（1）先序遍历其左子树 —— 进入左子树后依然优先它的左子树。（2）先序遍历其右子树 —— 进入右子树后依旧保持“能左就优先左”的规律。

接着来看图5-19所示的二叉搜索树的先序遍历顺序。依照先序遍历的规律，从根节点11开始访问，然后进入根节点11的左子树后依然优先它的左子树，即7、6、3。访问到叶子节点3之后（无左子树了）开始回溯到节点5，此时节点5已无未访问过的左子树，因此访问节点5的右子树6（叶子节点）。接着回溯到节点5再回溯到节点7，由于节点7的左子树部分已全部访问过，所以进入节点7的右子树中，从节点9开始访问，但进入右子树后依旧保持“能左就优先左”的规律，所以节点9访问结束后，需要检查节点9是否有未访问过的左子树（节点8），有则优先访问，后续访问遍历规律依照如上。

最终如图5-19所示的二叉搜索树的先序遍历结果为：11、7、5、3、6、9、8、10、15、13、12、14、20、18，25。

图5-19 二叉搜索树的先序遍历顺序

在代码中，如何实现二叉搜索树的先序遍历-preOrderTraverse()方法？首先我们传入二叉树的根节点，preOrderTraverse()方法第一时间就能拿到根节点并打印输出，因此可以先访问当前节点，然后递归访问左子树，左子树遍历完成后再递归访问右子树，整个顺序由递归自然维护，无需额外强调右子树内部的访问顺序。由于递归的“执行顺序”是由系统调用栈来维持的，每一次递归进入新节点，当前执行位置都会被压入栈中，所以执行“结束并返回”的顺序是相反的，从最深的叶子节点开始一层层往回走。因此我们需要在递归之前先把当前节点打印出来，如果把打印操作放在递归操作之后，打印结果的顺序会发生结构性的改变。也得益于递归操作会从最深的叶子节点一层层往回走，因此左子树结束往回的同时刚好可以调用右子树。

当然，由于先序遍历访问二叉搜索树是从特定根节点开始的，而外界是无法直接拿到根节点也不应该能直接拿到的，因此我们额外封装preOrderTraverseNode()私有方法（自由决定遍历节点这一需求不符合实际，需要满足先能自由拿到所需节点的前置条件，因此不交由使用者决定，将该方法设置为私有），将上述先序遍历逻辑放入该私有方法中，然后由preOrderTraverse()方法调用preOrderTraverseNode()私有方法并传入根节点。后续的中序遍历以及后续遍历也是依照此逻辑实现，将公有方法作为调用入口，私有方法作为实现核心。

▼
ts
复制代码
// 先序遍历
preOrderTraverse() {
  this.preOrderTraverseNode(this.root)
}
private preOrderTraverseNode(node: TreeNode<T> | null) {
  if (node) {
    console.log(node.value)
    this.preOrderTraverseNode(node.left)
    this.preOrderTraverseNode(node.right)
  }
}

5.5.3 中序遍历（递归与非递归）

如果我们想实现一个中序遍历，分3步骤：

（1）中序遍历其左子树。

（2）访问根节点。

（3）中序遍历其右子树。

二叉树的中序遍历遵循“左子树 → 根节点 → 右子树”的顺序。在图 5-20 所示的这棵树中，我们从根节点 A 开始，但并不首先访问 A，而是按照规则先进入它的左子树，来到节点 B。在 B 的左子树中继续深入，进入节点 D，并由于它没有左孩子，所以先访问 D，然后返回到 B，此时左子树已经遍历完，访问根节点 B。接着再进入 B 的右子树，访问节点 F，并继续按照相同规则访问 F 的左孩子 E。这样左子树访问彻底完成后，才返回根节点 A，访问 A，然后进入 A 的右子树，从 C 开始继续按照“左 → 根 → 右”的方式依次访问其子节点 G、H、I。最终形成的中序遍历结果就是：D B E F A G H C I。

图5-20 二叉树的中序遍历顺序

根据图中 5–20 的访问顺序，我们可以把中序遍历的执行过程细化为这样一种理解：

中序遍历的核心规则是 “左 → 根 → 右”。因此，我们首先进入当前节点的左子树，沿着左孩子不断向下深入，直到遇到没有左子树的节点为止。此时，访问该节点本身，然后再转向它的右子树。对于右子树，也同样遵循“能左就左”的规律，先访问右子树的左子树，再访问右子树的根，最后访问右子树的右子树。

也就是说，在中序遍历中：只要有未访问的左子树，总是先访问左子树；访问完左子树后，再访问当前节点；最后才访问右子树，并且在进入右子树后依然保持“先左后根再右”的规律。

因此再回头看中序遍历步骤中的两句话就很容易理解：

（1）中序遍历其左子树 —— 进入左子树后依然优先它的左子树，直到无法再深入。（2）访问根节点 —— 左子树访问完后，回到当前节点访问它本身。（3）中序遍历其右子树 —— 进入右子树后依旧保持“能左就优先左”的规律，先左再根再右。

接着来看图5-19所示的二叉搜索树的中序遍历顺序。依照中序遍历的规律，从根节点11开始，先进入根节点11的左子树，对节点7重复“先左再根再右”的规则。节点7的左子树依次访问节点5、3、6，最终顺序为 3、5、6。访问完左子树后回到节点7，再访问节点7本身，然后进入节点7的右子树，依次访问节点9及其左子树节点8、右子树节点10，最终左子树部分的访问顺序为 3、5、6、7、8、9、10。回到根节点11访问它本身后，再进入右子树，按照同样规律访问节点15及其左右子树（13、12、14）、节点20及其左子树18、右子树25。

最终如图5-21所示的二叉搜索树的中序遍历结果为：3、5、6、7、8、9、10、11、12、13、14、15、18、20、25。

图5-21 二叉搜索树的中序遍历顺序

需要记住递归的核心逻辑，在5.5.2小节的先序遍历中，我们说明递归执行“结束并返回”的顺序是相反的，从最深的叶子节点开始一层层往回走。因此如果console.log(node.value)放在this.inOrderTraverseNode(node.left)之后，那么左子树递归会先到二叉树中的左子树最深处再开始往回执行，也就是返回到每一层时才执行打印节点值，打印操作执行于每一层返回的位置，所以打印顺序就变成了：最左 → 父节点 → 右节点。从而形成中序遍历。

▼
ts
复制代码
// 中序遍历
inOrderTraverse() {
  this.inOrderTraverseNode(this.root)
}
private inOrderTraverseNode(node: TreeNode<T> | null) {
  if (node) {
    this.inOrderTraverseNode(node.left)
    console.log(node.value)
    this.inOrderTraverseNode(node.right)
  }
}

5.5.4 后序遍历（递归与非递归）

如果我们想实现一个后序遍历，分3步骤：

（1）后序遍历其左子树。

（2）后序遍历其右子树。

（3）访问根节点。

二叉树的后序遍历遵循“左子树 → 右子树 → 根节点”的顺序。在图 5-22 所示的这棵树中，我们从根节点 A 开始，但并不首先访问 A，而是按照规则先进入它的左子树，来到节点 B。在 B 的左子树中继续深入，进入节点 D，由于它没有左孩子和右孩子，先完成对 D 的访问（D 自身就是叶子节点）。然后回到 B，进入 B 的右子树，访问节点 F，再进入 F 的左孩子 E 先访问 E，左、右子树都遍历完后，再访问 F。此时 B 的左右子树都已完成，最后访问根节点 B。

左子树遍历完毕后，回到根节点 A，再进入右子树，从 C 开始，先进入 C 的左子树 G、访问G的右子树 H，而后返回访问G，接着是C的右子树I，左右子树都遍历完后，才访问根节点 C。

最终按照后序遍历规律，整个二叉树的访问顺序为：D E F B H G I C A。

图5-22 二叉树的后序遍历顺序

后序遍历的核心规则是 “左 → 右 → 根”。因此，我们首先进入当前节点的左子树，沿着左孩子不断向下深入，直到遇到没有左子树的节点为止。此时，开始检查右子树，如果存在右子树，则先遍历右子树，右子树也遵循相同规律：先左后右再根。左、右子树都遍历完成后，最后才访问当前节点本身。

也就是说，在后序遍历中：只要有未访问的左子树，总是先访问左子树；左子树访问完后，再访问右子树；当左右子树都访问完后，才访问当前节点。每进入一个新子树，都严格遵循“先左、再右、最后根”的规律。

因此再回头看后序遍历步骤中的三句话就很容易理解：

（1）后序遍历其左子树 —— 进入左子树后依然优先它的左子树，直到无法再深入。（2）后序遍历其右子树 —— 左子树完成后进入右子树，仍然先左再右再根。（3）访问根节点 —— 左右子树都访问完后，才访问当前节点本身。

接着来看图5-19所示的二叉搜索树的后序遍历顺序。依照后序遍历的规律，从根节点11开始，先进入根节点11的左子树，对节点7重复“先左、再右、最后根”的规则。节点7的左子树依次访问节点5及其左孩子3、右孩子6，访问顺序为 3、6、5；接着访问节点7的右子树，先访问节点9及其左子树8、右子树10，访问顺序为 8、10、9；左右子树遍历完毕后，访问节点7本身，左子树整体访问顺序为 3、6、5、8、10、9、7。

回到根节点11，再进入右子树，按照同样规律访问节点15及其左右子树（12、14、13）、节点20及其左子树18、右子树25，右子树整体访问顺序为 12、14、13、18、25、20、15。左右子树访问完毕后，最后访问根节点11本身。

最终如图5-21所示的二叉搜索树的后序遍历结果为：3、6、5、8、10、9、7、12、14、13、18、25、20、15、11。

图5-23 二叉搜索树的后序遍历顺序

后序遍历的思路与前序、中序遍历的思路保持一致，只是递归打印位置发生变化。

▼
ts
复制代码
// 后序遍历
postOrderTraverse() {
  this.postOrderTraverseNode(this.root)
}
private postOrderTraverseNode(node: TreeNode<T> | null) {
  if (node) {
    this.postOrderTraverseNode(node.left) // 先访问左子树
    this.postOrderTraverseNode(node.right) // 再访问右子树
    console.log(node.value) // 最后访问根节点
  }
}

所以先序/中序/后序的区别只在于访问根节点（root）的时机：先访问根节点（先序）；中间访问根节点（中序）；最后访问根节点（后序）。规则总结如下3点：

（1）先序：根、左、右。

（2）中序：左、根、右。

（3）后序：左、右、根。

5.5.5 层序遍历实现

层序遍历很好理解，就是从上往下逐层遍历，每层从左往右的访问，因此层序遍历可以利用队列的先进先出特性来完成。实现步骤为以下3步：

（1）创建一个队列，并把根节点入队。

（2）以根节点为开端，开始逐层遍历。

（3）每次遍历取出队列的头部节点并访问，并且判断该节点是否有左右节点，有则入队，无则跳过，循环遍历到队列为空。

层序遍历从根节点开始，按照“自上而下、从左到右”的顺序依次访问节点。每访问一个节点时，就把它的左、右子节点依次加入队列。由于每次访问都伴随“当前节点出队、子节点入队”，队列中元素数量会随着遍历层数缓慢增加或保持稳定；当遍历到叶子节点（没有子节点）时，队列开始只出不进，长度逐渐减少，最终变为空，遍历结束。

只要能够以层序遍历的规则访问到节点，是打印还是存储后用于其他操作都是非常方便的。

在实现过程中，做边界判断：检查是否有根节点，无根节点则直接返回，无需遍历。并且由于完美二叉树的情况是较为少见的，所以在逐层遍历的过程中，是有可能访问不到值的，因此需要对节点进行判断是否有值，有值才push到队列之中。

▼
ts
复制代码
// 层序遍历
levelOrderTraverse() {
  // 1.如果没有根节点, 那么不需要遍历
  if (!this.root) return

  // 2.创建队列结构
  const queue: TreeNode<T>[] = []
  // 第一个节点时根节点
  queue.push(this.root)

  // 3.遍历队列中所有的节点(依次出队)
  while (queue.length) {
    // 3.1.访问节点的过程
    const current = queue.shift()!
    console.log(current.value)

    // 3.2.将左子节点放入到队列
    if (current.left) {
      queue.push(current.left)
    }

    // 3.3.将右子节点放入到队列
    if (current.right) {
      queue.push(current.right)
    }
  }
}

5.6 二叉搜索树操作 - 查找与删除

5.6.1 最值查找方法

最值的查找有两种：最大值与最小值。在二叉搜索树中搜索最值是一件非常简单的事情，最值寻找如图5-24所示。对于二叉搜索树来说，最小值就是最左侧的叶子节点，最大值就是最右侧的叶子节点。

图5-24 二叉搜索树的最值寻找

如果让我们来实现这两个方法，两个方法的逻辑必然是类似的。求最小值主要为以下2步：

（1）访问根节点。

（2）从根节点开始递归访问左子节点，直到左子节点为空之后，返回当前节点。

▼
ts
复制代码
getMaxValue(node = this.root): T | null {
  return node?.right ? this.getMaxValue(node.right) : node?.value ?? null
}

getMinValue(node = this.root): T | null {
  return node?.left ? this.getMinValue(node.left) : node?.value ?? null
}

当然，我们这里不一定要使用递归，使用循环也是可以的，循环的终止条件分别为左右子节点为null。

▼
ts
复制代码
/** 获取最值操作: 最大值/最小值 */
getMaxValue(): T | null {
  let current = this.root
  while (current && current.right) {
    current = current.right
  }

  return current?.value ?? null
}

getMinValue(): T | null {
  let current = this.root
  while (current && current.left) {
    current = current.left
  }

  return current?.value ?? null
}

5.6.2 特定值搜索（递归与非递归）

二叉搜索树不仅仅获取最值效率非常高，搜索特定的值效率也非常高。特点值的搜索是传入数值与二叉搜索树节点的数值不断比对的过程，传入数值更大，则进入当前节点的右子节点继续比对，反之则进入当前节点的左子节点比对，比对上之后返回结果，比对到叶子节点还未搜索到特定值则返回false来表明未找到。

因此特点值的搜索分3步骤：

（1）判断拿到的节点是否是搜索的节点，如果是直接返回true。

（2）拿到的节点比搜索的节点小，进入当前节点的右子树；拿到的节点比搜索的节点大，进入当前节点的左子树。

（3）逐层循环对比，直到找到结果或者没有结果返回false。

▼
ts
复制代码
search(value: T): boolean {
  let current = this.root
  while (current) {
    // 找到了节点
    if (current.value === value) return true

    if (current.value < value) {
      current = current.right
    } else {
      current = current.left
    }
  }

  return false
}

接下来是递归的写法，递归必须有退出条件，我们这里是两种情况下退出：

（1）node === null，也就是后面不再有节点的时候。

（2）找到对应的value，也就是node.value === value的时候。

在其他情况下，根据node.的value和传入的value进行比较来决定向左还是向右查找。如果node.value > value，那么说明传入的值更小，需要向左查找。如果node.value < value，那么说明传入的值更大，需要向右查找。

▼
ts
复制代码
// 搜索特定的值
search(value: T): boolean {
  return this.searchNode(this.root, value)
}

private searchNode(node: Node<T> | null, value: T): boolean {
  // 1. 如果节点为 null，直接退出递归
  if (node === null) return false

  // 2. 判断节点值和传入 value 的大小
  if (node.value > value) {          
    // 在左边继续查
    return this.searchNode(node.left, value)
  } else if (node.value < value) {   
    // 在右边继续查找
    return this.searchNode(node.right, value)
  } else {
    return true
  }
}

5.6.3 删除操作 - 无子节点情况

二叉搜索树的删除有些复杂，我们一点点完成。删除节点要从查找要删的节点开始，找到节点后，需要考虑3种情况：

（1）该节点是叶子节点（没有子节点，比较简单）。

（2）该节点有一个子节点（相对简单）。

（3）该节点有两个子节点（情况比较复杂）。

除此之外，还有一些边界情况的判断，例如要删除的节点并不在二叉搜索树中，那么就不需要我们去执行实际操作。如图5-25所示，我如果想要删除以下3种不同情况的节点（对应3种需要考虑的情况），所需要做出的准备与难度也是不同的：

（1）删除节点3。通过特定值搜索到节点3，将其置为null。

（2）删除节点5。通过特定值搜索到节点5，发现节点5存在一个子节点，需要将节点7的左子节点置为节点3，从而删除节点5。

（3）删除节点9。通过特定值搜索到节点9，发现节点9存在两个子节点，这是需要更复杂的判断操作，我们放在5.6.5小节中进行学习。

图5-25 二叉搜索树的删除示例

现在，我们来完成删除无子节点（叶子节点）的情况，与特定值搜索一致的逻辑，然后将值置为null即可。通过remove()方法实现删除操作，接收需要删除的节点值，返回布尔值来表达删除情况。这个删除操作的模板我们可以用在三种不同的删除情况处理中，最后将三种情况合并处理。

▼
ts
复制代码
/** 实现删除操作 */
remove(value: T): boolean {

}

remove()删除方法需要以下2个步骤：

（1）搜索是否有要删除的值，没有就直接返回false。

（2）有要删除的值，将叶子节点置为null。

可惜5.6.2小节的search()方法无法复用，因为search()方法返回的是布尔值，并不能让我们拿到对应的节点。不过这部分找到对应节点的代码开始重复了，我们后续可以做出优化。

▼
ts
复制代码
/** 实现删除操作 */
remove(value: T): boolean {
  // 判断需要删除节点是否在二叉搜索树中，若不在直接返回
  if(!this.search(value)) return false
  let current = this.root
  while (current) {
    // 找到了叶子节点 将其置为null
    if (current.value === value) current.value == null

    if (current.value < value) {
      current = current.right
    } else {
      current = current.left
    }
  }

  return true
}

那么以上的做法真的可以吗？当然是不行的，虽然传入需要删除的叶子节点值确实能删除，边界判断也处理了，但存在两个非常关键的问题：

（1）删除操作应该将目标的叶子节点置为null，我们以上代码置为null的是叶子节点值，而非叶子节点本身。只将叶子节点值置为null虽然简单，但该节点依然存在树中，只是值没了，之后的遍历、搜索、插入都可能出现混乱。我们真正要做的是找到目标节点的父节点，把父节点对应的子节点置为null。因此我们还需要一个属性来存储需要删除目标子节点的父节点。

（2）我们怎么把判断叶子节点的事情交给使用者了？如果使用者不知道自己要删除的是叶子节点呢，那这份代码就会出现问题。在这里我们犯了一个先入为主，认为使用者知道自己删除的节点是哪一种情况，然后会调用对应情况的方法。实际中当然不可以这么做，我们应该在封装删除方法的过程中就做好对应判断。

好的，所以我们先来解决第一个问题，拿到需要删除目标子节点的同时，拿到对应的父节点。

▼
ts
复制代码
/** 实现删除操作 */
remove(value: T): boolean {
  // 1.搜索: 当前是否有这个value
  let current = this.root
  let parent: TreeNode<T> | null = null
  while (current) {
    if (current.value === value) break
	// 拿到需要删除目标子节点的对应父节点
    parent = current
    if (current.value < value) {
      current = current.right
    } else {
      current = current.left
    }
  }

  console.log(current?.value, parent?.value)

  return true
}

接着我们优化抽取一下搜索节点的代码逻辑，实现一个searchNode()私有方法，该方法接收一个value值，返回搜索到的节点本身，同时允许返回null（没搜索到目标节点）。

▼
ts
复制代码
private searchNode(value: T): TreeNode<T> | null {
  let current = this.root
  while (current) {
    // 1.如果找到current, 直接返回即可
    if (current.value === value) {
      return current
    }

    // 2.继续向下找
    if (current.value < value) {
      current = current.right
    } else {
      current = current.left
    }

  }

  return null
}

然后验证一下重构之后的search()方法是否可以正常调用。

▼
ts
复制代码
/** 搜索特定的值: 20 => boolean */
search(value: T): boolean {
  return !!this.searchNode(value)
}

接着继续来实现我们的remove()方法，通过searchNode()私有方法能够获取到目标节点，但目标节点的父节点呢？要如何获取？

有没有一种可能，我们可以让searchNode()私有方法返回一个元组，就类似于React Hook中的useState：

const [目标节点, 父节点] = searchNode(value)

确实可以这么做，但其实我们可以有更好的方法，目前的节点有left、right和value三个属性，我们再添加一个parent父节点属性，在获取到目标节点的同时，可通过访问该节点的parent属性拿到对应父节点。因为节点其实是一个静态且独立自制的，所以我们可以采用这种形式去获取。

那么，我们在返回current的上一次循环中，将current节点的父节点保存在parent属性中，但parent属性是有可能为null的，有且只有根节点的parent属性为null，因此定义parent属性时需要联合类型一下。

▼
ts
复制代码
class TreeNode<T> extends Node<T> {
  left: TreeNode<T> | null = null
  right: TreeNode<T> | null = null

  // 当前节点的父节点
  parent: TreeNode<T> | null = null
}

private searchNode(value: T): TreeNode<T> | null {
  let current = this.root
  let parent: TreeNode<T> | null = null
  while (current) {
    // 1.如果找到current, 直接返回即可
    if (current.value === value) {
      return current
    }

    // 2.继续向下找
    parent = current
    if (current.value < value) {
      current = current.right
    } else {
      current = current.left
    }

    // 如果current有值, 那么current保存自己的父节点
    if (current) current.parent = parent
  }

  return null
}

那么在remove()删除方法中，就可以采用current.parent?.value的形式拿到目标节点的父节点。

▼
ts
复制代码
  /** 实现删除操作 */
  remove(value: T): boolean {
    // 1.搜索: 当前是否有这个value
    const current = this.searchNode(value)
    if (!current) return false

    // 2.获取到三个东西: 当前节点/父节点/是属于父节点的左子节点, 还是右子节点
    console.log("当前节点:", current.value, "父节点:", current.parent?.value)

    return true
  }

接着我们应该来解决第二个问题：判断用户传入的节点存在后，要继续判断是否为叶子节点。当目标节点为叶子节点，才判断父节点的左右子节点与目标节点是否相同，从而判断目标节点位于父节点的哪一边，从而将对应左右目标子节点置为null。

▼
ts
复制代码
if(current.parent?.left === current) {
  // current在父节点的左边
} else {
  // current在父节点的右边
}

但判断删除的节点在父节点哪边的这一操作是很有可能复用的，在接下来的单子节点情况以及双子节点情况的两种处理中都很有可能会用到这一判断，那么为了防止代码的多次重复，我们就可以提前将这一判断操作封装成一个私有方法。为了方便，我们可以使用get语法将对象属性绑定到查询该属性时将被调用的函数方法。

无论是判断左子节点的isLeft()私有方法还是判断右子节点的isRight()私有方法都可以达成我们的目的，选择其中一个私有方法就可以。判断左右子节点也并非只有一种方法，如果是为了更好理解，则可以传入当前节点与父节点两个参数，返回布尔值或者其他格式信息（left or right）作为判断标准。这种传入两个参数做法的可复用性更强，但我们这里的实际需求并不需要做到该程度。因此直接固定死对应部分的判断，无需传入参数，直接返回布尔值结果。

▼
ts
复制代码
// 判断当前节点的父节点是否拥有左子节点
get isLeft(): boolean {
  return !!(this.parent && this.parent.left === this)
}

// 判断当前节点的父节点是否拥有右子节点
get isRight(): boolean {
  return !!(this.parent && this.parent.right === this)
}

接着完成无子节点情况的具体删除以及对叶子节点的判断（待解决的第二个问题）。在删除无子节点的叶子节点情况中，有一种情况，即除了根节点之外的所有节点都删完了，那么根节点同时也是叶子节点，因此我们需要在判断叶子节点的基础上额外判断当前节点是否为根节点，若为根节点则直接将二叉树的root属性（根节点）置为null就可以。

▼
ts
复制代码
/** 实现删除操作 */
remove(value: T): boolean {
  // 1.搜索: 当前是否有这个value
  const current = this.searchNode(value)
  if (!current) return false

  // 2.获取到三个东西: 当前节点/父节点/是属于父节点的左子节点, 还是右子节点
  // 2.判断删除的是否为叶子节点
  if (current.left === null && current.right === null) {
    if (current === this.root) { // 根节点
      this.root = null
    } else if (current.isLeft) { // 父节点的左子节点
      current.parent!.left = null
    } else {
      current.parent!.right = null
    }
  }

  return true
}

5.6.4 删除操作 - 单子节点情况

那么单子节点的情况就是获取目标节点的单子节点，然后直接覆盖掉目标节点就可以了，如图5-26所示就是"删除"节点15，该节点存在一个单子节点13（该单子节点未必是叶节点，但不影响代码书写），我们需要做的是判断目标节点是否为单子节点。

图5-26 删除操作 - 单子节点情况

那么，判断目标节点是否为单子节点直接判断当前节点的左右节点是否只有为null，，而判断目标节点位于父节点的左右节点则可以使用isLeft()和isRight()私有方法。处理单子节点分两种情况：

（1）处理左子节点：将当前节点的左子节点赋值给当前节点的父节点的对应节点。

（2）处理右子节点：将当前节点的右子节点赋值给当前节点的父节点的对应节点。

所以这里其实有4种情况，即当前节点处于父节点的两种情况以及当前节点的左右子节点两种情况。我们的判断逻辑接续在判断无子节点情况的后面。往后判断双子节点的情况也会接续在判断单子节点的情况下。

▼
ts
复制代码
// 3.只有一个子节点: 只有左子节点
    else if (current.right === null) {
      if (current === this.root) { // 根节点情况
        this.root = current.left
      } else if (current.isLeft) { // 目标节点是父节点的左子节点
        current.parent!.left = current.left // 将目标节点的左子节点赋值给父节点的左子节点
      } else {
        current.parent!.right = current.left // 将目标节点的左子节点赋值给父节点的右子节点
      }
    }
    
    // 4.只有一个子节点: 只有右子节点
    else if (current.left === null) {
      if (current === this.root) { // 根节点情况
        this.root = current.right
      } else if (current.isLeft) { // 同上
        current.parent!.left = current.right // 同上
      } else {
        current.parent!.right = current.right // 同上
      }
    }

5.6.5 删除操作 - 双子节点情况

删除操作需要考虑的最后一种情况是删除的目标节点同时具备左右子节点，那么我们就不能简单的将某一个目标节点的子节点覆盖掉目标节点。以图5-27所示的二叉搜索树为例，考虑以下3种情况如何处理：

（1）删除节点9。将节点8替换到节点9的位置或者将节点10替换到节点9的位置。在替换的过程中，例如节点8->节点9时，节点7需要指向节点8，节点8需要指向节点10。

（2）删除节点7。分两种情况，方式一：将节点5替换节点7，节点3依然被节点5指向，但是5有一个right需要指向节点9，这样依旧保持二叉搜索树；方式二：在目标节点7的右侧找节点8，将节点8替换到节点7的位置，节点8的left指向节点5，right指向节点9。

（3）删除节点15。如果像删除节点7的方式二一样从目标节点的右子树中寻找，我们能找到的是节点18，将节点18替换节点15，节点20的left指向节点19，这样也是一棵二叉搜索树。

情况看起来很多变，我们要找出其中的规律。

图5-27 删除操作 - 双子节点情况

规律是这样的，假如我们要删除一个目标节点，而目标节点有两个子节点，我们有两种方式：

（1）到目标节点的左子树中找一个比目标节点小，同时是：目标节点左子树中的最大节点（目标节点左子树的最大值）。

（2）到目标节点的右子树中找一个比目标节点大，同时是：目标节点右子树中的最小节点（目标节点右子树的最小值）。

如果我们要删除的目标节点有两个子节点，甚至子节点还有子节点，这种情况下我们需要从目标节点下面的子节点中找到一个节点，来替换当前的节点。但是找到的这个节点有什么特征呢？应该是current节点下面所有节点中最接近current节点的。要么比current节点小一点点，要么比current节点大一点点。最接近current值的子节点，就可以用来替换current的位置。

在二叉搜索树中，我们所想要寻找的目标节点左右子树两侧的那特别节点，有特别的名字：比目标节点小一点点的节点，称为目标节点的前驱；比目标节点大一点点的节点，称为目标节点的后继。也就是为了能够删除有两个子节点的目标节点，要么找到它的前驱，要么找到它的后继。所以接下来，我们要先找到这样的节点。PS：以下代码采用后继节点的方式。

由于采用获取后继节点的方式，因此需要去目标节点的右子树中寻找最小值。获取最值的问题是很简单的，我们只要以需要删除的目标节点为根节点，寻找其左子树中最左侧的节点。由于getMinValue()方法的节点是固定死当前二叉搜索树的根节点，因此我们可能需要重新实现，或者可以再封装一个私有的方法，然后复用。根据自己的想法决定，这里就不进一步抽象了。

我们删除目标节点存在双子节点的情况需要以下4个步骤：

（1）找后继节点（右子树最左节点）。

（2）若后继不是右子节点，先把它从原位置挪出来。

PS：后继节点是右子树的最左节点，所以它一定没有左子节点，但它可能有右子节点，并不是始终没有右子节点。

（3）将目标节点的左子树挂到后继节点上。

（4）用后继节点替换目标节点的位置。

我们先实现getSuccessor()私有方法，该方法传入我们想删除的目标节点，返回后继节点。在该私有方法中同时需要在找到后继节点之后，需要做两件事情：

（1）后继节点的右子树顶替后继节点的位置（把后继节点从原位置挪出来）。

（2）后继节点的左侧（左子节点）需要接收将要被删除目标节点的左侧（左节点），后继节点的右侧（右子节点）需要接收将要被删除目标节点的右侧（右节点）。

其实这两件事情还是很好理解的，后继节点替代了目标节点，那么后继节点既要处理自己可能存在的右子树，还要继承被替代的目标节点的左右子树。但有一种情况，即后继节点刚好是目标节点的右子节点，那么后续节点替换目标节点之后，就不需要处理自己可能存在的右子树了，因为此时后继节点的右子树就刚好可以继续作为替换目标节点之后的右子树，只需要接管原有目标节点的左子树。针对该情况，我们需要做出以下2点处理：

（1）若后继节点不是目标节点的右子节点：要将后继节点的右子树顶替其原位置，并且后继节点接管目标节点的右子树。反之则不用。

（2）后继节点必须接管目标节点的左子树。

▼
ts
复制代码
private getSuccessor(delNode: TreeNode<T>): TreeNode<T> {
  // 获取右子树
  let current = delNode.right
  // 后继节点
  let successor: TreeNode<T> | null = null
  // 获取后继节点，可以考虑和最值方法抽取共性代码来复用
  while (current) {
    successor = current
    current = current.left
    // 获取后继节点的父节点
    if (current) {
      current.parent = successor
    }
  }

  // 若后继节点不是目标节点的右子节点
  if (successor !== delNode.right) {
    successor!.parent!.left = successor!.right // 将后继节点的右子树顶替其原位置（需要拿到后继节点的父节点才能真正替换调后继节点）。
    successor!.right = delNode.right // 后继节点接管目标节点的右子树。
  }

  // 后继节点必须接管目标节点的左子树。
  successor!.left = delNode.left

  return successor!
}

通过getSuccessor()私有方法实现了以下3点目的：

（1）获取后继节点。

（2）后继节点继承被删除目标节点的左右子树。

（3）令后继节点可能存在的右子树继承后继节点原有位置，将后继节点腾出来。

接下来我们需要继续完成删除操作的最后一种情况，双子节点情况。获取了getSuccessor()私有方法返回的后继节点，我们需要使用后继节点替换要删除的目标节点在整棵树中的位置，即令原目标节点的父结点指向后继节点。这里有3种情况，分别处理：

（1）原目标节点的父节点是根节点。

（2）原目标节点在父节点的左节点。

（3）原目标节点在父节点的右节点。

▼
ts
复制代码
else {
  const successor = this.getSuccessor(current)
  if (current === this.root) {
    this.root = successor
  } else if (current.isLeft) {
    current.parent!.left = successor
  } else {
    current.parent!.right = successor
  }
}

5.6.6 优化重构代码

通过5.6.3、5.6.4和5.6.5小节，我们完成了删除目标节点的整体功能，但在判断删除的是否是叶子节点、只有一个子节点（只有左子节点，只有右子节点）以及由双子节点的时候，判断逻辑是不断重复的。

▼
ts
复制代码
// 判断叶子节点
current.left === null && current.right === null
// 判断只有左子节点
current.right === null
// 判断只有右子节点
current.left === null

以及内部的3种边界情况判断：原目标节点的父节点是根节点、原目标节点在父节点的左节点，原目标节点在父节点的右节点。

▼
ts
复制代码
if (current === this.root) {
  // 原目标节点的父节点是根节点
  this.root =
} else if (current.isLeft) {
  // 原目标节点在父节点的左节点
  current.parent!.left =
} else {
  // 原目标节点在父节点的右节点
  current.parent!.right =
}

那么，能否将以上的判断部分抽取出来，倘若可以抽取，又要如何抽取？在删除节点时，不管它是叶子节点、单子节点、双子节点，最终的目的都是：确定一个用来替换它的新节点（replaceNode），然后把它挂回去。

所以remove()删除方法逻辑可以统一成两步：

（1）找到用来替换的位置节点replaceNode。

（2）把replaceNode挂到父节点的对应位置。

▼
ts
复制代码
if (current === this.root) {
  this.root = replaceNode
} else if (current.isLeft) {
  current.parent!.left = replaceNode
} else {
  current.parent!.right = replaceNode
}

重构之前，我们的三段长逻辑分别处理叶子、单左和单右节点，每段都要写一遍是不是root，是不是左子节点，是不是右子节点。

▼
ts
复制代码
// 重构前的代码
  remove(value: T): boolean {
    // 1.搜索: 当前是否有这个value
    const current = this.searchNode(value)
    if (!current) return false

    // 2.获取到三个东西: 当前节点/父节点/是属于父节点的左子节点, 还是右子节点
    // 2.如果删除的是叶子节点
    if (current.left === null && current.right === null) {
      if (current === this.root) { // 根节点
        this.root = null
      } else if (current.isLeft) { // 父节点的左子节点
        current.parent!.left = null
      } else {
        current.parent!.right = null
      }
    }
    
    // 3.只有一个子节点: 只有左子节点
    else if (current.right === null) {
      if (current === this.root) {
        this.root = current.left
      } else if (current.isLeft) {
        current.parent!.left = current.left
      } else {
        current.parent!.right = current.left
      }
    }
    
    // 4.只有一个子节点: 只有右子节点
    else if (current.left === null) {
      if (current === this.root) {
        this.root = current.right
      } else if (current.isLeft) {
        current.parent!.left = current.right
      } else {
        current.parent!.right = current.right
      }
    }

    // 5.有两个子节点
    else {
      const successor = this.getSuccessor(current)
      if (current === this.root) {
        this.root = successor
      } else if (current.isLeft) {
        current.parent!.left = successor
      } else {
        current.parent!.right = successor
      }
    }

    return true
  }

核心思想是：删除一个节点时，不再把叶子节点、只有一个子节点、或者有两个子节点分别写成三套不同的处理流程，而是统一成一个动作——先判断“谁来替代被删除的节点”，然后再把这个替代者挂回到原来的位置。这相当于把复杂流程拆成两个简单的步骤，因此代码自然就清晰、简洁、可维护性更高。

▼
ts
复制代码
// 重构后的代码
remove(value: T): boolean {
  // 1.搜索: 当前是否有这个value
  const current = this.searchNode(value)
  if (!current) return false

  // 2.获取到三个东西: 当前节点/父节点/是属于父节点的左子节点, 还是右子节点
  let replaceNode: TreeNode<T> | null = null
  if (current.left === null && current.right === null) {
    replaceNode = null
  } else if (current.right === null) {
    replaceNode = current.left
  } else if (current.left === null) {
    replaceNode = current.right
  } else {
    const successor = this.getSuccessor(current)
    replaceNode = successor
  }

  // 由replaceNode统一管理不同情况所获取到的节点。
  if (current === this.root) {
    this.root = replaceNode
  } else if (current.isLeft) {
    current.parent!.left = replaceNode
  } else {
    current.parent!.right = replaceNode
  }

  return true
}

但是为什么可以统一成一个replaceNode？因为无论删除的是哪种情况，BST删除的本质永远一致：父节点“失去”这个节点，然后必须要有一个新的节点来填补这个空位。不同的只是“哪个节点来替代它”。所以可以把所有情况浓缩为四种选择——没有节点（null）、左孩子、右孩子、或者后继节点（successor）。把这四种用一个变量 replaceNode 表示，就能把不同分支合并成统一结构，减少重复逻辑。

当我们把“不同情况决定用哪个节点替代”这一部分抽离出来后，“如何把替代节点挂接到父节点”这段逻辑就完全可以写成统一三步：若被删除的是根节点，则替换根；若被删除的是父节点的左子，则把父节点的左子改成新节点；否则改成父节点的右子。这三种情况本来在原代码中被重复写了多次，现在只需要写一次，代码自然变得短、更不容易出错、维护成本更低。

它的原理就是“分离关注点”（Separation of Concerns）。在重构后，删除操作被拆成两个相互独立的小问题：

（1）用哪个节点来替换当前节点（逻辑条件判断）。

（2）把替代者挂到父节点的正确位置（固定模板逻辑）。

5.6.7 删除操作总结

看到这里，你就会发现删除节点相当棘手。实际上，因为它非常复杂，一些程序员都尝试着避开删除操作。他们的做法是在Node类中添加一个boolean的字段，例如名称为isDeleted。要删除一个节点时，就将此字段设置为true。其他操作，例如find()在查找之前先判断这个节点是不是标记为删除。这样相对比较简单，每次删除节点不会改变原有的树结构，但是在二叉树的存储中，还保留着那些本该已经被删除掉的节点。这种做法在5.6.3小节的开头就尝试过类似的，并且说明了其中的缺陷与弊端。

那种做法看起来很聪明，其实是一种逃避。这样会造成很大空间的浪费，特别是针对数据量较大的情况。而且，作为程序员要学会通过这些复杂的操作，锻炼自己的逻辑。

最后，我们将最终实现版本的二叉搜索树操作代码示例放在下方。

▼
ts
复制代码
import Node from "../types/Node"

import { btPrint } from 'hy-algokit'

class TreeNode<T> extends Node<T> {
  left: TreeNode<T> | null = null
  right: TreeNode<T> | null = null

  // 当前节点的父节点
  parent: TreeNode<T> | null = null

  // 判断当前节点是父节点的左子节点
  get isLeft(): boolean {
    return !!(this.parent && this.parent.left === this)
  }

  // 判断当前节点是父节点的右子节点
  get isRight(): boolean {
    return !!(this.parent && this.parent.right === this)
  }
}

class BSTree<T> {
  private root: TreeNode<T> | null = null

  print() {
    btPrint(this.root)
  }

  private searchNode(value: T): TreeNode<T> | null {
    let current = this.root
    let parent: TreeNode<T> | null = null
    while (current) {
      // 1.如果找到current, 直接返回即可
      if (current.value === value) {
        return current
      }

      // 2.继续向下找
      parent = current
      if (current.value < value) {
        current = current.right
      } else {
        current = current.left
      }

      // 如果current有值, 那么current保存自己的父节点
      if (current) current.parent = parent
    }

    return null
  }

  /** 插入数据的操作 */
  insert(value: T) {
    // 1.根据传入value创建Node(TreeNode)节点
    const newNode = new TreeNode(value)

    // 2.判断当前是否已经有了根节点
    if (!this.root) { // 当前树为空
      this.root = newNode
    } else { // 树中已经有其他值
      this.insertNode(this.root, newNode)
    }
  }

  private insertNode(node: TreeNode<T>, newNode: TreeNode<T>) {
    if (newNode.value < node.value) { // 去左边继续查找空白位置
      if (node.left === null) { // node节点的左边已经是空白
        node.left = newNode
      } else {
        this.insertNode(node.left, newNode)
      }
    } else { // 去右边继续查找空白位置
      if (node.right === null) {
        node.right = newNode
      } else {
        this.insertNode(node.right, newNode)
      }
    }
  }

  /** 遍历的操作 */
  // 先序遍历
  preOrderTraverse() {
    this.preOrderTraverseNode(this.root)
  }
  private preOrderTraverseNode(node: TreeNode<T> | null) {
    if (node) {
      console.log(node.value)
      this.preOrderTraverseNode(node.left)
      this.preOrderTraverseNode(node.right)
    }
  }

  // 中序遍历
  inOrderTraverse() {
    this.inOrderTraverseNode(this.root)
  }
  private inOrderTraverseNode(node: TreeNode<T> | null) {
    if (node) {
      this.inOrderTraverseNode(node.left)
      console.log(node.value)
      this.inOrderTraverseNode(node.right)
    }
  }

  // 后序遍历
  postOrderTraverse() {
    this.postOrderTraverseNode(this.root)
  }
  private postOrderTraverseNode(node: TreeNode<T> | null) {
    if (node) {
      this.postOrderTraverseNode(node.left)
      this.postOrderTraverseNode(node.right)
      console.log(node.value)
    }
  }

  // 层序遍历
  levelOrderTraverse() {
    // 1.如果没有根节点, 那么不需要遍历
    if (!this.root) return

    // 2.创建队列结构
    const queue: TreeNode<T>[] = []
    // 第一个节点时根节点
    queue.push(this.root)

    // 3.遍历队列中所有的节点(依次出队)
    while (queue.length) {
      // 3.1.访问节点的过程
      const current = queue.shift()!
      console.log(current.value)

      // 3.2.将左子节点放入到队列
      if (current.left) {
        queue.push(current.left)
      }

      // 3.3.将右子节点放入到队列
      if (current.right) {
        queue.push(current.right)
      }
    }
  }


  /** 获取最值操作: 最大值/最小值 */
  getMaxValue(): T | null {
    let current = this.root
    while (current && current.right) {
      current = current.right
    }

    return current?.value ?? null
  }

  getMinValue(): T | null {
    let current = this.root
    while (current && current.left) {
      current = current.left
    }

    return current?.value ?? null
  }

  /** 搜索特定的值: 20 => boolean */
  search(value: T): boolean {
    return !!this.searchNode(value)
  }


  /** 实现删除操作 */
  private getSuccessor(delNode: TreeNode<T>): TreeNode<T> {
    // 获取右子树
    let current = delNode.right
    let successor: TreeNode<T> | null = null
    while (current) {
      successor = current
      current = current.left
      if (current) {
        current.parent = successor
      }
    }

    // 拿到了后继节点
    if (successor !== delNode.right) {
      successor!.parent!.left = successor!.right
      successor!.right = delNode.right
    }

    // 一定要进行的操作: 将删除节点的left, 赋值给后继节点的left
    successor!.left = delNode.left

    return successor!
  }

  remove(value: T): boolean {
    // 1.搜索: 当前是否有这个value
    const current = this.searchNode(value)
    if (!current) return false

    // 2.获取到三个东西: 当前节点/父节点/是属于父节点的左子节点, 还是右子节点
    let replaceNode: TreeNode<T> | null = null
    if (current.left === null && current.right === null) {
      replaceNode = null
    } else if (current.right === null) {
      replaceNode = current.left
    } else if (current.left === null) {
      replaceNode = current.right
    } else {
      const successor = this.getSuccessor(current)
      replaceNode = successor
    }

    if (current === this.root) {
      this.root = replaceNode
    } else if (current.isLeft) {
      current.parent!.left = replaceNode
    } else {
      current.parent!.right = replaceNode
    }

    return true
  }
}

const bst = new BSTree<number>()
bst.insert(11)
bst.insert(7)
bst.insert(15)
bst.insert(5)
bst.insert(3)
bst.insert(9)
bst.insert(8)
bst.insert(10)
bst.insert(13)
bst.insert(12)
bst.insert(14)
bst.insert(20)
bst.insert(18)
bst.insert(25)
bst.insert(6)

bst.print()

// bst.preOrderTraverse()
// bst.inOrderTraverse()
// bst.postOrderTraverse()
// bst.levelOrderTraverse()

// console.log(bst.getMaxValue())
// console.log(bst.getMinValue())

// console.log(bst.search(20))
// console.log(bst.search(18))
// console.log(bst.search(6))
// console.log(bst.search(30))


// 删除功能: 删除有两个子节点的情况
bst.remove(11)
bst.print()
bst.remove(15)
bst.print()
bst.remove(9)
bst.print()
bst.remove(7)
bst.print()


export {}

哪怕是优化抽象重构后的代码也有接近300行代码，因此完全掌握下来并不是一件轻松的事情。虽然在如今我们可以利用AI快速的优化并且做得一样好，但我们的逻辑并没有得到锻炼，长久之后，我们的理解能力也会下降，直到有一天连AI给出的优化代码都看不明白，连AI给出的解释都理解得费力。当放弃去理解其中的逻辑，就是将自身的主体性拱手让出，我觉得不是一件很OK的事情。

5.7 二叉搜索树的缺陷与平衡树

5.7.1 二叉搜索树的缺陷

二叉搜索树作为数据存储的结构有重要的优势：可以快速地找到给定关键字的数据项并且可以快速地插入和删除数据项。但是二叉搜索树有一个很麻烦的问题，如果插入的数据是有序的数据，比如下面的情况：

有一棵初始化为 9 8 12 的二叉树，如图5-28所示。

图5-28 二叉树的缺陷-A

插入数据：7 6 5 4 3，展现效果如图5-29所示。

图5-29 二叉树的缺陷-B

如图5-29所示的这一棵二叉搜索树长得实在太奇怪了，看起来相对于树来说更像一道抛物线。当我们把有序的数据依次插入普通的二叉搜索树（BST）时，树不会长成“左右均匀”的形状，而是沿着一条方向一直长下去：递增序列会产生完全右偏的树（每个节点只有右子节点）；递减序列会产生完全左偏的树（每个节点只有左子节点）。形象地说，BST 会“退化”为一个链表。

正常的二叉搜索树，如果左右分布相对均匀，它的高度大约是logN，因此查找、插入、删除操作都很快。但在数据有序的情况下，树不断往一条链上长，最终高度变成N。一个本应像金字塔一样层层展开的树，此时却变成一条斜着的链。这样的结构就叫非平衡树——左右子树极度不均匀。

因为树退化成链表，每次查找、插入或删除一个节点都必须从根节点一路走到最底部，最坏情况要访问所有节点，因此时间复杂度变成O(N)。这比原本的 O(logN) 慢了一个数量级。在数据量大的情况下，这种性能差异会非常明显，甚至可能导致程序卡顿、响应变慢。

除了时间复杂度变差，树变成链表还有额外的工程隐患，例如：递归操作的深度变得很大，有可能造成栈溢出；链表状结构使得指针访问更加分散，CPU缓存利用率降低；删除节点时需要处理的指针情况更复杂，出错概率更高。看似是一个结构问题，实质上会带来性能与稳定性的全面下降。

为了避免普通 BST 在有序数据下退化，实际开发中通常不会使用简单的二叉搜索树，而会使用能够自动保持平衡的自平衡树（如 AVL 树、红黑树等）；或者在需要有序结构时，直接选择其他更稳定的数据结构，比如跳表、B 树、堆、哈希表等。核心思想就是避免“连续插入有序数据导致一条长链”的最坏情况发生。

5.7.2 树的平衡性与平衡树介绍

在二叉搜索树（BST）中，节点的插入顺序会极大影响树的形状。如果数据分布不均，树就可能倾斜成“单链条”，使查找、插入、删除的时间复杂度从 O(logN) 退化为 O(N)。 “树的平衡性”指的是树的高度保持在一个较低且可控的范围，使左右子树的高度差保持小，从而让操作效率保持稳定。平衡树的核心目标是避免最坏情况，使所有基本操作都能维持对数级复杂度 O(logN)。也就是说树中每个节点左边的子孙节点的个数，应该尽可能的等于右边的子孙节点的个数。

计算机中常见的平衡二叉树或多路树包括以下7种：

AVL Tree（高度平衡树）。
Red-Black Tree（红黑树）。
Splay Tree（伸展树）。
Treap（树堆，随机平衡 BST）。
Scapegoat Tree（替罪羊树）。
B-Tree / B+Tree（用于磁盘、数据库）。
Segment Tree（线段树，用于区间查询）。

这些结构都是为避免普通 BST 的极端退化情况而设计的。其中 AVL Tree 和 Red-Black Tree 是最经典、最广泛使用的两种自平衡二叉搜索树。

AVL 树是最早提出“自平衡”的二叉搜索树（1962 年），它通过为每个节点记录“平衡因子 = 左子树高度 − 右子树高度”，并强制这个值必须在 -1、0、1 之间。AVL树是在普通BST的基础上加了“严格的高度平衡规则”，当插入或删除破坏平衡时，通过单旋转 / 双旋转（LL、LR、RR、RL）自动恢复平衡。且因为AVL树是平衡的，所以时间复杂度也是O(logN)。但是，每次插入/删除操作相对于红黑树效率都不高，所以整体效率不如红黑树。

红黑树插入与删除比AVL更省时，所以它成为工业界的标准平衡树，像Java 的 TreeMap、TreeSet、ConcurrentSkipListMap（内部逻辑）；C++ 的 std::map、std::set；Linux 调度器、虚拟内存区间管理以及各种语言的基础库都能找到红黑树的身影。

总结一句话：红黑树是实践中的霸主，所以现在平衡树的应用基本都是红黑树。在第10章中，我们会专门学习到AVL树和红黑树。