计算机学习笔记 二叉搜索树核心操作（含注释代码）

二叉树专题复习笔记二叉树核心操作本次复习内容全面覆盖了二叉搜索树BST的核心操作。课程从基础的节点定义与手动构建开始逐步深入到自动插入、查找、两种遍历策略广度优先与深度优先最后攻克了最为复杂的删除操作。第一部分二叉搜索树的构建与插入1. 节点定义与手动构建节点结构二叉树的节点类Node通常包含三个核心部分value数据域用于存储节点的值。left指针域存储左子节点的内存地址。right指针域存储右子节点的内存地址。构建过程手动构建通过new关键字创建多个独立的节点对象然后通过赋值操作如n1.left n2将它们的left和right指针连接起来形成树状结构。树类封装设计一个树类Tree内部维护一个root变量作为整棵树的入口。所有操作都围绕root展开。2. 插入操作 (Insert)核心规则二叉搜索树遵循“左小右大”的原则即任意节点的左子树所有值均小于该节点右子树所有值均大于该节点。实现逻辑空树处理若root为空则直接将新节点设为根节点。非空树处理若树不为空则从root开始使用一个游标index进行遍历比较。若新节点值小于当前节点值则向左子树方向查找。若新节点值大于当前节点值则向右子树方向查找。定位插入重复上述比较过程直到找到一个空的left或right位置将新节点插入该位置。第二部分二叉树的查找与遍历1. 查找操作 (Search)核心思想充分利用BST“左小右大”的特性实现高效的二分查找。实现方式定义游标index指向root。进入循环只要index不为空就比较目标值与index.value。比较逻辑相等查找成功返回该节点。目标值更小index移向左子节点index index.left。目标值更大index移向右子节点index index.right。若循环结束仍未找到则返回null。2. 遍历操作 (Traversal)遍历是访问树中所有节点的基础主要分为广度优先和深度优先两种方式。广度优先遍历 (BFS) / 层序遍历核心思想按层级顺序从上到下、从左到右逐层访问。实现方式借助队列 (Queue)实现。将root入队。当队列不为空时循环执行节点出队并访问。将其非空的左、右子节点依次入队。关键点队列的“先进先出”特性天然保证了节点按层级顺序被处理。深度优先遍历 (DFS)核心思想沿着树的深度尽可能深地搜索分支。通常使用递归 (Recursion)实现。三种遍历方式区别在于访问根节点的时机先序遍历 (Pre-order)根 - 左 - 右。先访问当前节点再递归遍历左右子树。中序遍历 (In-order)左 - 根 - 右。先递归遍历左子树再访问当前节点最后递归遍历右子树。特性对BST进行中序遍历结果是一个有序序列。后序遍历 (Post-order)左 - 右 - 根。先递归遍历左右子树最后访问当前节点。关键点理解递归的调用栈和“触底反弹”的过程是掌握DFS的关键。第三部分二叉树的删除操作删除是BST中最复杂的操作必须在删除后仍保持树的“左小右大”结构。操作前需先定位目标节点及其父节点。1. 删除叶子节点 (无子树)情况目标节点没有左、右子树。处理若目标节点是根节点即整棵树只有一个节点直接将root置为null。若目标节点有父节点则判断它是父节点的左孩子还是右孩子然后将父节点对应的指针left或right置为null。2. 删除仅有一棵子树的节点情况目标节点只有左子树或只有右子树。处理若目标节点是根节点直接让root指向其唯一的子树根节点。若目标节点有父节点则判断它是父节点的左孩子还是右孩子然后将父节点对应的指针指向目标节点的唯一子树。这相当于让父节点“跳过”目标节点直接连接其子树。3. 删除有两棵子树的节点情况目标节点同时拥有左、右子树。这是最复杂的情况。处理采用“值替换法”。寻找替代值在目标节点的左子树中找到最大值节点或在其右子树中找到最小值节点。右子树的最小值从目标节点的右子节点开始一路向左直到左指针为空的节点。左子树的最大值从目标节点的左子节点开始一路向右直到右指针为空的节点。替换值将找到的替代值复制到目标节点上覆盖其原有值。删除替代节点在子树中删除那个被取走值的节点。关键点被选中的替代节点右子树最小值或左子树最大值本身最多只有一个子树或没有因此删除它的操作会退化为情况1或情况2从而避免了无限递归。这种方法完美地维持了二叉搜索树的性质。代码如下package tree; public class Test { public static void main(String[] args) { YouxvTree tree new YouxvTree(); tree.insert(10); tree.insert(5); tree.insert(15); tree.insert(1); tree.insert(12); tree.insert(30); System.out.println(tree.root); tree.search(10); System.out.println(tree.search(30).value); tree.levelOrder(); tree.beforeOrder(tree.root); tree.inOrder(tree.root); tree.afterOrder(tree.root); System.out.println(tree.searchParent(12).value); tree.delete(1); System.out.println(tree); } }package tree; import java.util.LinkedList; import java.util.Queue; /** * 二叉搜索树Binary Search Tree实现类 * 特点左子树所有节点值小于根节点右子树所有节点值大于根节点 */ public class YouxvTree { Node root null; // 树的根节点 /** * 插入节点 * param value 要插入的整数值 */ public void insert(int value) { Node node new Node(value); // 创建新节点 // 如果树为空新节点作为根节点 if(root null) { root node; return; } Node index root; // 从根节点开始遍历 while(index ! null) { // 如果当前节点值小于新节点值向右子树移动 if(index.value node.value) { if(index.right null) { // 右子树为空直接插入 index.right node; return; } else { index index.right; // 继续向右遍历 } } // 如果当前节点值大于新节点值向左子树移动 if(index.value node.value) { if(index.left null) { // 左子树为空直接插入 index.left node; return; } else { index index.left; // 继续向左遍历 } } } } /** * 查找指定值的节点 * param nums 要查找的值 * return 找到的节点如果未找到返回null */ public Node search(int nums) { Node index root; while(index ! null) { if(index.value nums) { // 找到目标节点 System.out.println(Found); return index; } else if(index.value nums) { // 目标值较大向右查找 index index.right; } else { // 目标值较小向左查找 index index.left; } } System.out.println(NotFound); return null; } /** * 查找指定值节点的父节点 * param nums 要查找的值 * return 父节点如果该节点是根节点或未找到则返回null */ public Node searchParent(int nums) { // 如果树为空或查找的是根节点没有父节点 if (root null || root.value nums) { return null; } Node current root; while (current ! null) { // 检查当前节点的左右子节点是否为目标节点 if ((current.left ! null current.left.value nums) || (current.right ! null current.right.value nums)) { return current; // 找到父节点 } // 根据值的大小决定遍历方向 if (nums current.value) { current current.left; } else { current current.right; } } return null; // 未找到父节点 } /** * 广度优先遍历层序遍历 * 使用队列实现按层从上到下、从左到右输出 */ public void levelOrder() { QueueNode queue new LinkedListNode(); queue.add(root); while(queue.isEmpty() false) { Node currentNode queue.remove(); // 取出队首节点 System.out.println(currentNode.value); // 将左右子节点加入队列 if(currentNode.left ! null) { queue.add(currentNode.left); } if(currentNode.right ! null) { queue.add(currentNode.right); } } } /** * 深度优先遍历 - 先序遍历根-左-右 * param currentNode 当前遍历的节点 */ public void beforeOrder(Node currentNode) { if(currentNode null) { return; } System.out.println(currentNode.value); // 访问根节点 beforeOrder(currentNode.left); // 递归遍历左子树 beforeOrder(currentNode.right); // 递归遍历右子树 } /** * 深度优先遍历 - 中序遍历左-根-右 * 对于二叉搜索树中序遍历结果为升序序列 * param currentNode 当前遍历的节点 */ public void inOrder(Node currentNode) { if(currentNode null) { return; } // 注意这里应该调用 inOrder 而不是 beforeOrder inOrder(currentNode.left); // 递归遍历左子树 System.out.println(currentNode.value); // 访问根节点 inOrder(currentNode.right); // 递归遍历右子树 } /** * 深度优先遍历 - 后序遍历左-右-根 * param currentNode 当前遍历的节点 */ public void afterOrder(Node currentNode) { if(currentNode null) { return; } // 注意这里应该调用 afterOrder 而不是 beforeOrder afterOrder(currentNode.left); // 递归遍历左子树 afterOrder(currentNode.right); // 递归遍历右子树 System.out.println(currentNode.value); // 访问根节点 } /** * 删除指定值的节点 * 分三种情况处理 * 1. 叶子节点无子节点直接删除 * 2. 只有一个子节点用子节点替换 * 3. 有两个子节点用右子树的最小节点替换 * param num 要删除的值 */ public void delete(int num) { Node target search(num); // 查找要删除的节点 if(target null) { System.out.println(NotFound); return; } Node parent searchParent(num); // 查找父节点 // 情况1删除叶子节点没有子节点 if(target.left null target.right null) { if(parent null) { // 如果删除的是根节点 root null; return; } // 判断目标节点是父节点的左子节点还是右子节点 if(parent.left ! null parent.left.value num) { parent.left null; } else { parent.right null; } } // 情况3删除有两个子节点的节点 else if(target.left ! null target.right ! null) { // 找到右子树中的最小节点即中序后继 Node index target.right; while(index.left ! null) { index index.left; } int min index.value; // 保存最小值 delete(min); // 递归删除这个最小节点 target.value min; // 用最小值替换目标节点的值 } // 情况2删除只有一个子节点的节点 else { if(parent null) { // 如果删除的是根节点 if(target.left ! null) { root target.left; } else { root target.right; } return; } // 判断目标节点是父节点的左子节点还是右子节点 if(parent.left ! null parent.left.value num) { if(target.left ! null) { parent.left target.left; } else { parent.left target.right; } } else { if(target.left ! null) { parent.right target.left; } else { parent.right target.right; } } } } /** * 重写toString方法返回树的根节点信息 */ Override public String toString() { return YouxvTree [root root ]; } }package tree; public class Node { int value; Node left; Node right; public Node(int num) { valuenum; } public String toString() { return YouxvTree [value value , left left , right right ]; } }