站酷网站源码,免费发布推广的网站,网页设计作业个人网站,建设企业网站的价格1.树是什么
一种分层数据的抽象模型前端工作中常见的树包括#xff1a;DOM树#xff0c;级联选择(省市区)#xff0c;树形控件#xff0c;…javascript中没有树#xff0c;但是可以用Object和Array构建树 4.树的常用操作#xff1a;深度/广度优先遍历#xff0c;先中后…1.树是什么
一种分层数据的抽象模型前端工作中常见的树包括DOM树级联选择(省市区)树形控件…javascript中没有树但是可以用Object和Array构建树 4.树的常用操作深度/广度优先遍历先中后序遍历
深度 / 广度遍历
深度优先遍历尽可能深的搜索树的分支。如下图深度访问顺序 广度优先遍历先访问离跟节点最近的节点。
标题目录深入看每个目录下的小节。
深度优先遍历算法口诀其实就是一个递归
1.访问根节点。 2.对根节点的children挨个进行深度优先遍历。 只有2步写代码也只有2行代码但是这2行代码实现了深度优先递归在遍历的过程中被反复调用很多次。
const tree {val: a,children: [{val: b,children: [{val: d,children: []},{val: e,children: []}]},{val: c,children: [{val: f,children: []},{val: g,children: []}]}]
}
const dfs function (tree) {console.log(tree.val)// root.children.forEach((child) dfs(child))root.children.forEach(dfs)
}广度优先遍历算法口诀对列
1.新建一个队列把根节点入队 2.把队头出队并访问 3.把队头的children挨个入队 4.重复第23步知道队列为空。
const root {val: a,children: [{val: b,children: [{val: d,children: []},{val: e,children: []}]},{val: c,children: [{val: f,children: []},{val: g,children: []}]}]
}const bfs function (root) {const q [root]while(q.length 0) {const n q.shift()console.log(n.val)if (n.children) {n.children.forEach(child {q.push(child)})}}
}
二叉树的先中 后序的三种遍历
1.二叉树树中每个树的节点最多有2个节点 2.在js中通常用Object来模拟二叉树 先序遍历根左右
1.访问根节点 2.对结节点的左子树进行先序遍历 3.对根节点的右子树进行先序遍历
如上图访问顺序12 4 53, 6 7
const bt {val: 1,left: {val: 2,left: {val: 4,left: {},right: {}},right: {val: 5,left: {},right: {}}},right: {val: 3,left: {val: 6,left: {},right: {}},right: {val: 7,left: {},right: {}}}}const preorder function (root) {if (!root) return // 访问根节点console.log(root.val)preorder(root.left)preorder(root.right)
}中序遍历
