侯体宗的博客
  • 首页
  • Hyperf版
  • beego仿版
  • 人生(杂谈)
  • 技术
  • 关于我
  • 更多分类
    • 文件下载
    • 文字修仙
    • 中国象棋ai
    • 群聊
    • 九宫格抽奖
    • 拼图
    • 消消乐
    • 相册

前端实现tree(树型结构)

前端  /  管理员 发布于 8年前   317
目录
一、是什么
二、操作
前序遍历
中序遍历
后序遍历
层序遍历
三、总结
参考文献

tree

# 面试官:说说你对树的理解?相关的操作有哪些?

# 一、是什么

在计算机领域,树形数据结构是一类重要的非线性数据结构,可以表示数据之间一对多的关系。以树与二叉树最为常用,直观看来,树是以分支关系定义的层次结构

二叉树满足以下两个条件:

  • 本身是有序树
  • 树中包含的各个结点的不能超过 2,即只能是 0、1 或者 2

如下图,左侧的为二叉树,而右侧的因为头结点的子结点超过2,因此不属于二叉树:

同时,二叉树可以继续进行分类,分成了满二叉树和完成二叉树:

  • 满二叉树:如果二叉树中除了叶子结点,每个结点的度都为 2

  • 完成二叉树:如果二叉树中除去最后一层节点为满二叉树,且最后一层的结点依次从左到右分布

# 二、操作

关于二叉树的遍历,常见的有:

  • 前序遍历

  • 中序遍历

  • 后序遍历

  • 层序遍历

# 前序遍历

前序遍历的实现思想是:

  • 访问根节点
  • 访问当前节点的左子树
  • 若当前节点无左子树,则访问当前节点的右子

根据遍历特性,递归版本用代码表示则如下:

const preOrder = (root) => {
  if(!root){ return }
  console.log(root)
  preOrder(root.left)
  preOrder(root.right)
}

如果不使用递归版本,可以借助栈先进后出的特性实现,先将根节点压入栈,再分别压入右节点和左节点,直到栈中没有元素,如下:

const preOrder = (root) => {
  if(!root){ return }
  const stack = [root]
  while (stack.length) {
    const n = stack.pop()
    console.log(n.val)
    if (n.right) {
      stack.push(n.right)
    }
    if (n.left) {
      stack.push(n.left)
    }
  }
}

# 中序遍历

前序遍历的实现思想是:

  • 访问当前节点的左子树
  • 访问根节点
  • 访问当前节点的右子

递归版本很好理解,用代码表示则如下:

const inOrder = (root) => {
  if (!root) { return }
  inOrder(root.left)
  console.log(root.val)
  inOrder(root.right)
}

非递归版本也是借助栈先进后出的特性,可以一直首先一直压入节点的左元素,当左节点没有后,才开始进行出栈操作,压入右节点,然后有依次压入左节点,如下:

const inOrder = (root) => {
  if (!root) { return }
  const stack = [root]
  let p = root
  while(stack.length || p){
    while (p) {
      stack.push(p)
      p = p.left
    }
    const n = stack.pop()
    console.log(n.val)
    p = n.right
  }
}

# 后序遍历

前序遍历的实现思想是:

  • 访问当前节点的左子树
  • 访问当前节点的右子
  • 访问根节点

递归版本,用代码表示则如下:

const postOrder = (root) => {
  if (!root) { return }
  postOrder(root.left)
  postOrder(root.right)
  console.log(n.val)
 }

后序遍历非递归版本实际根全序遍历是逆序关系,可以再多创建一个栈用来进行输出,如下:

const preOrder = (root) => {
  if(!root){ return }
  const stack = [root]
  const outPut = []
  while (stack.length) {
    const n = stack.pop()
    outPut.push(n.val)
    if (n.right) {
      stack.push(n.right)
    }
    if (n.left) {
      stack.push(n.left)
    }
  }
  while (outPut.length) {
    const n = outPut.pop()
    console.log(n.val)
  }
}

# 层序遍历

按照二叉树中的层次从左到右依次遍历每层中的结点

借助队列先进先出的特性,从树的根结点开始,依次将其左孩子和右孩子入队。而后每次队列中一个结点出队,都将其左孩子和右孩子入队,直到树中所有结点都出队,出队结点的先后顺序就是层次遍历的最终结果

用代码表示则如下:

const levelOrder = (root) => {
    if (!root) { return [] }
    const queue = [[root, 0]]
    const res = []
    while (queue.length) {
        const n = queue.shift()
        const [node, leval] = n
        if (!res[leval]) {
            res[leval] = [node.val]
        } else {
            res[leval].push(node.val)
        }
        if (node.left) { queue.push([node.left, leval + 1]) }
        if (node.right) { queue.push([node.right, leval + 1]) }
    }
    return res
};

# 三、总结

树是一个非常重要的非线性结构,其中二叉树以二叉树最常见,二叉树的遍历方式可以分成前序遍历、中序遍历、后序遍历

同时,二叉树又分成了完成二叉树和满二叉树

# 参考文献

  • https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%A0%91
  • http://data.biancheng.net/view/27.html

  • 上一条:
    前端实现时间与空间复杂度浅析
    下一条:
    WebView_jscore微信小程序的实现原理浅析
  • 昵称:

    邮箱:

    0条评论 (评论内容有缓存机制,请悉知!)
    最新最热
    • 分类目录
    • 人生(杂谈)
    • 技术
    • linux
    • Java
    • php
    • 框架(架构)
    • 前端
    • ThinkPHP
    • 数据库
    • 微信(小程序)
    • Laravel
    • Redis
    • Docker
    • Go
    • swoole
    • Windows
    • Python
    • 苹果(mac/ios)
    • 相关文章
    • 使用 Alpine.js 排序插件对元素进行排序(0个评论)
    • 在js中使用jszip + file-saver实现批量下载OSS文件功能示例(0个评论)
    • 在vue中实现父页面按钮显示子组件中的el-dialog效果(0个评论)
    • 使用mock-server实现模拟接口对接流程步骤(0个评论)
    • vue项目打包程序实现把项目打包成一个exe可执行程序(0个评论)
    • 近期文章
    • 在go语言中使用api.geonames.org接口实现根据国际邮政编码获取地址信息功能(1个评论)
    • 在go语言中使用github.com/signintech/gopdf实现生成pdf分页文件功能(0个评论)
    • gmail发邮件报错:534 5.7.9 Application-specific password required...解决方案(0个评论)
    • 欧盟关于强迫劳动的规定的官方举报渠道及官方举报网站(0个评论)
    • 在go语言中使用github.com/signintech/gopdf实现生成pdf文件功能(0个评论)
    • Laravel从Accel获得5700万美元A轮融资(0个评论)
    • 在go + gin中gorm实现指定搜索/区间搜索分页列表功能接口实例(0个评论)
    • 在go语言中实现IP/CIDR的ip和netmask互转及IP段形式互转及ip是否存在IP/CIDR(0个评论)
    • PHP 8.4 Alpha 1现已发布!(0个评论)
    • Laravel 11.15版本发布 - Eloquent Builder中添加的泛型(0个评论)
    • 近期评论
    • 122 在

      学历:一种延缓就业设计,生活需求下的权衡之选中评论 工作几年后,报名考研了,到现在还没认真学习备考,迷茫中。作为一名北漂互联网打工人..
    • 123 在

      Clash for Windows作者删库跑路了,github已404中评论 按理说只要你在国内,所有的流量进出都在监控范围内,不管你怎么隐藏也没用,想搞你分..
    • 原梓番博客 在

      在Laravel框架中使用模型Model分表最简单的方法中评论 好久好久都没看友情链接申请了,今天刚看,已经添加。..
    • 博主 在

      佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 @1111老铁这个不行了,可以看看近期评论的其他文章..
    • 1111 在

      佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 网站不能打开,博主百忙中能否发个APP下载链接,佛跳墙或极光..
    • 2016-10
    • 2016-11
    • 2017-06
    • 2017-07
    • 2017-08
    • 2017-09
    • 2017-10
    • 2017-11
    • 2018-03
    • 2018-04
    • 2018-05
    • 2018-06
    • 2018-09
    • 2018-11
    • 2018-12
    • 2019-02
    • 2020-03
    • 2020-04
    • 2020-05
    • 2020-06
    • 2021-04
    • 2021-05
    • 2021-07
    • 2021-08
    • 2021-09
    • 2021-10
    • 2021-11
    • 2022-08
    • 2022-09
    • 2022-10
    • 2022-11
    • 2022-12
    • 2023-01
    • 2023-02
    • 2023-03
    • 2023-04
    • 2023-05
    • 2023-06
    • 2023-07
    • 2023-09
    • 2023-10
    • 2023-11
    • 2023-12
    • 2024-01
    • 2024-02
    • 2024-03
    • 2024-04
    Top

    Copyright·© 2019 侯体宗版权所有· 粤ICP备20027696号 PHP交流群

    侯体宗的博客