一、什么是树数据结构中的树是对现实世界中树的抽象和简化根节点对应现实中的树根是一切的起点边对应现实中的树枝连接两个节点叶子节点对应现实中的树叶是树的末端把现实中的树倒过来看就是数据结构中树的样子从根节点开始每个节点延伸出一个或多个子节点层层向下直到叶子节点为止。A ← 根节点第 1 层 / \ B C ← 第 2 层 / \ / \ D E F G ← 第 3 层叶子节点关键概念速览概念说明层次根节点为第 1 层其子节点为第 2 层依此类推高度叶子节点高度为 1每向上一层 1度一个节点拥有的子树数量叶子节点度为 0 的节点即没有子节点的节点深度从根节点到目标节点的路径长度⚖️二、二叉树定义二叉树是每个节点最多有两个子节点的树。它的定义天然适合用递归来描述一棵二叉树要么是空树要么由根节点、左子树和右子树三部分组成且左右子树本身也都是二叉树。这里有两点值得注意左右严格区分二叉树中左子树和右子树的位置是严格约定的不能随意交换。左右互换后是两棵不同的二叉树。度 ≤ 2 不等于二叉树二叉树不能简单定义为每个节点度最大为 2 的树因为普通树不区分左右而二叉树区分。在 JavaScript 中表示二叉树一个二叉树节点由三部分构成数据域左子节点引用右子节点引用。functionTreeNode(val){this.valval;this.leftthis.rightnull;// 左右子节点初始为空}构建一棵具体的二叉树consttree{val:A,left:{val:B,left:{val:D,left:null,right:null},right:{val:E,left:null,right:null}},right:{val:C,left:{val:F,left:null,right:null},right:{val:G,left:null,right:null}}};这棵二叉树的结构如下A / \ B C / \ / \ D E F G多叉树的表示如果不是二叉树而是一个节点可以有任意多个子节点的情况可以用children数组来表示consttree{value:A,children:[{value:B,children:[{value:D,children:[]},{value:E,children:[]}]},{value:C,children:[{value:F,children:[]},{value:G,children:[]}]}]};两种表示方式的选择取决于实际场景二叉树用left/right语义更清晰多叉树用children数组更灵活。三、二叉树的遍历遍历是树最核心的操作。按照访问根节点的时机不同分为四种遍历方式。递归遍历中左右子树的访问顺序永远是先左后右区别只在于根节点何时被访问。✨3.1 前序遍历根 → 左 → 右先访问根节点再递归访问左子树最后递归访问右子树。functionpreorder(root){if(!root){return;// 退出条件空节点}console.log(root.val);// 先访问根preorder(root.left);// 再访问左子树preorder(root.right);// 最后访问右子树}对示例树调用preorder(tree)输出顺序为A → B → D → E → C → F → G。动态演示✨3.2 中序遍历左 → 根 → 右先递归访问左子树再访问根节点最后递归访问右子树。functioninorder(root){if(!root){return;// 退出条件空节点}inorder(root.left);// 先访问左子树console.log(root.val);// 再访问根inorder(root.right);// 最后访问右子树}输出顺序为D → B → E → A → F → C → G。二叉搜索树的中序遍历结果是有序的这是中序遍历的一个重要特性。✨3.3 后序遍历左 → 右 → 根先递归访问左子树再递归访问右子树最后访问根节点。functionpostorder(root){if(!root){return;// 退出条件空节点}postorder(root.left);// 先访问左子树postorder(root.right);// 再访问右子树console.log(root.val);// 最后访问根}输出顺序为D → E → B → F → G → C → A。后序遍历的一个典型应用场景是删除树先删除子节点最后删除父节点避免删了父节点找不到子节点的问题。✨3.4 层序遍历广度优先层序遍历不使用递归而是借助队列实现逐层访问。functionlevelorder(root){constqueue[];// 辅助队列constresult[];// 存放遍历结果if(!root){returnresult;}queue.push(root);// 根节点入队while(queue.length0){constnodequeue.shift();// 队首出队result.push(node.val);// 访问当前节点if(node.left){queue.push(node.left);// 左子节点入队}if(node.right){queue.push(node.right);// 右子节点入队}}returnresult;}输出顺序为A → B → C → D → E → F → G逐层从左到右。✅四种遍历对比遍历方式访问顺序实现方式示例输出前序根 → 左 → 右递归A B D E C F G中序左 → 根 → 右递归D B E A F C G后序左 → 右 → 根递归D E B F G C A层序逐层从左到右队列迭代A B C D E F G四、递归思想 —— 从爬楼梯理解树状结构树和递归是天然绑定的一对概念。递归的核心三要素自顶向下思考把大问题拆成小问题找到递归公式每次解决的问题模式相同明确退出条件递归不能无限进行爬楼梯问题假设你正在爬楼梯每次可以爬 1 阶或 2 阶。爬到第n阶有多少种不同的方法这个问题从顶向下看呈现出典型的树状结构f(10) / \ f(9) f(8) / \ / \ f(8) f(7) f(7) f(6) ... ... ... ... 最终 f(1) 1 种 f(2) 2 种递归公式f(n) f(n-1) f(n-2)退出条件n ≤ 2时f(1) 1f(2) 2functionclimbStairs(n){if(n2){returnn;// 退出条件}letaclimbStairs(n-1);// 最后一步走 1 阶letbclimbStairs(n-2);// 最后一步走 2 阶returnab;// 递归公式}console.log(climbStairs(10));// 89// ⚠️ 注意这种朴素递归当 n 较大时如 n100会卡死// 原因大量重复计算时间复杂度 O(2ⁿ)函数调用栈也可能爆栈⚡递归的隐患爆栈每次递归调用都会在调用栈中压入一个新的函数帧。递归过深时栈内存会被耗尽。重复计算从上图可以看到f(8)被计算了两次f(7)被计算了三次……随 n 增大重复量呈指数级增长。实际工程中可以用记忆化搜索缓存已计算的结果或动态规划自底向上迭代来优化这里不展开。五、总结整篇文章的核心脉络可以归纳为一条线现实中的树 → 数据结构的树 → 二叉树 → JS 中的表示 → 遍历递归 / 迭代 → 递归思维爬楼梯树是递归定义的天然适合用递归思维去理解和操作二叉树的四种遍历前序、中序、后序、层序是树操作的基础三种深度优先遍历的区别仅在于访问根节点的时机递归三要素自顶向下、递归公式、退出条件不仅是树的解题框架也是所有递归问题的通用心法递归代码简洁优雅但要警惕重复计算和爆栈的风险标签树与二叉树
从零理解树与二叉树 —— 概念、实现与遍历
一、什么是树数据结构中的树是对现实世界中树的抽象和简化根节点对应现实中的树根是一切的起点边对应现实中的树枝连接两个节点叶子节点对应现实中的树叶是树的末端把现实中的树倒过来看就是数据结构中树的样子从根节点开始每个节点延伸出一个或多个子节点层层向下直到叶子节点为止。A ← 根节点第 1 层 / \ B C ← 第 2 层 / \ / \ D E F G ← 第 3 层叶子节点关键概念速览概念说明层次根节点为第 1 层其子节点为第 2 层依此类推高度叶子节点高度为 1每向上一层 1度一个节点拥有的子树数量叶子节点度为 0 的节点即没有子节点的节点深度从根节点到目标节点的路径长度⚖️二、二叉树定义二叉树是每个节点最多有两个子节点的树。它的定义天然适合用递归来描述一棵二叉树要么是空树要么由根节点、左子树和右子树三部分组成且左右子树本身也都是二叉树。这里有两点值得注意左右严格区分二叉树中左子树和右子树的位置是严格约定的不能随意交换。左右互换后是两棵不同的二叉树。度 ≤ 2 不等于二叉树二叉树不能简单定义为每个节点度最大为 2 的树因为普通树不区分左右而二叉树区分。在 JavaScript 中表示二叉树一个二叉树节点由三部分构成数据域左子节点引用右子节点引用。functionTreeNode(val){this.valval;this.leftthis.rightnull;// 左右子节点初始为空}构建一棵具体的二叉树consttree{val:A,left:{val:B,left:{val:D,left:null,right:null},right:{val:E,left:null,right:null}},right:{val:C,left:{val:F,left:null,right:null},right:{val:G,left:null,right:null}}};这棵二叉树的结构如下A / \ B C / \ / \ D E F G多叉树的表示如果不是二叉树而是一个节点可以有任意多个子节点的情况可以用children数组来表示consttree{value:A,children:[{value:B,children:[{value:D,children:[]},{value:E,children:[]}]},{value:C,children:[{value:F,children:[]},{value:G,children:[]}]}]};两种表示方式的选择取决于实际场景二叉树用left/right语义更清晰多叉树用children数组更灵活。三、二叉树的遍历遍历是树最核心的操作。按照访问根节点的时机不同分为四种遍历方式。递归遍历中左右子树的访问顺序永远是先左后右区别只在于根节点何时被访问。✨3.1 前序遍历根 → 左 → 右先访问根节点再递归访问左子树最后递归访问右子树。functionpreorder(root){if(!root){return;// 退出条件空节点}console.log(root.val);// 先访问根preorder(root.left);// 再访问左子树preorder(root.right);// 最后访问右子树}对示例树调用preorder(tree)输出顺序为A → B → D → E → C → F → G。动态演示✨3.2 中序遍历左 → 根 → 右先递归访问左子树再访问根节点最后递归访问右子树。functioninorder(root){if(!root){return;// 退出条件空节点}inorder(root.left);// 先访问左子树console.log(root.val);// 再访问根inorder(root.right);// 最后访问右子树}输出顺序为D → B → E → A → F → C → G。二叉搜索树的中序遍历结果是有序的这是中序遍历的一个重要特性。✨3.3 后序遍历左 → 右 → 根先递归访问左子树再递归访问右子树最后访问根节点。functionpostorder(root){if(!root){return;// 退出条件空节点}postorder(root.left);// 先访问左子树postorder(root.right);// 再访问右子树console.log(root.val);// 最后访问根}输出顺序为D → E → B → F → G → C → A。后序遍历的一个典型应用场景是删除树先删除子节点最后删除父节点避免删了父节点找不到子节点的问题。✨3.4 层序遍历广度优先层序遍历不使用递归而是借助队列实现逐层访问。functionlevelorder(root){constqueue[];// 辅助队列constresult[];// 存放遍历结果if(!root){returnresult;}queue.push(root);// 根节点入队while(queue.length0){constnodequeue.shift();// 队首出队result.push(node.val);// 访问当前节点if(node.left){queue.push(node.left);// 左子节点入队}if(node.right){queue.push(node.right);// 右子节点入队}}returnresult;}输出顺序为A → B → C → D → E → F → G逐层从左到右。✅四种遍历对比遍历方式访问顺序实现方式示例输出前序根 → 左 → 右递归A B D E C F G中序左 → 根 → 右递归D B E A F C G后序左 → 右 → 根递归D E B F G C A层序逐层从左到右队列迭代A B C D E F G四、递归思想 —— 从爬楼梯理解树状结构树和递归是天然绑定的一对概念。递归的核心三要素自顶向下思考把大问题拆成小问题找到递归公式每次解决的问题模式相同明确退出条件递归不能无限进行爬楼梯问题假设你正在爬楼梯每次可以爬 1 阶或 2 阶。爬到第n阶有多少种不同的方法这个问题从顶向下看呈现出典型的树状结构f(10) / \ f(9) f(8) / \ / \ f(8) f(7) f(7) f(6) ... ... ... ... 最终 f(1) 1 种 f(2) 2 种递归公式f(n) f(n-1) f(n-2)退出条件n ≤ 2时f(1) 1f(2) 2functionclimbStairs(n){if(n2){returnn;// 退出条件}letaclimbStairs(n-1);// 最后一步走 1 阶letbclimbStairs(n-2);// 最后一步走 2 阶returnab;// 递归公式}console.log(climbStairs(10));// 89// ⚠️ 注意这种朴素递归当 n 较大时如 n100会卡死// 原因大量重复计算时间复杂度 O(2ⁿ)函数调用栈也可能爆栈⚡递归的隐患爆栈每次递归调用都会在调用栈中压入一个新的函数帧。递归过深时栈内存会被耗尽。重复计算从上图可以看到f(8)被计算了两次f(7)被计算了三次……随 n 增大重复量呈指数级增长。实际工程中可以用记忆化搜索缓存已计算的结果或动态规划自底向上迭代来优化这里不展开。五、总结整篇文章的核心脉络可以归纳为一条线现实中的树 → 数据结构的树 → 二叉树 → JS 中的表示 → 遍历递归 / 迭代 → 递归思维爬楼梯树是递归定义的天然适合用递归思维去理解和操作二叉树的四种遍历前序、中序、后序、层序是树操作的基础三种深度优先遍历的区别仅在于访问根节点的时机递归三要素自顶向下、递归公式、退出条件不仅是树的解题框架也是所有递归问题的通用心法递归代码简洁优雅但要警惕重复计算和爆栈的风险标签树与二叉树
