🏕️序言
在我们的日常生活中,无时无刻都会看到树。比如,在街上行走时,就有着一排排的树。那么,树在前端中,都有哪些应用呢?
事实上,前端在写页面时,每个页面就有它对应的 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实现先中后序三种遍历
下面我们用代码来实现二叉树的这三种遍历。接下来开始讲解~
(1)JS实现二叉树的先序遍历
对于二叉树的先序遍历来说,是先访问根节点,之后再访问左子树,最后访问右子树。下面我们用两种方式来实现先序遍历,第一种是递归版本,第二种是非递归版本。
先定义一棵树:
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 */ 复制代码
(2)JS实现二叉树的中序遍历
对于二叉树的中序遍历来说,是先访问左子树,之后访问根节点,最后再访问右子树。下面我们用两种方式来实现中序遍历,第一种是递归版本,第二种是非递归版本。
同样地,我们先来先定义一棵树:
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 */ 复制代码
(3)JS实现二叉树的后序遍历
对于二叉树的后序遍历来说,是先访问左子树,之后访问右子树,最后再访问根节点。下面我们用两种方式来实现后序遍历,第一种是递归版本,第二种是非递归版本。
首先同样地,先来定义一棵树:
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)总结
看完上面的代码实现后,我们来做个总结。为什么这里要展示递归版本和非递归版本呢?
事实上,在我们的日常开发中,递归遍历是非常常见的。但试想一下,有时候我们的业务逻辑有可能很复杂,那这个时候前端从后端接收到的数据量是比较大的。这个时候如果用递归版本来处理的话,算法复杂度相对来说就会比较高了。
所以我们多了一种非递归版本的实现方式,非递归版本的实现方式,旨在以空间来换时间,减少代码的时间复杂度。