网站 分站福州网站建设方案优化

网站 分站,福州网站建设方案优化,厦网站建设培训,凡科网免费建站官网在数据结构的学习中#xff0c;二叉排序树#xff08;Binary Sort Tree#xff0c;BST#xff09;是连接 “树结构” 与 “高效数据操作” 的关键桥梁。它凭借 “左子树节点值小于父节点、右子树节点值大于父节点” 的核心特性#xff0c;实现了查找、插入操作的高效性二叉排序树Binary Sort TreeBST是连接 “树结构” 与 “高效数据操作” 的关键桥梁。它凭借 “左子树节点值小于父节点、右子树节点值大于父节点” 的核心特性实现了查找、插入操作的高效性在信息检索、动态集合维护等场景中应用广泛。本文将聚焦二叉排序树的两大核心能力 ——构建新增节点与遍历查找衍生操作通过清晰的逻辑拆解、代码实现与原理分析帮助你轻松掌握这一基础数据结构难度评级为两颗星适合入门级学习者深入理解。一、二叉排序树的基础定义1.1 核心特性二叉排序树要么是一棵空树要么是满足以下条件的非空二叉树若左子树非空则左子树上所有节点的关键字值均小于根节点的关键字值若右子树非空则右子树上所有节点的关键字值均大于根节点的关键字值左、右子树本身也分别是一棵二叉排序树递归特性。关键结论对二叉排序树进行中序遍历会得到一个严格递增的有序序列这是二叉排序树的核心价值所在。1.2 节点类设计在 Java 中我们通过类来定义二叉排序树的节点每个节点包含三个核心属性数据值、左子节点引用、右子节点引用。/** * 二叉排序树节点类 */ class BSTNode { int val; // 节点存储的数据 BSTNode left; // 左子节点引用 BSTNode right; // 右子节点引用 // 构造方法 public BSTNode(int val) { this.val val; this.left null; this.right null; } }二、二叉排序树的构建新增节点二叉排序树的构建是一个动态插入的过程树的结构由依次插入的节点决定。核心逻辑是遵循 “左小右大” 原则为新节点找到合适的空位置。2.1 核心插入逻辑空树判断如果当前树为空根节点为null则新节点直接作为根节点。循环查找位置如果树非空从根节点开始遍历若新节点值小于当前节点值向左子树移动若左子节点为null则插入此处若新节点值大于当前节点值向右子树移动若右子节点为null则插入此处若新节点值等于当前节点值直接跳过二叉排序树默认不存储重复值。引用更新插入新节点时只需修改父节点的左 / 右子节点引用即可无需移动已有节点。2.2 非递归实现推荐入门非递归实现通过循环遍历树的分支避免了递归的栈开销且更易理解引用的传递过程。/** * 二叉排序树操作类 */ public class BinarySortTree { private BSTNode root; // 根节点 // 构造方法初始化空树 public BinarySortTree() { this.root null; } /** * 插入节点非递归实现 * param val 要插入的数据值 */ public void insert(int val) { BSTNode newNode new BSTNode(val); // 情况1树为空新节点作为根节点 if (root null) { root newNode; return; } // 情况2树非空查找插入位置 BSTNode curr root; // 当前遍历节点 BSTNode parent null; // 记录当前节点的父节点 while (curr ! null) { parent curr; if (val curr.val) { // 新值小向左子树找 curr curr.left; } else if (val curr.val) { // 新值大向右子树找 curr curr.right; } else { // 存在重复值直接返回 return; } } // 找到空位置插入新节点 if (val parent.val) { parent.left newNode; } else { parent.right newNode; } } }2.3 递归实现利用二叉排序树的递归特性可简化插入代码逻辑与非递归实现完全一致。/** * 递归插入节点 * param node 当前遍历的节点初始为root * param val 要插入的值 * return 插入后的当前节点 */ private BSTNode insertRecursive(BSTNode node, int val) { // 递归终止条件找到空位置返回新节点 if (node null) { return new BSTNode(val); } // 递归查找左/右子树 if (val node.val) { node.left insertRecursive(node.left, val); } else if (val node.val) { node.right insertRecursive(node.right, val); } // 重复值直接返回原节点 return node; } // 对外暴露的递归插入方法 public void insertByRecursive(int val) { root insertRecursive(root, val); }2.4 完整构建示例通过向空树中依次插入数组元素即可构建一棵完整的二叉排序树。// 测试构建二叉排序树 public static void main(String[] args) { int[] arr {5, 3, 7, 2, 4, 6, 8}; BinarySortTree bst new BinarySortTree(); for (int num : arr) { bst.insert(num); // 调用非递归插入 // 或调用递归插入bst.insertByRecursive(num); } }三、二叉排序树的遍历Java 实现遍历是访问树中所有节点的过程二叉排序树的遍历分为深度优先遍历DFS和广度优先遍历BFS两大类其中深度优先遍历包含前序、中序、后序三种方式。我们在BinarySortTree类中添加以下遍历方法。3.1 深度优先遍历DFS深度优先遍历的核心是优先访问子树的深度可通过递归或栈非递归实现三种方式的区别在于根节点的访问时机。3.1.1 前序遍历根 → 左子树 → 右子树特点先访问根节点再递归遍历左子树最后递归遍历右子树。应用场景复制树结构、获取树的拓扑结构。遍历结果以上文树为例5 3 2 4 7 6 8递归实现/** * 前序遍历递归 * param node 当前节点 */ public void preOrder(BSTNode node) { if (node null) { return; } System.out.print(node.val ); // 1. 访问根节点 preOrder(node.left); // 2. 遍历左子树 preOrder(node.right); // 3. 遍历右子树 }非递归实现栈Java 中可使用java.util.Stack类模拟栈结构注意右子节点先入栈栈先进后出。import java.util.Stack; /** * 前序遍历非递归-栈实现 */ public void preOrderNonRecursive() { if (root null) { return; } StackBSTNode stack new Stack(); stack.push(root); while (!stack.isEmpty()) { BSTNode curr stack.pop(); System.out.print(curr.val ); // 访问根节点 // 右子节点先入栈左子节点后入栈 if (curr.right ! null) { stack.push(curr.right); } if (curr.left ! null) { stack.push(curr.left); } } }3.1.2 中序遍历左子树 → 根 → 右子树特点先递归遍历左子树再访问根节点最后递归遍历右子树。核心优势遍历结果为严格递增的有序序列二叉排序树的核心特性。应用场景获取有序数据、验证二叉排序树的合法性。遍历结果2 3 4 5 6 7 8递归实现/** * 中序遍历递归 * param node 当前节点 */ public void inOrder(BSTNode node) { if (node null) { return; } inOrder(node.left); // 1. 遍历左子树 System.out.print(node.val ); // 2. 访问根节点 inOrder(node.right); // 3. 遍历右子树 }非递归实现栈/** * 中序遍历非递归-栈实现 */ public void inOrderNonRecursive() { if (root null) { return; } StackBSTNode stack new Stack(); BSTNode curr root; while (curr ! null || !stack.isEmpty()) { // 先遍历所有左子节点压入栈 while (curr ! null) { stack.push(curr); curr curr.left; } // 弹出栈顶节点访问 curr stack.pop(); System.out.print(curr.val ); // 遍历右子树 curr curr.right; } }3.1.3 后序遍历左子树 → 右子树 → 根特点先递归遍历左子树再递归遍历右子树最后访问根节点。应用场景删除树结构、计算子树的节点数或深度。遍历结果2 4 3 6 8 7 5递归实现/** * 后序遍历递归 * param node 当前节点 */ public void postOrder(BSTNode node) { if (node null) { return; } postOrder(node.left); // 1. 遍历左子树 postOrder(node.right); // 2. 遍历右子树 System.out.print(node.val ); // 3. 访问根节点 }3.2 广度优先遍历BFS层次遍历层次遍历的核心是按层级访问节点先访问根节点第 1 层再访问第 2 层以此类推。Java 中使用java.util.Queue队列先进先出实现。应用场景按层级处理任务、计算树的宽度。遍历结果5 3 7 2 4 6 8import java.util.LinkedList; import java.util.Queue; /** * 层次遍历队列实现 */ public void levelOrder() { if (root null) { return; } QueueBSTNode queue new LinkedList(); queue.offer(root); // 根节点入队 while (!queue.isEmpty()) { BSTNode curr queue.poll(); // 出队并访问 System.out.print(curr.val ); // 左子节点先入队 if (curr.left ! null) { queue.offer(curr.left); } // 右子节点后入队 if (curr.right ! null) { queue.offer(curr.right); } } }四、完整测试代码将所有方法整合后编写测试类验证功能import java.util.LinkedList; import java.util.Queue; import java.util.Stack; // 节点类 class BSTNode { int val; BSTNode left; BSTNode right; public BSTNode(int val) { this.val val; } } // 二叉排序树操作类 public class BinarySortTree { private BSTNode root; public BinarySortTree() { this.root null; } // 非递归插入 public void insert(int val) { BSTNode newNode new BSTNode(val); if (root null) { root newNode; return; } BSTNode curr root; BSTNode parent null; while (curr ! null) { parent curr; if (val curr.val) { curr curr.left; } else if (val curr.val) { curr curr.right; } else { return; } } if (val parent.val) { parent.left newNode; } else { parent.right newNode; } } // 递归插入辅助方法 private BSTNode insertRecursive(BSTNode node, int val) { if (node null) { return new BSTNode(val); } if (val node.val) { node.left insertRecursive(node.left, val); } else if (val node.val) { node.right insertRecursive(node.right, val); } return node; } // 递归插入对外方法 public void insertByRecursive(int val) { root insertRecursive(root, val); } // 前序递归遍历 public void preOrder(BSTNode node) { if (node null) return; System.out.print(node.val ); preOrder(node.left); preOrder(node.right); } // 中序递归遍历 public void inOrder(BSTNode node) { if (node null) return; inOrder(node.left); System.out.print(node.val ); inOrder(node.right); } // 后序递归遍历 public void postOrder(BSTNode node) { if (node null) return; postOrder(node.left); postOrder(node.right); System.out.print(node.val ); } // 前序非递归遍历 public void preOrderNonRecursive() { if (root null) return; StackBSTNode stack new Stack(); stack.push(root); while (!stack.isEmpty()) { BSTNode curr stack.pop(); System.out.print(curr.val ); if (curr.right ! null) stack.push(curr.right); if (curr.left ! null) stack.push(curr.left); } } // 中序非递归遍历 public void inOrderNonRecursive() { if (root null) return; StackBSTNode stack new Stack(); BSTNode curr root; while (curr ! null || !stack.isEmpty()) { while (curr ! null) { stack.push(curr); curr curr.left; } curr stack.pop(); System.out.print(curr.val ); curr curr.right; } } // 层次遍历 public void levelOrder() { if (root null) return; QueueBSTNode queue new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { BSTNode curr queue.poll(); System.out.print(curr.val ); if (curr.left ! null) queue.offer(curr.left); if (curr.right ! null) queue.offer(curr.right); } } // 获取根节点 public BSTNode getRoot() { return root; } // 测试主方法 public static void main(String[] args) { int[] arr {5, 3, 7, 2, 4, 6, 8}; BinarySortTree bst new BinarySortTree(); for (int num : arr) { bst.insert(num); } System.out.println(前序递归遍历); bst.preOrder(bst.getRoot()); // 5 3 2 4 7 6 8 System.out.println(\n中序递归遍历有序); bst.inOrder(bst.getRoot()); // 2 3 4 5 6 7 8 System.out.println(\n层次遍历); bst.levelOrder(); // 5 3 7 2 4 6 8 } }