编程知识 cdmana.com

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
              }
            ]
          },
        }
      ]
    }
    • 树的常用操作: 深度 / 广度 优先遍历、先中后序遍历

深度与广度优先遍历

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

image-20201223205523031

算法口诀:

  • 访问根节点
  • 对根节点的 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. 广度优先遍历: 先访问离根节点最近的节点

image-20201223205608813

算法口诀

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

先序遍历

image-20201224100004922

算法口诀

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

代码实践

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

中序遍历

image-20201224101445115

算法口诀

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

代码实践

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

后序遍历

image-20201224102218265

算法口诀

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

代码实践

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

版权声明
本文为[提莫队长]所创,转载请带上原文链接,感谢
https://segmentfault.com/a/1190000038624135

Scroll to Top