• 技术文章 >web前端 >js教程

    详细介绍JavaScript二叉树及各种遍历算法

    长期闲置长期闲置2022-07-27 17:34:36转载222
    本篇文章给大家带来了关于javascript的相关知识,主要介绍了JavaScript二叉树及各种遍历算法详情,文章围绕主题展开详细的内容介绍,具有一定的参考价值,需要的小伙伴可以参考一下,希望对大家有帮助。

    【相关推荐:javascript视频教程web前端

    什么是二叉树

    二叉树是每个节点最多只能有两个子节点的树,如下图所示:

    一个二叉树具有以下几个特质:

    满二叉树

    如果在一个二叉树中,除了叶子节点,其余的节点的每个度都是2,则说明该二叉树是一个满二叉树

    如下图所示:

    满二叉树除了满足普通二叉树特质,还具有如下几个特质:

    完全二叉树

    如果一个二叉树去掉最后一次层是满二叉树,且最后一次的节点是依次从左到右分布的,则这个二叉树是一个完全二叉树,

    如下图所示:

    二叉树的存储

    存储二叉树的常见方式分为两种,一种是使用数组存储,另一种使用链表存储。

    数组存储

    使用数组存储二叉树,如果遇到完全二叉树,存储顺序从上到下,从左到右,如下图所示:

    如果是一个非完全二叉树,如下图所示:

    需要先将其转换为完全二叉树,然后在进行存储,如下图所示:

    可以很明显的看到存储空间的浪费。

    链表存储

    使用链表存储通常将二叉树中的分为3个部分,如下图:

    这三个部分依次是左子树的引用,该节点包含的数据,右子树的引用,存储方式如下图所示:

    与二叉树相关的算法

    以下算法中遍历用到的树如下

    // tree.js
    const bt = {
      val: 'A',
      left: {
        val: 'B',
        left: { val: 'D', left: null, right: null },
        right: { val: 'E', left: null, right: null },
      },
      right: {
        val: 'C',
        left: {
          val: 'F',
          left: { val: 'H', left: null, right: null },
          right: { val: 'I', left: null, right: null },
        },
        right: { val: 'G', left: null, right: null },
      },
    }
    module.exports = bt

    深度优先遍历

    二叉树的深度优先遍历与树的深度优先遍历思路一致,思路如下:

    实现代码如下:

    const bt = {
      val: 'A',
      left: {
        val: 'B',
        left: { val: 'D', left: null, right: null },
        right: { val: 'E', left: null, right: null },
      },
      right: {
        val: 'C',
        left: {
          val: 'F',
          left: { val: 'H', left: null, right: null },
          right: { val: 'I', left: null, right: null },
        },
        right: { val: 'G', left: null, right: null },
      },
    }
    
    function dfs(root) {
      if (!root) return
      console.log(root.val)
      root.left && dfs(root.left)
      root.right && dfs(root.right) 
    }
    dfs(bt)
    /** 结果
    A B D E C F H I G
    */

    广度优先遍历

    实现思路如下:

    实现代码如下:

    function bfs(root) {
      if (!root) return
      const queue = [root]
      while (queue.length) {
        const node = queue.shift()
        console.log(node.val)
        node.left && queue.push(node.left)
        node.right && queue.push(node.right)
      }
    }
    bfs(bt)
    /** 结果
    A B C D E F G H I
     */

    先序遍历

    二叉树的先序遍历实现思想如下:

    如下图所示:

    递归方式实现如下:

    const bt = require('./tree')
    
    function preorder(root) {
      if (!root) return
      console.log(root.val)
      preorder(root.left)
      preorder(root.right)
    }
    preorder(bt)
    /** 结果
    A B D E C F H I G
    */

    迭代方式实现如下:

    // 非递归版
    function preorder(root) {
      if (!root) return
      // 定义一个栈,用于存储数据
      const stack = [root]
      while (stack.length) {
        const node = stack.pop()
        console.log(node.val)
        /* 由于栈存在先入后出的特性,所以需要先入右子树才能保证先出左子树 */
        node.right && stack.push(node.right)
        node.left && stack.push(node.left)
      }
    }
    preorder(bt)
    /** 结果
    A B D E C F H I G
    */

    中序遍历

    二叉树的中序遍历实现思想如下:

    如下图所示:

    递归方式实现如下:

    const bt = require('./tree')
    
    // 递归版
    function inorder(root) {
      if (!root) return
      inorder(root.left)
      console.log(root.val)
      inorder(root.right)
    }
    inorder(bt)
    
    /** 结果
    D B E A H F I C G
    */

    迭代方式实现如下:

    // 非递归版
    function inorder(root) {
      if (!root) return
      const stack = []
      // 定义一个指针
      let p = root
      // 如果栈中有数据或者p不是null,则继续遍历
      while (stack.length || p) {
        // 如果p存在则一致将p入栈并移动指针
        while (p) {
          // 将 p 入栈,并以移动指针
          stack.push(p)
          p = p.left
        }
    
        const node = stack.pop()
        console.log(node.val)
        p = node.right
      }
    }
    inorder(bt)
    /** 结果
    D B E A H F I C G
    */

    后序遍历

    二叉树的后序遍历实现思想如下:

    如下图所示:

    递归方式实现如下:

    const bt = require('./tree')
    
    // 递归版
    function postorder(root) {
      if (!root) return
      postorder(root.left)
      postorder(root.right)
      console.log(root.val)
    }
    postorder(bt)
    /** 结果
    D E B H I F G C A
    */

    迭代方式实现如下:

    // 非递归版
    function postorder(root) {
      if (!root) return
      const outputStack = []
      const stack = [root]
      while (stack.length) {
        const node = stack.pop()
        outputStack.push(node)
        // 这里先入left需要保证left后出,在stack中后出,就是在outputStack栈中先出
        node.left && stack.push(node.left)
        node.right && stack.push(node.right)
      }
      while (outputStack.length) {
        const node = outputStack.pop()
        console.log(node.val)
      }
    }
    postorder(bt)
    /** 结果
    D E B H I F G C A
    */

    【相关推荐:javascript视频教程web前端

    以上就是详细介绍JavaScript二叉树及各种遍历算法的详细内容,更多请关注php中文网其它相关文章!

    声明:本文转载于:脚本之家,如有侵犯,请联系admin@php.cn删除
    专题推荐:javascript
    上一篇:怎么使用pkg将Node.js项目打包为可执行文件? 下一篇:JavaScript字典与集合(总结分享)
    VIP课程(WEB全栈开发)

    相关文章推荐

    • 【活动】充值PHP中文网VIP即送云服务器• 详细介绍JavaScript中Promise的基本概念及使用方法• 浅显易懂的JavaScript引入• 详细了解JavaScript编译原理• 简单介绍JavaScript “原型“与“原型链“• 万字图解JavaScript笔记总结
    1/1

    PHP中文网