保养车哪个网站做的好国内网页设计网站

保养车哪个网站做的好,国内网页设计网站,装修网站建设摘要,ps制作网页导航条有序二叉树#xff08;二叉排序树#xff09;是数据结构中极具实用性的树形结构#xff0c;其「左小右大」的核心特性让插入、查找、遍历操作具备高效性。一、二叉排序树的定义二叉排序树的核心规则#xff1a;任意节点的左子树中#xff0c;所有节点值 小于 该节点值二叉排序树是数据结构中极具实用性的树形结构其「左小右大」的核心特性让插入、查找、遍历操作具备高效性。一、二叉排序树的定义二叉排序树的核心规则任意节点的左子树中所有节点值小于该节点值任意节点的右子树中所有节点值大于该节点值左右子树也必须是二叉排序树。二、节点类的构建package com.qcby.Tree; /** * 二叉树节点类 * 存储节点数据、左子节点、右子节点引用 */ public class TreeNode { public TreeNode lChild; // 左子节点 public TreeNode rChild; // 右子节点 public Integer data; // 节点存储的数据 // 构造方法初始化节点数据 public TreeNode(Integer data) { this.data data; } }三、二叉排序树的构建3.1 插入逻辑拆解若树为空根节点为 null新节点直接作为根节点若树非空从根节点开始循环遍历新节点值 当前节点值向右子树查找直到右子节点为 null插入新节点新节点值 ≤ 当前节点值向左子树查找直到左子节点为 null插入新节点。3.2 构建代码实现package com.qcby.Tree; import java.util.LinkedList; /** * 有序二叉树核心类 * 包含构建、遍历、查找核心方法 */ public class BinaryTree { // 二叉树根节点初始为空 TreeNode root; /** * 插入节点构建有序二叉树 * param value 要插入的节点值 */ public void insert(Integer value) { // 1. 创建新节点 TreeNode newNode new TreeNode(value); // 2. 空树直接设为根节点 if (root null) { root newNode; return; } // 3. 非空树从根节点开始找插入位置 TreeNode current root; while (true) { // 新节点值大于当前节点 → 走右子树 if (newNode.data current.data) { if (current.rChild null) { current.rChild newNode; return; } current current.rChild; } else { // 新节点值小于等于当前节点 → 走左子树 if (current.lChild null) { current.lChild newNode; return; } current current.lChild; } } } // 后续遍历、查找方法将在此类中补充 }四、二叉排序树的遍历算法遍历是访问二叉树所有节点的方式分为深度优先遍历先序、中序、后序和广度优先遍历层次遍历两种方式适用于不同场景。4.1 深度优先遍历递归实现深度优先遍历的核心是「先深入子树再回溯」通过递归实现极为简洁三种遍历的区别仅在于访问根节点的时机。4.1.1 先序遍历根 → 左 → 右逻辑先访问当前节点 → 递归遍历左子树 → 递归遍历右子树特点先拿到根节点适合快速获取树的「根优先」结构。/** * 先序遍历深度优先 * param node 遍历的起始节点通常传根节点 */ public void preOrder(TreeNode node) { // 递归终止条件节点为空 if (node null) { return; } System.out.print(node.data ); // 1. 访问当前节点 preOrder(node.lChild); // 2. 遍历左子树 preOrder(node.rChild); // 3. 遍历右子树 }4.1.2 中序遍历左 → 根 → 右逻辑递归遍历左子树 → 访问当前节点 → 递归遍历右子树特点有序二叉树的中序遍历结果为升序序列是有序二叉树最常用的遍历方式。/** * 中序遍历深度优先 * param node 遍历的起始节点通常传根节点 */ public void inOrder(TreeNode node) { if (node null) { return; } inOrder(node.lChild); // 1. 遍历左子树 System.out.print(node.data ); // 2. 访问当前节点 inOrder(node.rChild); // 3. 遍历右子树 }4.1.3 后序遍历左 → 右 → 根逻辑递归遍历左子树 → 递归遍历右子树 → 访问当前节点特点最后访问根节点适合「先处理子节点再处理父节点」的场景如删除节点。/** * 后序遍历深度优先 * param node 遍历的起始节点通常传根节点 */ public void postOrder(TreeNode node) { if (node null) { return; } postOrder(node.lChild); // 1. 遍历左子树 postOrder(node.rChild); // 2. 遍历右子树 System.out.print(node.data ); // 3. 访问当前节点 }4.2 广度优先遍历层次遍历广度优先遍历层次遍历的核心是「按层访问」从根节点开始依次访问每一层的所有节点依赖队列实现先进先出特性。4.2.1 层次遍历逻辑创建队列将根节点入队循环取出队首节点访问该节点将该节点的左、右子节点依次入队若存在直到队列为空遍历完成。4.2.2 层次遍历代码实现/** * 层次遍历广度优先 * param node 遍历的起始节点通常传根节点 */ public void levelOrder(TreeNode node) { if (node null) { return; } // 1. 创建队列存储待访问的节点 LinkedListTreeNode queue new LinkedList(); queue.add(node); // 2. 循环处理队列中的节点 while (!queue.isEmpty()) { // 取出队首节点并访问 TreeNode current queue.pop(); System.out.print(current.data ); // 左子节点入队若存在 if (current.lChild ! null) { queue.add(current.lChild); } // 右子节点入队若存在 if (current.rChild ! null) { queue.add(current.rChild); } } }五、二叉排序树的查找算法基于有序二叉树「左小右大」的特性查找节点的效率远高于无序二叉树理想时间复杂度 O (logn)。5.1 迭代法查找循环实现5.1.1 查找逻辑拆解从根节点开始遍历若当前节点值等于目标值返回该节点若目标值 当前节点值向左子树继续查找若目标值 当前节点值向右子树继续查找若遍历到空节点仍未找到返回 null。5.1.2 迭代法代码实现/** * 迭代法查找指定值的节点 * param root 查找的起始节点通常传根节点 * param data 要查找的节点值 * return 找到的节点未找到返回null */ public TreeNode find(TreeNode root, Integer data) { TreeNode current root; // 循环查找直到节点为空或找到目标 while (current ! null) { if (current.data.equals(data)) { return current; // 找到目标节点返回 } // 目标值更小 → 走左子树 if (data current.data) { current current.lChild; } else { // 目标值更大 → 走右子树 current current.rChild; } } return null; // 未找到 }5.2 递归法查找5.2.1 查找逻辑拆解递归终止条件当前节点为 null未找到或当前节点值等于目标值找到若目标值 当前节点值递归查找左子树若目标值 当前节点值递归查找右子树。5.2.2 递归法代码实现/** * 递归法查找指定值的节点 * param root 查找的起始节点通常传根节点 * param data 要查找的节点值 * return 找到的节点未找到返回null */ public TreeNode find(TreeNode root,Integer data){ TreeNode current root; // 递归终止条件1节点为空未找到 if(current.datanull){ return null; } // 递归终止条件2找到目标节点 if(current.datadata){ return current; } // 目标值更小 → 递归查找左子树 if(current.data data){ return find(current.rChild,data); } else{ // 目标值更大 → 递归查找右子树 return find(current.lChild,data); } }六、完整测试验证所有功能编写测试类验证二叉树的构建、遍历、查找功能是否正常package com.qcby.Tree; /** * 有序二叉树测试类 */ public class Test { public static void main(String[] args) { // 1.创建二叉树实例 BinaryTree tree new BinaryTree(); // 2. 插入节点构建有序二叉树 bt.create(5); bt.create(3); bt.create(7); bt.create(0); bt.create(4); bt.create(6); bt.create(9); // 3. 测试深度优先遍历 System.out.println( 深度优先遍历 ); System.out.print(先序遍历); System.out.println(tree.beforeOrder(tree.root)); // 输出5 3 0 4 7 6 9 System.out.print(中序遍历); System.out.println(tree.inOrder(tree.root)); // 输出0 3 4 5 6 7 9升序 System.out.print(后序遍历); System.out.println(tree.afterOrder(tree.root)); // 输出0 4 3 6 9 7 5 // 4. 测试广度优先遍历 System.out.println(\n 广度优先遍历 ); System.out.print(层次遍历); System.out.println(tree.levelOrder(tree.root)); // 输出5 3 7 0 4 6 9 // 5. 测试节点查找 System.out.println(\n 节点查找 ); TreeNode target tree.find(tree.root, 9); if (target ! null) { System.out.println(找到节点 target.data); // 输出找到节点9 } else { System.out.println(未找到指定节点); } TreeNode notFound tree.find(tree.root, 10); if (notFound null) { System.out.println(未找到节点10); // 输出未找到节点10 } } }