襄樊市网站建设,网站建设高级开发语言,有了网站开发app是不是更容易,门户网站建设 突出服务一文了解树在前端中的应用#x1f3d5;️序言#x1f332;一、树是什么#xff1f;#x1f334;二、深/广度优先遍历1、深度优先遍历#xff08;1#xff09;定义#xff08;2#xff09;口诀#xff08;3#xff09;代码实现2、广度优先遍历#xff08;1#xff0… 一文了解树在前端中的应用️序言一、树是什么二、深/广度优先遍历1、深度优先遍历1定义2口诀3代码实现2、广度优先遍历1定义2口诀3代码实现三、二叉树1、定义2、二叉树的先/中/后序遍历1先序遍历2中序遍历3后序遍历3、JS实现先中后序三种遍历1JS实现二叉树的先序遍历2JS实现二叉树的中序遍历3JS实现二叉树的后序遍历4总结☘️四、leetcode经典题目剖析1、leetcode104二叉树的最大深度简单2、leetcode111二叉树的最小深度简单3、leetcode102二叉树的层序遍历中等4、leetcode94二叉树的中序遍历简单5、leetcode112路径总和简单6、leetcode129求根节点到叶节点数字之和中等五、前端与树遍历JSON的所有节点值1、碎碎念2、代码实现1制造数据2遍历节点值3打印结果六、结束语彩蛋One More Thing(:往期推荐(:番外篇️序言
在我们的日常生活中无时无刻都会看到树。比如在街上行走时就有着一排排的树。那么树在前端中都有哪些应用呢
事实上前端在写页面时每个页面就有它对应的 DOM 树、 CSSOM 树等等。除此之外呢像我们写级联选择器时它也是一层叠一层的就像一棵树一样。
在接下来的这篇文章中将讲解树这个数据结构的一些基本操作以及树在前端中的应用。
一起来学习叭~
一、树是什么
树是一种具有分层数据功能的抽象模型。前端工作中常用的树包括 DOM 树、级联选择、树形空间……。JS 中没有树但是可以用 Object 和 Array 构建树。树的常用操作深度/广度优先遍历、先中后序遍历。
二、深/广度优先遍历
1、深度优先遍历
1定义
深度优先遍历即尽可能深的搜索树的分支。
2口诀
访问根节点。对根节点的 children 挨个进行深度优先遍历。
3代码实现
接下来用 JS 来实现树的深度优先遍历。具体代码如下
const tree {val:a,children:[{val:b,children:[{val:d,children:[]},{val:e,children:[]}]},{val:c,children:[{val:f,children:[]},{val:a,children:[]}]}]
}const dfs (root) {console.log(root.val);// 使用递归root.children.forEach(dfs);
}/*
打印结果
a
b
d
e
c
f
a
*/通过以上代码我们可以知道首先我们先定义一棵树 tree 之后使用递归的方法对树的 Children 挨个进行遍历最终得到 abdecfa 的打印结果。
这个顺序怎么理解会更为容易一点呢
在上面的知识点我们谈到树是往深了遍历。那在我们这道题的 tree 树当中我们总得先对第一层的遍历完才能遍历第二层的。而第一层的内容又有很多层那就先把它往深了遍历等到第一层的深度遍历结束后我们才开始遍历第二层的。
所以我们先在来看一下最上面的是 a 接着就是第一层第一层有 bde 接下来是第二层第二层就有 cfa 。因此最终的顺序为 abdecfa 。
2、广度优先遍历
1定义
广度优先遍历即先访问根节点最近的节点。
2口诀
新建一个队列。把队头出队并访问。把队头的 children 挨个入队。重复第二步和第三步直到队列为空。
3代码实现
接下来用 JS 来实现树的广度优先遍历。具体代码如下
const tree {val:a,children:[{val:b,children:[{val:d,children:[]},{val:e,children:[]}]},{val:c,children:[{val:f,children:[]},{val:a,children:[]}]}]
}const bfs (root) {// 新建一个队列并把根节点先放到队列里面const q [root];while(q.length 0){// 不断进行出队访问const n q.shift();// 边出队边访问console.log(n.val);// 把队头的children挨个入队退到队列里面n.children.forEach(child {q.push(child);});}
}bfs(tree);/*
打印结果
a
b
c
d
e
f
a
*/三、二叉树
1、定义
对于二叉树来说树中的每个节点最多只能有两个子节点。JS 中没有二叉树但通常用对象 Object 模拟二叉树。
2、二叉树的先/中/后序遍历
1先序遍历
访问根节点。对根节点的左子树进行先序遍历。对根节点的右子树进行先序遍历。
2中序遍历
对根节点的左子树进行中序遍历。访问根节点。对根节点的右子树进行中序遍历。
3后序遍历 对根节点的左子树进行后序遍历。 对根节点的右子树进行后序遍历。 访问根节点。
3、JS实现先中后序三种遍历
下面我们用代码来实现二叉树的这三种遍历。接下来开始讲解~
1JS实现二叉树的先序遍历
对于二叉树的先序遍历来说是先访问根节点之后再访问左子树最后访问右子树。下面我们用两种方式来实现先序遍历第一种是递归版本第二种是非递归版本。
先定义一棵树
const bt {val:1,left:{val:2,left:{val:4,left:null,right:null},right:{val:5,left:null,right:null}},right:{val:3,left:{val:6,left:null,right:null},right:{val:7,left:null,right:null}}
}递归版本实现
// 递归版本实现
const preOrder1 (root) {if(!root){return;}console.log(root.val);preOrder1(root.left);preOrder1(root.right);
}preOrder1(bt);
/**打印结果
1
2
4
5
3
6
7
*/非递归版本实现
// 非递归版实现
/*** 思路* 1.新建一个栈模拟函数的调用堆栈* 2.对于先序遍历来说需要先把根节点取出然后再遍历左子树了右子树* 3.按照栈的先进后出特点先把右子树放进栈里再把左子树放进栈里一一取出。*/
const preOrder2 (root) {if(!root){return;}// 新建一个stack代表函数的调用堆栈const stack [root];// console.log(stack)while(stack.length){// 将根节点从栈里弹出const n stack.pop();console.log(n.val);if(n.right){stack.push(n.right);}if(n.left){stack.push(n.left);}}
}preOrder2(bt);
/**打印结果
1
2
4
5
3
6
7
*/2JS实现二叉树的中序遍历
对于二叉树的中序遍历来说是先访问左子树之后访问根节点最后再访问右子树。下面我们用两种方式来实现中序遍历第一种是递归版本第二种是非递归版本。
同样地我们先来先定义一棵树
const bt {val:1,left:{val:2,left:{val:4,left:null,right:null},right:{val:5,left:null,right:null}},right:{val:3,left:{val:6,left:null,right:null},right:{val:7,left:null,right:null}}
}递归版本实现
// 递归版本实现
const inOrder1 (root) {if(!root){return;}inOrder(root.left);console.log(root.val);inOrder(root.right);
}inOrder1(bt);
/**打印结果
4
2
5
1
6
3
7
*/非递归版本实现
// 非递归版实现
/*** 思路* 1.新建一个栈模拟函数的调用堆栈* 2.对于中序遍历来说需要先把左子树全部丢到栈里面那么需要每当遍历一个就推到栈里面* 3.遍历完成之后把最尽头的结点弹出并访问它此处最尽头的结点即尽头出的根节点左根右* 4.访问完左结点后需要访问右结点*/
const inOrder2 (root) {if(!root){return;}let p root;const stack [];while(p || stack.length){while(p){// 先进栈stack.push(p);// 进栈完继续指向左子树p p.left;}// 弹出最后一个const n stack.pop();console.log(n.val);p n.right;}}inOrder2(bt);
/**打印结果
4
2
5
1
6
3
7
*/3JS实现二叉树的后序遍历
对于二叉树的后序遍历来说是先访问左子树之后访问右子树最后再访问根节点。下面我们用两种方式来实现后序遍历第一种是递归版本第二种是非递归版本。
首先同样地先来定义一棵树
const bt {val:1,left:{val:2,left:{val:4,left:null,right:null},right:{val:5,left:null,right:null}},right:{val:3,left:{val:6,left:null,right:null},right:{val:7,left:null,right:null}}
}递归版本实现
// 递归版本实现
const postOrder1 (root) {if(!root){return;}postOrder1(root.left);postOrder1(root.right);console.log(root.val);
}preOrder1(bt);
/**打印结果
1
2
4
5
3
6
7
*/非递归版本实现
// 非递归版实现
/*** 思路* 1.建立一个空栈stack* 2.分别把左子树右子树分别放入stack栈* 3.建立一个倒序栈outputStack先把根树放进再一一放入右子树右子树全部放完之后再放左子树*/
const postOrder2 (root) {if(!root){return;}// 倒序栈输出放根右左的顺序之后再一一取出const outputStack [];// 先放左子树再放右子树方便后面取出const stack [root];while(stack.length){const n stack.pop();outputStack.push(n);if(n.left){stack.push(n.left);}if(n.right){stack.push(n.right);}}while(outputStack.length){const n outputStack.pop();console.log(n.val);}
}
preOrder2(bt);
/**打印结果
1
2
4
5
3
6
7
*/4总结
看完上面的代码实现后我们来做个总结。为什么这里要展示递归版本和非递归版本呢
事实上在我们的日常开发中递归遍历是非常常见的。但试想一下有时候我们的业务逻辑有可能很复杂那这个时候前端从后端接收到的数据量是比较大的。这个时候如果用递归版本来处理的话算法复杂度相对来说就会比较高了。
所以我们多了一种非递归版本的实现方式非递归版本的实现方式旨在以空间来换时间减少代码的时间复杂度。
☘️四、leetcode经典题目剖析
接下来我们引用几道经典的 leetcode 算法来巩固树和二叉树的知识。
1、leetcode104二叉树的最大深度简单
1题意
附上题目链接leetcode104二叉树的最大深度
给定一个二叉树找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
输入输出示例
输入: 给定二叉树 [3,9,20,null,null,15,7]输出: 3
2解题思路
求最大深度考虑使用深度优先遍历。在深度优先遍历过程中记录每个节点所在的层级找出最大的层级即可。
3解题步骤
新建一个变量记录最大深度。深度优先遍历整棵树并记录每个节点的层级同时不断刷新最大深度的这个变量。遍历结束返回最大深度的变量。
4代码实现
/*** param {TreeNode} root* return {number}*/
let maxDepth function(root) {let res 0;const dfs (n, l) {if(!n){return;}if(!n.left !n.right){res Math.max(res, l);}dfs(n.left, l 1);dfs(n.right, l 1);}dfs(root, 1);return res;
}2、leetcode111二叉树的最小深度简单
1题意
附上题目链接leetcode111二叉树的最小深度
给定一个二叉树找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
**说明**叶子节点是指没有子节点的节点。
输入输出示例
输入: root [3,9,20,null,null,15,7]输出: 2
2解题思路
求最小深度考虑使用广度优先遍历。在广度优先遍历过程中遇到叶子节点停止遍历返回节点层级。
3解题步骤
广度优先遍历整棵树并记录每个节点的层级。遇到叶子节点返回节点层级停止遍历。
4代码实现
/*** param {TreeNode} root* return {number}*/let minDepth function(root){if(!root){return 0;}const q [[root, 1]];while(q.length){const [n, l] q.shift();if(!n.left !n.right){return l;}if(n.left){q.push([n.left, l 1]);}if(n.right){q.push([n.right, l 1]);}}
}3、leetcode102二叉树的层序遍历中等
1题意
附上题目链接leetcode102二叉树的层序遍历
给你一个二叉树请你返回其按 层序遍历 得到的节点值。 即逐层地从左到右访问所有节点。
输入输出示例 输入: 二叉树[3,9,20,null,null,15,7] 3/ \9 20/ \15 7输出: [[3],[9,20],[15,7]
]2解题思路
层序遍历顺序就是广度优先遍历。不过在遍历时候需要记录当前节点所处的层级方便将其添加到不同的数组中。
3解题步骤
广度优先遍历二叉树。遍历过程中记录每个节点的层级并将其添加到不同的数组中。
4代码实现
/*** param {TreeNode} root* return {number[][]}*/
// 方法一
let levelOrder1 function(root) {if(!root){return [];}const q [[root, 0]];const res [];while(q.length){const [n, level] q.shift();if(!res[level]){// 没有该层次的数组时先创建一个数组res.push([n.val]);}else{// 有数组时直接将值放进res[level].push(n.val);}if(n.left){q.push([n.left, level 1]);}if(n.right){q.push([n.right, level 1]);}}return res;
};// 方法二
let levelOrder2 function(root){if(!root){return [];}const q [root];const res [];while(q.length){let len q.length;res.push([]);while(len--){const n q.shift();res[res.length - 1].push(n.val);if(n.left){q.push(n.left);}if(n.right){q.push(n.right);}}}return res;
}4、leetcode94二叉树的中序遍历简单
1题意
附上题目链接leetcode94二叉树的中序遍历
给定一个二叉树的根节点 root 返回它的 中序 遍历。
输入输出示例
输入: root [1,null,2,3]输出: [1,3,2]
2解题思路解题步骤
这里的解题思路和步骤和上方讲中序遍历时类似所以不再做讲解下面直接看代码实现。
3代码实现
/*** param {TreeNode} root* return {number[]}*/
// 遍历版本let inorderTraversal1 function(root) {const res [];const rec (n) {if(!n){return;}rec(n.left);rec(n.val);rec(n.right);}rec(root);return res;
};// 迭代版本——栈方法
let inorderTraversal2 function(root){const res [];const stack [];let p root;while(stack.length || p){while(p){stack.push(p);p p.left;}const n stack.pop();res.push(n.val);p n.right;}return res;
}inorderTraversal1(root);
inorderTraversal2(root);5、leetcode112路径总和简单
1题意
附上题目链接leetcode112路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 判断该树中是否存在 根节点到叶子节点 的路径这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。
输入输出示例
输入: root [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum 22输出: true
2解题思路
在深度优先遍历的过程中记录当前路径思维节点值的和。在叶子节点处判断当前路径的节点值的和是否等于目标值。
3解题步骤
深度优先遍历二叉树在叶子节点处判断当前路径路径的节点值的和是否等于目标值是就返回true。遍历结束如果没有匹配就返回false。
4代码实现
/*** param {TreeNode} root* param {number} targetSum* return {boolean}*/
// 递归法
let hasPathSum function(root, targetSum) {if(!root){return false;}let res false;const dfs (n, s) {if(!n.left !n.right s targetSum){res true;}if(n.left){dfs(n.left, s n.left.val);}if(n.right){dfs(n.right, s n.right.val);}}dfs(root, root.val);return res;
};6、leetcode129求根节点到叶节点数字之和中等
1题意
附上题目链接leetcode129求根节点到叶节点数字之和
给你一个二叉树的根节点 root 树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字
例如从根节点到叶节点的路径 1 - 2 - 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。
输入输出示例
输入: root [1,2,3]输出: 25解释: 从根到叶子节点路径 1-2 代表数字 12从根到叶子节点路径 1-3 代表数字 13因此数字总和 12 13 25
2解题思路
在深度优先遍历的过程中记录当前路径前面节点的值。在叶子节点处计算出当前路径值。
3解题步骤
深度优先遍历二叉树直到每一棵树的叶子节点处结束。遍历结束返回所有路径值。
4代码实现
/*** param {TreeNode} root* return {number}*/var sumNumbers function(root) {// 深度优先遍历处理const dfs (n, preNum) {if(!n){return 0;}const sum preNum * 10 n.val;if(!n.left !n.right){return sum;}else{return dfs(n.left, sum) dfs(n.right, sum);}}return dfs(root, 0);
};五、前端与树遍历JSON的所有节点值
1、碎碎念
有时候后端传过来的数据可能不是很友好有可能一串数据里面又是对象又是数组的这个时候前端拿到数据后就需要稍微处理一下了。
因此我们可以通过深度优先遍历来遍历 JSON 中的所有节点值。
接下来用一个例子来展示~
2、代码实现
1制造数据
假设我们心在有一串 json 的数据代码如下
const json {a:{b:{c:1}},d:[1, 2]
}2遍历节点值
接下来我们用深度优先遍历的方式来遍历 JSON 中的所有节点值。具体实现代码如下
const dfs (n, path) {console.log(n, path);Object.keys(n).forEach(k {dfs(n[k], path.concat(k));});
};dfs(json, []);3打印结果
最终打印结果如下
{ a: { b: { c: 1 } }, d: [ 1, 2 ] } []
{ b: { c: 1 } } [ a ]
{ c: 1 } [ a, b ]
1 [ a, b, c ]
[ 1, 2 ] [ d ]
1 [ d, 0 ]
2 [ d, 1 ]大家看上面的打印结果可以发现通过深度优先遍历的方式数据都被一一遍历出来。因此对于树这种数据结构来说在前端当中出现的频率也是较高的~~
六、结束语
通过上文的学习我们了解了树的两种遍历深度优先遍历和广度优先遍历。同时还有一种特殊的树二叉树。二叉树在面试中基本上是一大必考点。对于二叉树来说要了解它的三种遍历方式先序、中序和后序遍历并且要掌握好这三者之间的区别以及常见的应用场景。
关于树在前端中的应用讲到这里就结束啦希望对大家有帮助~
如有疑问或文章有误欢迎评论区留言或公众号后台加我微信提问~
彩蛋One More Thing
(:往期推荐
栈栈在前端中的应用顺便再了解下深拷贝和浅拷贝
队列详解队列在前端的应用深剖JS中的事件循环Eventloop再了解微任务和宏任务
链表详解链表在前端的应用顺便再弄懂原型和原型链
字典和集合ES6的Set和Map你都知道吗一文了解集合和字典在前端中的应用
动态规则和分而治之算法一文了解分而治之和动态规则算法在前端中的应用
贪心算法和回溯算法一文了解贪心算法和回溯算法在前端中的应用
(:番外篇 关注公众号星期一研究室第一时间关注学习干货更多精选专栏待你解锁~如果这篇文章对你有用记得留个脚印jio再走哦~以上就是本文的全部内容我们下期见
