尧图网站建设 
使用 JavaScript 构建平衡二叉搜索树从 buildTree 到 rebalance 的完整实践指南【免费下载链接】curriculumThe open curriculum for learning web development项目地址: https://gitcode.com/GitHub_Trending/cu/curriculum导读本篇指南围绕 JavaScript 课程中「计算机科学」章节的平衡二叉搜索树Balanced Binary Search Tree, BST项目展开目标是从零实现一个功能完备的平衡 BST包括节点与树的类/工厂、从无序数组构建平衡树的buildTree()、查找、插入、删除、四种遍历、高度/深度计算、平衡性检查与再平衡最后用一个驱动脚本串联验证全部功能。读完本篇你将掌握 BST 的递归构建原理、广度优先/深度优先遍历的实现技巧、删除节点的三种经典情形以及如何通过 Big O 理解这些操作在O(log n)时间内的运行效率。前置知识为什么需要平衡二叉搜索树在动手编码之前先回顾 BST 的基本模型将一组数据组织成由节点组成的树每个节点最多有两个子节点且左子树上所有节点的值都小于该节点右子树上所有节点的值都大于该节点。树以「根节点」root node开始没有任何子节点的节点称为「叶节点」leaf node。这些概念在前置课程 常见数据结构与算法 中已经介绍过其中还涵盖广度优先搜索BFS与深度优先搜索DFS两种遍历思路。BST 的核心价值在于查找lookup、插入insertion与删除deletion都能获得极快的速度。根据 时间复杂度基础 中关于 Big O 的讲解O(log N)对数复杂度意味着数据量翻倍时只需增加一步操作——这是相对于数组线性扫描的巨大性能优势。但这一优势有一个前提树必须是平衡的。如果树退化成一条单链例如按升序依次插入节点查找复杂度就会退化为O(N)。因此本项目的首要任务就是通过「从有序数组递归建树」的方式直接构造出一棵平衡树。另外建树与遍历都高度依赖递归而 递归方法 一课强调的核心是「分而治之」Divide and Conquer把大问题拆成同类型的更小子问题直到子问题简单到可以直接求解再把子问题的解逐层合并回原问题。buildTree()正是这一思想的典型应用你可以在上一个项目 递归项目斐波那契与归并排序 中已经体会过同样的模式。项目目标概览本项目的要求来自 平衡二叉搜索树项目最终交付物包括Node类/工厂存储数据以及左右子节点引用Tree类/工厂接收数组并暴露root属性buildTree(array)排序去重后构建平衡树并返回根节点includes(value)/insert(value)/deleteItem(value)核心增删查操作levelOrderForEach(callback)广度优先层序遍历inOrderForEach/preOrderForEach/postOrderForEach三种深度优先遍历height(value)/depth(value)节点高度与深度isBalanced()/rebalance()平衡性检查与再平衡一个完整的驱动脚本串联验证所有功能。原项目特别强调不要使用重复值因为重复值会让树更难平衡插入前必须先查重或在构建阶段去重。第一步Node 类/工厂节点是树的原子单元。每个Node需要三个属性存储的数据data以及指向左右孩子的left与right。使用 ES6 类语法class Node { constructor(data) { this.data data; this.left null; this.right null; } }也可以使用工厂函数const Node (data) ({ data, left: null, right: null, });两种方式等价选择哪种取决于你对 ES6 模块与组织代码 的熟练程度。项目在 链表项目 中已经演示过「类/工厂二选一」的模式这里保持一致即可。第二步buildTree 的核心算法Tree类在初始化时接收一个数组root属性由buildTree()的返回值赋初值class Tree { constructor(array) { this.root buildTree(array); } }排序与去重buildTree()接收的数组是乱序且可能含重复的例如原文档给出的用例[1, 7, 4, 23, 8, 9, 4, 3, 5, 7, 9, 67, 6345, 324]处理顺序应为用[...new Set(array)]去重用.sort((a, b) a - b)按数值升序排序注意默认sort()按字符串排序必须传入比较函数。function buildTree(array) { const sorted [...new Set(array)].sort((a, b) a - b); // 递归构建…… }递归取中点从有序数组构建平衡树的最经典方法是取数组的中间元素作为根节点左半部分递归构建左子树右半部分递归构建右子树。这样构造出的树天然满足「左右子树高度差不超过 1」的平衡性质因为每一层都把剩余元素对半分。function buildTree(array) { const sorted [...new Set(array)].sort((a, b) a - b); const build (arr) { if (arr.length 0) return null; const mid Math.floor(arr.length / 2); const node new Node(arr[mid]); node.left build(arr.slice(0, mid)); node.right build(arr.slice(mid 1)); return node; }; return build(sorted); }递归的基线条件是数组为空时返回null即叶节点的子节点。每次递归取中间下标Math.floor(arr.length / 2)保证左右两部分元素数量相差不超过 1从而维持平衡。为了让buildTree只服务于内部初始化可以用类语法中的私有字段#前缀或工厂函数的闭包将其隐藏只暴露root。用 prettyPrint 可视化你的树为了验证建树结果原项目提供了一个现成的prettyPrint()函数它用递归 前缀字符在控制台打印树形结构。该函数期望接收树的根节点作为node参数const prettyPrint (node, prefix , isLeft true) { if (node null || node undefined) { return; } prettyPrint(node.right, ${prefix}${isLeft ? │ : }, false); console.log(${prefix}${isLeft ? └── : ┌── }${node.data}); prettyPrint(node.left, ${prefix}${isLeft ? : │ }, true); };其原理是先递归打印右子树、再打印当前节点、最后打印左子树一种中序变体布局通过prefix传递层级缩进用└──/┌──/│拼出树形连线。每次建树后调用prettyPrint(tree.root)即可直观检查树的形态。第三步查找与插入includes(value)沿路径二分搜索BST 的查找本质是沿着根到叶的一条路径走到底当前节点值等于目标则命中目标小于当前值则去左子树大于则去右子树走到null说明不存在。includes(value, node this.root) { if (node null) return false; if (value node.data) return true; return value node.data ? this.includes(value, node.left) : this.includes(value, node.right); }由于每深入一层就排除一半的树查找复杂度为O(log n)平衡状态下。insert(value)保持二叉搜索性质插入同样利用递归定位从根开始目标值小于当前节点就去左子树找空位大于就去右子树找空位遇到null就在该位置挂上新节点。关键约束是保持二叉搜索性质——每个节点左侧的所有值必须更小右侧的所有值必须更大。若插入的值已存在函数应直接返回、不做任何操作。insert(value, node this.root) { if (node null) return new Node(value); if (value node.data) { node.left this.insert(value, node.left); } else if (value node.data) { node.right this.insert(value, node.right); } // value node.data 时什么都不做避免重复值 return node; }这里要注意插入操作绝不能依赖最初用于建树的原始数组。原项目专门强调这一点如果通过操作数组来「假装」插入就丢失了 BST 的O(log n)效率——数组的插入/删除是O(n)的。正确做法是遍历树、操作节点及其连接只有这样才能兑现二叉搜索树的性能优势。第四步deleteItem 的三种情形删除是 BST 中最具挑战性的操作取决于目标节点有多少个孩子情形一叶节点无孩子。直接置空父节点对应的引用即可。情形二只有一个孩子。用其唯一的孩子顶替被删除节点的位置。情形三有两个孩子。这是经典难点。正确策略是找到右子树中的最小节点中序后继或左子树中的最大节点中序前驱用它的值覆盖待删除节点然后递归地删除那个被借用的节点它必然至多只有一个孩子从而退化到前两种情形。deleteItem(value, node this.root) { if (node null) return null; if (value node.data) { node.left this.deleteItem(value, node.left); } else if (value node.data) { node.right this.deleteItem(value, node.right); } else { // 情形一叶节点 if (node.left null node.right null) return null; // 情形二只有一个孩子 if (node.left null) return node.right; if (node.right null) return node.left; // 情形三两个孩子——找右子树最小节点 let successor node.right; while (successor.left ! null) { successor successor.left; } node.data successor.data; node.right this.deleteItem(successor.data, node.right); } return node; }如果给定的值不在树中递归会自然走到底部返回null链最终整棵树不变符合「什么都不做」的要求。第五步四种遍历方式广度优先levelOrderForEach层序遍历按「从上到下、从左到右」逐层访问节点实现方式是用一个数组充当队列出队当前节点并调用回调同时把它的左右孩子依次入队。原项目提示使用数组作为队列来跟踪尚未遍历的孩子节点并推荐同时尝试迭代与递归两种实现。迭代版levelOrderForEach(callback) { if (typeof callback ! function) { throw new Error(Callback is required); } const queue [this.root]; while (queue.length 0) { const node queue.shift(); if (node null) continue; callback(node.data); // 传入的是值而不是节点 queue.push(node.left, node.right); } }注意回调接收的是每个节点的值而非节点对象语义上与Array.prototype.forEach()一致如果未提供回调必须throw new Error(...)报告缺少回调。递归版的思想是记录层级维护一个保存每层节点的数组逐层展开。队列数据结构的概念在前置课 常见数据结构与算法 中与栈、链表一起介绍过——层序遍历正是队列的经典应用场景。深度优先inOrder / preOrder / postOrder三种深度优先遍历的区别只在于访问当前节点的时机相对于递归左右子树的顺序遍历方式访问顺序特点preOrderForEach前序根 → 左 → 右根节点最先被访问inOrderForEach中序左 → 根 → 右对 BST 输出升序序列postOrderForEach后序左 → 右 → 根根节点最后被访问inOrderForEach(callback, node this.root) { if (typeof callback ! function) { throw new Error(Callback is required); } if (node null) return; this.inOrderForEach(callback, node.left); callback(node.data); this.inOrderForEach(callback, node.right); } preOrderForEach(callback, node this.root) { if (typeof callback ! function) { throw new Error(Callback is required); } if (node null) return; callback(node.data); this.preOrderForEach(callback, node.left); this.preOrderForEach(callback, node.right); } postOrderForEach(callback, node this.root) { if (typeof callback ! function) { throw new Error(Callback is required); } if (node null) return; this.postOrderForEach(callback, node.left); this.postOrderForEach(callback, node.right); callback(node.data); }三种遍历都与levelOrderForEach一样在缺少回调参数时抛出Error。中序遍历的特殊价值在于对一棵 BST 做中序遍历得到的一定是递增的有序序列——这一性质稍后在rebalance()中会派上大用场。第六步height 与 depth高度height的定义从该节点到某个叶节点的最长路径上的边数。叶节点的高度为 0。递归实现为「左右子树高度取较大者加 1」height(value) { const node this.#findNode(value); if (node undefined) return undefined; const getHeight (current) { if (current null) return -1; // 空子树贡献 -1使叶节点高度为 0 return 1 Math.max(getHeight(current.left), getHeight(current.right)); }; return getHeight(node); }这里用内部辅助函数#findNode(value)定位节点若值不存在原项目要求返回undefined。空子树返回-1是常见技巧1 max(-1, -1) 0恰好使叶节点高度为 0。深度depth的定义从该节点到根节点的路径上的边数根节点的深度为 0。实现方式是从根出发沿查找路径计数depth(value) { let current this.root; let edges 0; while (current ! null) { if (value current.data) return edges; current value current.data ? current.left : current.right; edges 1; } return undefined; // 未找到 }高度是从节点向下看到叶子的最长距离深度是从节点向上看到根的距离两者方向相反注意区分。第七步isBalanced 与 rebalanceisBalanced检查每一个节点一棵树是平衡的当且仅当对于树中的每个节点其左右子树的高度差不超过 1并且左右子树自身也平衡。原项目专门给出一个「陷阱提示」只比较根节点左右子树的高度差是不够的——某个深层的节点可能早已失衡。因此必须递归检查所有节点isBalanced(node this.root) { if (node null) return true; const leftHeight this.#getHeight(node.left); const rightHeight this.#getHeight(node.right); if (Math.abs(leftHeight - rightHeight) 1) return false; return this.isBalanced(node.left) this.isBalanced(node.right); }每次递归都要重新计算左右子树高度O(n)整体检查为O(n log n)如果想优化到O(n)可以让递归同时返回「是否平衡」与「子树高度」两个信息自底向上一次遍历完成但先写出正确版本更重要。rebalance借遍历之力重建平衡rebalance()的思路非常优雅先用中序遍历把失衡的树拍平成有序数组再把这个有序数组交给buildTree()重建一棵平衡树。这正是中序遍历对 BST 输出有序序列这一性质的直接应用rebalance() { const values []; this.inOrderForEach((value) values.push(value)); this.root buildTree(values); }由于中序遍历结果天然有序buildTree()内部的「排序去重」步骤对已是升序的数组而言只是幂等操作取中点递归建树后即可恢复平衡。第八步驱动脚本——把一切串联起来原项目要求编写一个驱动脚本按以下流程端到端验证整棵树的正确性从一组随机数每个元素小于 100创建 BST可用一个每次调用都返回随机数组的函数来生成调用isBalanced()确认树是平衡的分别以层序、前序、中序、后序打印所有元素插入几个大于 100的数值使树失衡调用isBalanced()确认树确实失衡调用rebalance()重新平衡再次调用isBalanced()确认已恢复平衡再次以层序、前序、中序、后序打印所有元素。一个参考骨架const randomArray () Array.from({ length: 15 }, () Math.floor(Math.random() * 100)); const tree new Tree(randomArray()); console.log(初始是否平衡:, tree.isBalanced()); // true tree.levelOrderForEach((v) console.log(level:, v)); tree.preOrderForEach((v) console.log(pre:, v)); tree.postOrderForEach((v) console.log(post:, v)); tree.inOrderForEach((v) console.log(in:, v)); [101, 205, 340, 450].forEach((n) tree.insert(n)); console.log(插入大数后是否平衡:, tree.isBalanced()); // false tree.rebalance(); console.log(再平衡后是否平衡:, tree.isBalanced()); // true tree.levelOrderForEach((v) console.log(level:, v)); tree.preOrderForEach((v) console.log(pre:, v)); tree.postOrderForEach((v) console.log(post:, v)); tree.inOrderForEach((v) console.log(in:, v));你可以配合prettyPrint(tree.root)观察失衡前后树形的变化连续插入[101, 205, 340, 450]会让树右侧越挂越长rebalance()之后再打印即可看到树重新变得「匀称」。若使用 ES6 模块import/export可参考 链表项目 中的提示使用 Node v22 及以上的 LTS 版本即可自动识别 ES6 模块并直接运行无需额外配置。复杂度总结与学习脉络把本次实现的所有操作放到 Big O 框架下审视操作平均时间复杂度说明buildTree(array)O(n log n)排序为主递归建树为O(n)includes(value)O(log n)每层排除一半节点insert(value)O(log n)沿查找路径走到空位deleteItem(value)O(log n)双孩子情形需查找中序后继四种遍历O(n)每个节点访问一次height/depthO(log n)高度需O(n)最坏取决于树形态isBalanced()O(n log n)朴素版每节点递归计算子树高度rebalance()O(n log n)中序收集 排序重建这些效率指标均建立在「树保持平衡」的前提上这正是本项目从建树到rebalance()始终围绕「平衡」这一主题的原因。本项目的直接前置是 常见数据结构与算法栈、队列、BFS/DFS、递归方法分而治之与 递归项目斐波那契与归并排序后续你将在 哈希映射项目 中对比另一种「平均O(1)」的查找结构并在 骑士旅行问题 中把 BFS 用于图的最短路径搜索。完成本项目后建议把每一段核心逻辑尤其是buildTree、deleteItem双孩子情形与isBalanced用prettyPrint反复可视化验证这是理解递归与树结构最有效的方式。【免费下载链接】curriculumThe open curriculum for learning web development项目地址: https://gitcode.com/GitHub_Trending/cu/curriculum创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 使用 JavaScript 构建平衡二叉搜索树：从 buildTree 到 rebalance 的完整实践指南
使用 JavaScript 构建平衡二叉搜索树从 buildTree 到 rebalance 的完整实践指南【免费下载链接】curriculumThe open curriculum for learning web development项目地址: https://gitcode.com/GitHub_Trending/cu/curriculum导读本篇指南围绕 JavaScript 课程中「计算机科学」章节的平衡二叉搜索树Balanced Binary Search Tree, BST项目展开目标是从零实现一个功能完备的平衡 BST包括节点与树的类/工厂、从无序数组构建平衡树的buildTree()、查找、插入、删除、四种遍历、高度/深度计算、平衡性检查与再平衡最后用一个驱动脚本串联验证全部功能。读完本篇你将掌握 BST 的递归构建原理、广度优先/深度优先遍历的实现技巧、删除节点的三种经典情形以及如何通过 Big O 理解这些操作在O(log n)时间内的运行效率。前置知识为什么需要平衡二叉搜索树在动手编码之前先回顾 BST 的基本模型将一组数据组织成由节点组成的树每个节点最多有两个子节点且左子树上所有节点的值都小于该节点右子树上所有节点的值都大于该节点。树以「根节点」root node开始没有任何子节点的节点称为「叶节点」leaf node。这些概念在前置课程 常见数据结构与算法 中已经介绍过其中还涵盖广度优先搜索BFS与深度优先搜索DFS两种遍历思路。BST 的核心价值在于查找lookup、插入insertion与删除deletion都能获得极快的速度。根据 时间复杂度基础 中关于 Big O 的讲解O(log N)对数复杂度意味着数据量翻倍时只需增加一步操作——这是相对于数组线性扫描的巨大性能优势。但这一优势有一个前提树必须是平衡的。如果树退化成一条单链例如按升序依次插入节点查找复杂度就会退化为O(N)。因此本项目的首要任务就是通过「从有序数组递归建树」的方式直接构造出一棵平衡树。另外建树与遍历都高度依赖递归而 递归方法 一课强调的核心是「分而治之」Divide and Conquer把大问题拆成同类型的更小子问题直到子问题简单到可以直接求解再把子问题的解逐层合并回原问题。buildTree()正是这一思想的典型应用你可以在上一个项目 递归项目斐波那契与归并排序 中已经体会过同样的模式。项目目标概览本项目的要求来自 平衡二叉搜索树项目最终交付物包括Node类/工厂存储数据以及左右子节点引用Tree类/工厂接收数组并暴露root属性buildTree(array)排序去重后构建平衡树并返回根节点includes(value)/insert(value)/deleteItem(value)核心增删查操作levelOrderForEach(callback)广度优先层序遍历inOrderForEach/preOrderForEach/postOrderForEach三种深度优先遍历height(value)/depth(value)节点高度与深度isBalanced()/rebalance()平衡性检查与再平衡一个完整的驱动脚本串联验证所有功能。原项目特别强调不要使用重复值因为重复值会让树更难平衡插入前必须先查重或在构建阶段去重。第一步Node 类/工厂节点是树的原子单元。每个Node需要三个属性存储的数据data以及指向左右孩子的left与right。使用 ES6 类语法class Node { constructor(data) { this.data data; this.left null; this.right null; } }也可以使用工厂函数const Node (data) ({ data, left: null, right: null, });两种方式等价选择哪种取决于你对 ES6 模块与组织代码 的熟练程度。项目在 链表项目 中已经演示过「类/工厂二选一」的模式这里保持一致即可。第二步buildTree 的核心算法Tree类在初始化时接收一个数组root属性由buildTree()的返回值赋初值class Tree { constructor(array) { this.root buildTree(array); } }排序与去重buildTree()接收的数组是乱序且可能含重复的例如原文档给出的用例[1, 7, 4, 23, 8, 9, 4, 3, 5, 7, 9, 67, 6345, 324]处理顺序应为用[...new Set(array)]去重用.sort((a, b) a - b)按数值升序排序注意默认sort()按字符串排序必须传入比较函数。function buildTree(array) { const sorted [...new Set(array)].sort((a, b) a - b); // 递归构建…… }递归取中点从有序数组构建平衡树的最经典方法是取数组的中间元素作为根节点左半部分递归构建左子树右半部分递归构建右子树。这样构造出的树天然满足「左右子树高度差不超过 1」的平衡性质因为每一层都把剩余元素对半分。function buildTree(array) { const sorted [...new Set(array)].sort((a, b) a - b); const build (arr) { if (arr.length 0) return null; const mid Math.floor(arr.length / 2); const node new Node(arr[mid]); node.left build(arr.slice(0, mid)); node.right build(arr.slice(mid 1)); return node; }; return build(sorted); }递归的基线条件是数组为空时返回null即叶节点的子节点。每次递归取中间下标Math.floor(arr.length / 2)保证左右两部分元素数量相差不超过 1从而维持平衡。为了让buildTree只服务于内部初始化可以用类语法中的私有字段#前缀或工厂函数的闭包将其隐藏只暴露root。用 prettyPrint 可视化你的树为了验证建树结果原项目提供了一个现成的prettyPrint()函数它用递归 前缀字符在控制台打印树形结构。该函数期望接收树的根节点作为node参数const prettyPrint (node, prefix , isLeft true) { if (node null || node undefined) { return; } prettyPrint(node.right, ${prefix}${isLeft ? │ : }, false); console.log(${prefix}${isLeft ? └── : ┌── }${node.data}); prettyPrint(node.left, ${prefix}${isLeft ? : │ }, true); };其原理是先递归打印右子树、再打印当前节点、最后打印左子树一种中序变体布局通过prefix传递层级缩进用└──/┌──/│拼出树形连线。每次建树后调用prettyPrint(tree.root)即可直观检查树的形态。第三步查找与插入includes(value)沿路径二分搜索BST 的查找本质是沿着根到叶的一条路径走到底当前节点值等于目标则命中目标小于当前值则去左子树大于则去右子树走到null说明不存在。includes(value, node this.root) { if (node null) return false; if (value node.data) return true; return value node.data ? this.includes(value, node.left) : this.includes(value, node.right); }由于每深入一层就排除一半的树查找复杂度为O(log n)平衡状态下。insert(value)保持二叉搜索性质插入同样利用递归定位从根开始目标值小于当前节点就去左子树找空位大于就去右子树找空位遇到null就在该位置挂上新节点。关键约束是保持二叉搜索性质——每个节点左侧的所有值必须更小右侧的所有值必须更大。若插入的值已存在函数应直接返回、不做任何操作。insert(value, node this.root) { if (node null) return new Node(value); if (value node.data) { node.left this.insert(value, node.left); } else if (value node.data) { node.right this.insert(value, node.right); } // value node.data 时什么都不做避免重复值 return node; }这里要注意插入操作绝不能依赖最初用于建树的原始数组。原项目专门强调这一点如果通过操作数组来「假装」插入就丢失了 BST 的O(log n)效率——数组的插入/删除是O(n)的。正确做法是遍历树、操作节点及其连接只有这样才能兑现二叉搜索树的性能优势。第四步deleteItem 的三种情形删除是 BST 中最具挑战性的操作取决于目标节点有多少个孩子情形一叶节点无孩子。直接置空父节点对应的引用即可。情形二只有一个孩子。用其唯一的孩子顶替被删除节点的位置。情形三有两个孩子。这是经典难点。正确策略是找到右子树中的最小节点中序后继或左子树中的最大节点中序前驱用它的值覆盖待删除节点然后递归地删除那个被借用的节点它必然至多只有一个孩子从而退化到前两种情形。deleteItem(value, node this.root) { if (node null) return null; if (value node.data) { node.left this.deleteItem(value, node.left); } else if (value node.data) { node.right this.deleteItem(value, node.right); } else { // 情形一叶节点 if (node.left null node.right null) return null; // 情形二只有一个孩子 if (node.left null) return node.right; if (node.right null) return node.left; // 情形三两个孩子——找右子树最小节点 let successor node.right; while (successor.left ! null) { successor successor.left; } node.data successor.data; node.right this.deleteItem(successor.data, node.right); } return node; }如果给定的值不在树中递归会自然走到底部返回null链最终整棵树不变符合「什么都不做」的要求。第五步四种遍历方式广度优先levelOrderForEach层序遍历按「从上到下、从左到右」逐层访问节点实现方式是用一个数组充当队列出队当前节点并调用回调同时把它的左右孩子依次入队。原项目提示使用数组作为队列来跟踪尚未遍历的孩子节点并推荐同时尝试迭代与递归两种实现。迭代版levelOrderForEach(callback) { if (typeof callback ! function) { throw new Error(Callback is required); } const queue [this.root]; while (queue.length 0) { const node queue.shift(); if (node null) continue; callback(node.data); // 传入的是值而不是节点 queue.push(node.left, node.right); } }注意回调接收的是每个节点的值而非节点对象语义上与Array.prototype.forEach()一致如果未提供回调必须throw new Error(...)报告缺少回调。递归版的思想是记录层级维护一个保存每层节点的数组逐层展开。队列数据结构的概念在前置课 常见数据结构与算法 中与栈、链表一起介绍过——层序遍历正是队列的经典应用场景。深度优先inOrder / preOrder / postOrder三种深度优先遍历的区别只在于访问当前节点的时机相对于递归左右子树的顺序遍历方式访问顺序特点preOrderForEach前序根 → 左 → 右根节点最先被访问inOrderForEach中序左 → 根 → 右对 BST 输出升序序列postOrderForEach后序左 → 右 → 根根节点最后被访问inOrderForEach(callback, node this.root) { if (typeof callback ! function) { throw new Error(Callback is required); } if (node null) return; this.inOrderForEach(callback, node.left); callback(node.data); this.inOrderForEach(callback, node.right); } preOrderForEach(callback, node this.root) { if (typeof callback ! function) { throw new Error(Callback is required); } if (node null) return; callback(node.data); this.preOrderForEach(callback, node.left); this.preOrderForEach(callback, node.right); } postOrderForEach(callback, node this.root) { if (typeof callback ! function) { throw new Error(Callback is required); } if (node null) return; this.postOrderForEach(callback, node.left); this.postOrderForEach(callback, node.right); callback(node.data); }三种遍历都与levelOrderForEach一样在缺少回调参数时抛出Error。中序遍历的特殊价值在于对一棵 BST 做中序遍历得到的一定是递增的有序序列——这一性质稍后在rebalance()中会派上大用场。第六步height 与 depth高度height的定义从该节点到某个叶节点的最长路径上的边数。叶节点的高度为 0。递归实现为「左右子树高度取较大者加 1」height(value) { const node this.#findNode(value); if (node undefined) return undefined; const getHeight (current) { if (current null) return -1; // 空子树贡献 -1使叶节点高度为 0 return 1 Math.max(getHeight(current.left), getHeight(current.right)); }; return getHeight(node); }这里用内部辅助函数#findNode(value)定位节点若值不存在原项目要求返回undefined。空子树返回-1是常见技巧1 max(-1, -1) 0恰好使叶节点高度为 0。深度depth的定义从该节点到根节点的路径上的边数根节点的深度为 0。实现方式是从根出发沿查找路径计数depth(value) { let current this.root; let edges 0; while (current ! null) { if (value current.data) return edges; current value current.data ? current.left : current.right; edges 1; } return undefined; // 未找到 }高度是从节点向下看到叶子的最长距离深度是从节点向上看到根的距离两者方向相反注意区分。第七步isBalanced 与 rebalanceisBalanced检查每一个节点一棵树是平衡的当且仅当对于树中的每个节点其左右子树的高度差不超过 1并且左右子树自身也平衡。原项目专门给出一个「陷阱提示」只比较根节点左右子树的高度差是不够的——某个深层的节点可能早已失衡。因此必须递归检查所有节点isBalanced(node this.root) { if (node null) return true; const leftHeight this.#getHeight(node.left); const rightHeight this.#getHeight(node.right); if (Math.abs(leftHeight - rightHeight) 1) return false; return this.isBalanced(node.left) this.isBalanced(node.right); }每次递归都要重新计算左右子树高度O(n)整体检查为O(n log n)如果想优化到O(n)可以让递归同时返回「是否平衡」与「子树高度」两个信息自底向上一次遍历完成但先写出正确版本更重要。rebalance借遍历之力重建平衡rebalance()的思路非常优雅先用中序遍历把失衡的树拍平成有序数组再把这个有序数组交给buildTree()重建一棵平衡树。这正是中序遍历对 BST 输出有序序列这一性质的直接应用rebalance() { const values []; this.inOrderForEach((value) values.push(value)); this.root buildTree(values); }由于中序遍历结果天然有序buildTree()内部的「排序去重」步骤对已是升序的数组而言只是幂等操作取中点递归建树后即可恢复平衡。第八步驱动脚本——把一切串联起来原项目要求编写一个驱动脚本按以下流程端到端验证整棵树的正确性从一组随机数每个元素小于 100创建 BST可用一个每次调用都返回随机数组的函数来生成调用isBalanced()确认树是平衡的分别以层序、前序、中序、后序打印所有元素插入几个大于 100的数值使树失衡调用isBalanced()确认树确实失衡调用rebalance()重新平衡再次调用isBalanced()确认已恢复平衡再次以层序、前序、中序、后序打印所有元素。一个参考骨架const randomArray () Array.from({ length: 15 }, () Math.floor(Math.random() * 100)); const tree new Tree(randomArray()); console.log(初始是否平衡:, tree.isBalanced()); // true tree.levelOrderForEach((v) console.log(level:, v)); tree.preOrderForEach((v) console.log(pre:, v)); tree.postOrderForEach((v) console.log(post:, v)); tree.inOrderForEach((v) console.log(in:, v)); [101, 205, 340, 450].forEach((n) tree.insert(n)); console.log(插入大数后是否平衡:, tree.isBalanced()); // false tree.rebalance(); console.log(再平衡后是否平衡:, tree.isBalanced()); // true tree.levelOrderForEach((v) console.log(level:, v)); tree.preOrderForEach((v) console.log(pre:, v)); tree.postOrderForEach((v) console.log(post:, v)); tree.inOrderForEach((v) console.log(in:, v));你可以配合prettyPrint(tree.root)观察失衡前后树形的变化连续插入[101, 205, 340, 450]会让树右侧越挂越长rebalance()之后再打印即可看到树重新变得「匀称」。若使用 ES6 模块import/export可参考 链表项目 中的提示使用 Node v22 及以上的 LTS 版本即可自动识别 ES6 模块并直接运行无需额外配置。复杂度总结与学习脉络把本次实现的所有操作放到 Big O 框架下审视操作平均时间复杂度说明buildTree(array)O(n log n)排序为主递归建树为O(n)includes(value)O(log n)每层排除一半节点insert(value)O(log n)沿查找路径走到空位deleteItem(value)O(log n)双孩子情形需查找中序后继四种遍历O(n)每个节点访问一次height/depthO(log n)高度需O(n)最坏取决于树形态isBalanced()O(n log n)朴素版每节点递归计算子树高度rebalance()O(n log n)中序收集 排序重建这些效率指标均建立在「树保持平衡」的前提上这正是本项目从建树到rebalance()始终围绕「平衡」这一主题的原因。本项目的直接前置是 常见数据结构与算法栈、队列、BFS/DFS、递归方法分而治之与 递归项目斐波那契与归并排序后续你将在 哈希映射项目 中对比另一种「平均O(1)」的查找结构并在 骑士旅行问题 中把 BFS 用于图的最短路径搜索。完成本项目后建议把每一段核心逻辑尤其是buildTree、deleteItem双孩子情形与isBalanced用prettyPrint反复可视化验证这是理解递归与树结构最有效的方式。【免费下载链接】curriculumThe open curriculum for learning web development项目地址: https://gitcode.com/GitHub_Trending/cu/curriculum创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考