当前位置:

首页 > 系统应用 > 前端:JavaScript中的二叉树算法实现

前端:JavaScript中的二叉树算法实现

圣诞快乐接下来,咱们一起深入探讨一下js数据结构中的树。其实呀,这里的树和现实生活中的树很相似,都有树干、树枝。而在程序里,树可是一种非常重要的数据结构哦,对于存储那些需要快速查找的数据来说,它简直太有用啦!它是一种分层数据的抽象模型。一个树结构包含了一系列具有父子关系的节点。每个节点都有一个父节点

本文目录


    圣

    诞

    快

    乐

    接下来,咱们一起深入探讨一下js数据结构中的树。其实呀,这里的树和现实生活中的树很相似,都有树干、树枝。而在程序里,树可是一种非常重要的数据结构哦,对于存储那些需要快速查找的数据来说,它简直太有用啦!它是一种分层数据的抽象模型。一个树结构包含了一系列具有父子关系的节点。每个节点都有一个父节点,同时还可能有零个或者多个子节点。就像下面这样的一个树结构:)

    和树相关的概念:1.子树:由节点和他的后代构成,如上图标示处。2.深度:节点的深度取决于它祖节点的数量,比如节点5有2个祖节点,他的深度为2。3.高度:树的高度取决于所有节点深度的最大值。

    二叉树和二叉搜索树介绍

    二叉树中的节点最多只能有2个子节点,一个是左侧子节点,一个是右侧子节点,这样定义的好处是有利于我们写出更高效的插入,查找,删除节点的算法。二叉搜索树是二叉树的一种,但是它只允许你在左侧子节点存储比父节点小的值,但在右侧节点存储比父节点大的值。接下来我们将按照这个思路去实现一个二叉搜索树。

    1. 创建BinarySearchTree类

    这里我们将使用构造函数去创建一个类:
    function BinarySearchTree(){
    // 用于创建节点的类
    let Node = function(key) {
    this.key = key;
    this.left = null;
    this.right = null;
    }
    // 根节点
    let root = null;
    }

    我们将使用和链表类似的指针方式去表示节点之间的关系,如果不了解链表,请看我后序的文章《如何实现单向链表和双向链表》。

    2.插入一个键

    // 插入一个键
    this.insert = function(key) {
    let newNode = new Node(key);
    root === null ? (root = newNode) : (insertNode(root, newNode))
    }

    向树中插入一个新的节点主要有以下三部分:1.创建新节点的Node类实例 --> 2.判断插入操作是否为根节点,是根节点就将其指向根节点 --> 3.将节点加入非根节点的其他位置。

    insertNode的具体实现如下:

    function insertNode(node, newNode){
    if(newNode.key < node.key) {
    node.left === null ? (node.left = newNode) : (insertNode(node.left, newNode))
    }else {
    node.right === null ? (node.right = newNode) : (insertNode(node.right, newNode))
    }
    }

    这里我们用到递归,接下来要实现的search,del等都会大量使用递归,所以说不了解的可以先自行学习了解。我们创建一个二叉树实例,来插入一个键:

    let tree = new BinarySearchTree();
    tree.insert(20);
    tree.insert(21);
    tree.insert(520);
    tree.insert(521);
    插入的结构会按照二叉搜索树的规则去插入,结构类似于上文的第一个树图。

    树的遍历

    访问树的所有节点有三种遍历方式:中序,先序和后序。
    • 中序遍历:以从最小到最大的顺序访问所有节点
    • 先序遍历:以优先于后代节点的顺序访问每个节点
    • 后序遍历:先访问节点的后代节点再访问节点本身
    根据以上的介绍,我们可以有以下的实现代码。
    1. 中序排序
    this.inOrderTraverse = function(cb){
    inOrderTraverseNode(root, cb);
    }

    // 辅助函数
    function inOrderTraverseNode(node, cb){
    if(node !== null){
    inOrderTraverseNode(node.left, cb);
    cb(node.key);
    inOrderTraverseNode(node.right, cb);
    }
    }
    使用中序遍历可以实现对树进行从小到大排序的功能。
    1. 先序排序
    // 先序排序 --- 优先于后代节点的顺序访问每个节点
    this.preOrderTraverse = function(cb) {
    preOrderTraverseNode(root, cb);
    }

    // 先序排序辅助方法
    function preOrderTraverseNode(node, cb) {
    if(node !== null) {
    cb(node.key);
    preOrderTraverseNode(node.left, cb);
    preOrderTraverseNode(node.right, cb);
    }
    }
    使用先序排序可以实现结构化输出的功能。
    1. 后序排序
    // 后续遍历 --- 先访问后代节点,再访问节点本身
    this.postOrderTraverse = function(cb) {
    postOrderTraverseNode(root, cb);
    }

    // 后续遍历辅助方法
    function postOrderTraverseNode(node, cb) {
    if(node !== null){
    postOrderTraverseNode(node.left, cb);
    postOrderTraverseNode(node.right, cb);
    cb(node.key);
    }
    }
    后序遍历可以用于计算有层级关系的所有元素的大小。

    搜索树中的值

    在树中有三种经常执行的搜索类型:最大值,最小值,特定的值。
    1. 最小值
    最小值通过定义可以知道即是左侧树的最底端的节点,具体实现代码如下:
    // 最小值
    this.min = function(){
    return minNode(root)
    }

    function minNode(node) {
    if(node) {
    while(node && node.left !== null){
    node = node.left;
    }
    return node.key
    }
    return null
    }
    相似的,实现最大值的方法如下:
    // 最大值
    this.max = function() {
    return maxNode(root)
    }

    function maxNode(node) {
    if(node){
    while(node && node.right !== null){
    node = node.right;
    }
    return node.key
    }
    return null
    }
    2.搜索一个特定的值
    // 搜索树中某个值
    this.search = function(key) {
    return searchNode(root, key)
    }

    // 搜索辅助方法
    function searchNode(node, key){
    if(node === null) {
    return false
    }
    if(key < node.key) {
    return searchNode(node.left, key)
    } else if(key > node.key) {
    return searchNode(node.right, key)
    }else {
    return true
    }
    }
    1. 移除一个节点
    this.remove = function(key){
    root = removeNode(root, key);
    }

    // 发现最小节点
    function findMinNode(node) {
    if(node) {
    while(node && node.left !== null){
    node = node.left;
    }
    return node
    }
    return null
    }

    // 移除节点辅助方法
    function removeNode(node, key) {
    if(node === null) {
    return null
    }

    if(key < node.key){
    node.left = removeNode(node.left, key);
    return node
    } else if( key > node.key){
    node.right = removeNode(node.right, key);
    return node
    } else {
    // 一个页节点
    if(node.left === null && node.right === null) {
    node = null;
    return node
    }

    // 只有一个子节点的节点
    if(node.left === null) {
    node = node.right;
    return node
    }else if(node.right === null) {
    node = node.left;
    return node
    }

    // 有两个子节点的节点
    let aux = findMinNode(node.right);
    node.key = aux.key;
    node.right = removeNode(node.right, aux.key);
    return node
    }
    }

    删除节点需要考虑的情况比较多,这里我们会使用和min类似的实现去写一个发现最小节点的函数,当要删除的节点有两个子节点时,我们要将当前要删除的节点替换为子节点中最大的一个节点的值,然后将这个子节点删除。

    至此,一个二叉搜索树已经实现,但是还存在一个问题,如果树的一遍非常深,将会存在一定的性能问题,为了解决这个问题,我们可以利用AVL树,一种自平衡二叉树,也就是说任何一个节点的左右两侧子树的高度之差最多为1。

    如果想学习更多js算法和数据结构,可以继续观看哦~

    点个在看,你最好看

    本文分享自微信公众号 - 趣谈前端(beautifulFront)。
    如有侵权,请联系 support@oschina.cn 删除。
    本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

    本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系bd@zhengruan.com
    作者最新文章
    系统应用 JavaScript
    相关文章 更多
    Modern Web Guidance 的 legacy-scan 反转建议应该怎样判断?
    Modern Web Guidance 的 legacy-scan 反转建议应该怎样判断?

    说明源码提交对字符串、生成器和数组的识别边界,以及扫描命令与发行包核验限制。

    JS中Math.round与toFixed实现四舍五入的区别
    JS中Math.round与toFixed实现四舍五入的区别

    深入解析JavaScript中Math.round与toFixed的核心差异:前者返回数字,后者返回字符串。揭示IEEE 754浮点数导致的1.005舍入错误,提供前端显示与后端结算的最佳实践方案,包括使用分为单位整数和decimal.js库。

    JS实现指定小数位标准四舍五入函数
    JS实现指定小数位标准四舍五入函数

    解决JavaScript中1.005四舍五入为1.00而非1.01的精度问题。深入分析IEEE 754双精度浮点数表示误差,提供健壮的roundTo函数实现,涵盖NaN、Infinity及负数处理。对比toFixed与自定义方案,明确显示与结算的场景边界,附带边界用例验证表。

    JS toFixed四舍五入不准的修正方法
    JS toFixed四舍五入不准的修正方法

    深入解析JavaScript中toFixed方法四舍五入不准确的根本原因,提供基于指数表示法与数字偏移的安全修正方案,并配有直观架构图与对比示例。

    JS刷新页面:location.reload()与location.href的核心区别
    JS刷新页面:location.reload()与location.href的核心区别

    详解JavaScript中location.reload()和location.href刷新页面的机制差异。对比两者在HTTP缓存验证、POST请求重复提交警告、浏览器历史记录栈行为上的不同,并提供绕过强缓存、处理Hash变化及避免死循环的实战代码示例。

    typescript是什么语言?一文看懂其定义与用途
    typescript是什么语言?一文看懂其定义与用途

    深入浅出解析TypeScript是什么语言。本文详细介绍TypeScript的语言定义、超集架构、核心运行原理、与JavaScript的核心对比以及四类典型工业级应用场景,帮助读者全面看懂TS的价值与用途。

    JS金额计算怎么避免四舍五入误差
    JS金额计算怎么避免四舍五入误差

    解决JavaScript中0.1+0.2!=0.3的精度问题。深入解析IEEE 754浮点数机制,对比展示用toFixed与结算用整数分计算的适用场景,提供decimal.js库的正确用法与验证方法,帮助开发者在电商与金融场景中实现精确的金额处理。

    uniapp网络请求拦截怎么办解决方法教程
    uniapp网络请求拦截怎么办解决方法教程

    学习如何在UniApp项目中封装网络请求拦截器,实现自动携带Token、统一错误处理和请求日志记录,提升代码维护效率。

    前端文件上传接口怎么传使用FormData提交文件教程
    前端文件上传接口怎么传使用FormData提交文件教程

    详解如何使用原生 JavaScript 和 FormData 对象实现前端文件上传,涵盖单文件、多文件提交及进度监听,无需依赖重型库,提升代码可控性。

    为什么vivo浏览器内核不支持某些最新的JavaScript语法?
    为什么vivo浏览器内核不支持某些最新的JavaScript语法?

    vivo浏览器因系统级冻结WebView内核,版本锁定在89.0.4389.105及以下,不支持可选链、逻辑赋值等ES2022+新语法。可通过chrome://version确认内核版本。临时方案:使用Babel转译代码,或改用KiwiBrowser、CometAI浏览器(自带Polyfill注入)。

    查看更多
    精品专题 更多
    装机必备
    装机必备

    正软商城装机必备专区,精选办公、浏览器、安全防护、影音播放、压缩解压、设计创作和系统工具等电脑常用正版软件,帮助用户快速完成新电脑软件配置。

    Windows
    Windows

    正软商城Windows软件专区,汇集适用于Windows电脑的办公、设计、安全防护、影音播放、开发工具和系统优化软件,提供软件介绍、系统要求、正版授权及购买下载服务。

    PDF教程
    PDF教程

    正软商城PDF教程频道提供PDF编辑、转换、合并、拆分、压缩及格式处理方法,同时介绍常用PDF软件和工具的使用技巧。

    Mac软件 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    Aperty macOS版
    Aperty macOS版
    macOS

    Aperty 是 Skylum 推出的 AI 人像修图软件,支持自然肤质修饰、瑕疵处理、面部与身体调整、预设及批量同步。

    WINDOWS 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    PixTV 网页版
    PixTV 网页版
    Windows

    PixTV 是一款在浏览器中使用的 AI 视觉内容创作平台,提供图片、视频、音频、文字生成、AI 分镜、局部重绘、提示词反推和无限画布等工具,适合短剧、漫剧、广告及社交媒体内容制作。