【JS】javascript数据结构与算法学习笔记之“树”

• Z时代
• 2024-01-10
• 分类：技术分享

​

树简介

• 一种分层数据的抽象模型
• 前端工作中常见的树包括： DOM 树、级联选择（省市区三级，日期。。。）、树形控件...

• JS 中没有树，但可以用 Object 和 Array 构建树，如下：

  {
  value: "安徽省",
  label: 'anhui',
  children: [
  {
  value: "合肥市",
  label: 'hefei',
  children: [
  {
  value: "包河区",
  label: 'baohe',
  children: null
  },
  {
  value: '滨湖区',
  label: 'binghu',
  children: null
  }
  ]
  },
  {
  {
  value: "安庆市",
  label: 'anqing',
  children: [
  {
  value: "越秀区",
  label: 'yuexiu',
  children: null
  }
  ]
  },
  }
  ]
  }

  • 树的常用操作： 深度 / 广度 优先遍历、先中后序遍历

深度与广度优先遍历

1. 深度优先遍历：尽可能深的搜索树的分支

算法口诀：

• 访问根节点
• 对根节点的 children 挨个进行深度优先遍历

代码实操

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 = (root) => {
console.log(root.val)
// root.children.map((child)=> dfs(child))
root.children.map(dfs)
}
// 执行深度优先遍历函数
dfs(tree)
// 执行后依次输出： a b d e c f g

2. 广度优先遍历： 先访问离根节点最近的节点

算法口诀

• 新建一个队列，把根节点入队
• 把队头出队并访问
• 把队头的 children 挨个入队
• 重复第二、三步，直到队列清空

代码实操

const tree = {
val: 'a',
children: [
{
val: 'b',
children: [
{
val: 'd',
children: []
},
{
val: 'e',
children: []
}
]
},
{
val: 'c',
children: [
{
val: 'f',
children: []
},
{
val: 'g',
children: []
}
]
}
]
}
const bfs = (root) => {
// step1: 新建一个队列
let queue = []
// step2: 把根节点入队
queue.push(root)
while(queue.length > 0) {
// step3: 取出队头并访问
let n = queue.shift()
console.log(n.val)
// step4: 把队头的 children 挨个入队并重复以上步骤
n.children.map(child=> {
queue.push(child)
})
}
}
// 执行广度优先遍历函数
bfs(tree)
// 依次输出：a b c d e f g

3. 二叉树的先中后序遍历

• 二叉树概念：

  树中每个节点最多只能有两个子节点；

  在 JS 中通常用 Object 来模拟二叉树

  代码模拟

  // bt.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,
  },
  },
  };
  module.exports = bt;

先序遍历

算法口诀

• 访问根节点
• 对根节点的左子树进行先序遍历
• 对根节点的右子树进行先序遍历

代码实践

const bt = require('./bt')
const preOrder = (root) => {
if(!root) return
console.log(root.val)
preOrder(root.left)
preOrder(root.right)
}
// 执行
preOrder(bt)
// 依次输出：1 2 4 5 3 6 7

中序遍历

算法口诀

• 对根节点的左子树进行中序遍历
• 访问根节点
• 对根节点的右子树进行中序遍历

代码实践

const bt = require('./bt')
const inOrder = (root) => {
if(!root) return
inOrder(root.left)
console.log(root.val)
inOrder(root.right)
}
inOrder(bt)
// 依次输出 4 2 5 1 6 3 7

后序遍历

算法口诀

• 对根节点的左子树进行后序遍历
• 对根节点的右子树进行后序遍历
• 访问根节点

代码实践

const bt = require('./bt')
const postOrder = (root) => {
if(!root) return
postOrder(root.left)
postOrder(root.right)
console.log(root.val)
}
postOrder(bt)
// 依次输出：4 5 2 6 7 3 1

以上是 【JS】javascript数据结构与算法学习笔记之“树” 的全部内容， 来源链接： utcz.com/a/90673.html