关于javascript:javascript数据结构与算法学习笔记之树

一种分层数据的形象模型
前端工作中常见的树包含：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
          }
        ]
      },
    }
  ]
}

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

拜访根节点
对根节点的 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

新建一个队列，把根节点入队
把队头出队并拜访
把队头的 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

二叉树概念：

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

在 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

关于javascript:javascript数据结构与算法学习笔记之树

树简介

深度与广度优先遍历

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

算法口诀：

代码实操

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

算法口诀

代码实操

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

先序遍历

中序遍历

后序遍历