javascript进阶必备的二叉树知识

徐小夕 等级 604 0 0

前言

每当放完小长假,我都会习惯性的反思和复盘一下自己的技术,尤其是端午节。为什么我会写二叉树的文章呢?其实这涉及到程序员的一个成长性的问题。对于0-3年前端程序员来说,可能很少有机会涉及到数据结构和算法的工作中,除非去大厂或者做架构相关的工作。但是很多工作2-3年的前端工程师,业务工作已经相对熟悉了,各种技术或多或少也都使用过,那么在这个阶段,对于每个有追求的程序员,是不是应该突破一下自己的技术瓶颈,去研究一些更深层次的知识呢?没错,这个阶段我们最应该了解的就是数据结构算法设计模式相关的知识,设计模式算法笔者在之前的文章中已经系统的总结过了,感兴趣的可以学习了解一下。

接下来笔者就系统的总结一下二叉树相关的知识,并且通过实际代码一步步来带大家实现一个二叉搜索树

二叉树介绍

二叉树(Binary tree)是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树,且有左右之分javascript进阶必备的二叉树知识 二叉树中的节点最多只能有两个子节点:左侧子节点右侧子节点。我们接下来主要来实现一个二叉搜索树(BST)。它是二叉树的一种,但是只允许你在左侧节点存储比父节点小的值,在右侧节点存储比父节点大(或者等于)的值。如下图: javascript进阶必备的二叉树知识 接下来我们就一起实现一下BST树。

实现一个二叉搜索(BST)树

在实现之前,我们需要先分析一下BST(二叉搜索)树。我们要想构建一棵实用的树,我们需要节点方法,如下图所示: javascript进阶必备的二叉树知识 我们先实现一个基类,如下:

function BinarySearchTree() {
    let Node = function(key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }
    let root = null;
}

我们按照上图的二叉搜索树的结构组织方式,来实现二叉树的基本方法。

// 插入
this.insert = function(key) {
    let newNode = new Node(key);
    if(root === null) {
        root = newNode;
    }else {
        insertNode(root, newNode);
    }
}

其中insertNode方法用来判断在根节点不为空时的执行逻辑,具体代码如下:

function insertNode(node, newNode) {
    // 如果新节点值小于当前节点值,则插入左子节点
    if(newNode.key < node.key) {
        if(node.left === null) {
            node.left = newNode;
        }else{
            insertNode(node.left, newNode);
        }
    }else {
    // 如果新节点值大于当前节点值,则插入右子节点
        if(node.right === null) {
            node.right = newNode;
        }else {
            insertNode(node.right, newNode);
        }
    }
}

以上代码即实现了BST的插入部分逻辑,具体使用方式如下:

let tree = new BinarySearchTree()
tree.insert(19)
tree.insert(10)
tree.insert(20)

以上代码生成的二叉树结构如下: javascript进阶必备的二叉树知识

树的遍历

树的遍历是指访问树的每个节点并对它们进行某种操作的过程。具体分为中序遍历先序遍历后序遍历。接下来我会一一介绍给大家。

中序遍历

中序遍历是一种以从最小到最大的顺序访问所有节点的遍历方式,具体实现如下:

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)
    }
}

具体遍历过程如下图所示: javascript进阶必备的二叉树知识

先序遍历

先序遍历是以优先于后代节点的顺序访问每一个节点。具体实现如下:

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)
    }
}

具体遍历如下图所示: javascript进阶必备的二叉树知识

后序遍历

后序遍历是先访问节点的后代节点,再访问节点本身。。具体实现如下:

this.postOrderTraverse = function(cb) {
    preOrderTraverseNode(root, cb)
}

function postOrderTraverseNode(node, cb) {
    if(node !== null) {
        postOrderTraverseNode(node.left, cb)
        postOrderTraverseNode(node.right, cb)
        cb(node.key)
    }
}

具体遍历顺序如下图所示: javascript进阶必备的二叉树知识

树的搜索

我们一般的搜索会有最值搜索(也就是最大值,最小值,中值)和对特定值的搜索,接下来我们就来实现它们。

搜索特定的值

在BST树中搜索特定的值,具体实现如下:

this.search = function(key) {
    return searchNode(root, key)
}

function searchNode(ndoe, 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
    }
}

实现逻辑也很简单,这里大家可以研究一下。

搜索最小值

由二叉树的结构特征我们可以发现,二叉树的最左端就是最小值,二叉树的最右端就是最大值,所以我们可以通过遍历来找到最小值,代码如下:

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
}

移除节点

移除BST中的节点相对来说比较复杂,需要考虑很多情况,具体情况如下:

  1. 移除一个叶节点 javascript进阶必备的二叉树知识
  2. 移除有一个左侧或右侧子节点的节点 javascript进阶必备的二叉树知识
  3. 移除有两个子节点的节点 javascript进阶必备的二叉树知识

了解了上述3种情况之后我们开始实现删除节点的逻辑:

this.remove = function(key) {
    root = removeNode(root, key)
}

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
    }
}

function findMinNode(node) {
    if(node) {
        while(node && node.left !== null) {
            node = node.left;
        }
        return node
    }
    return null
}

至此,一棵完整的搜索二叉树就实现了,是不是很有成就感呢?本文的源码以上传至笔者的github,感兴趣的朋友可以感受一下。

二叉树的应用

二叉树一般可以用来:

  • 生成树结构
  • 数据库的搜索算法
  • 利用二叉树加密
  • 计算目录和子目录中所有文件的大小,
  • 打印一个结构化的文档
  • 在游戏中用来做路径规划等

扩展

其实的类型还有很多种,这些不同类型的树在计算机中有很广泛的用途,比如红黑树B树自平衡二叉查找树空间划分树散列树希尔伯特R树等,如果对这些树敢兴趣的朋友可以深入研究一下,毕竟对自己未来的技术视野还是很有帮助的。

最后

如果想学习更多前端技能,实战学习路线, 欢迎在公众号《趣谈前端》加入我们的技术群一起学习讨论,共同探索前端的边界。 javascript进阶必备的二叉树知识

参考文献

二叉树 - https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%A0%91

更多推荐

收藏
评论区

相关推荐

What the f*ck JavaScript?
What the fck JavaScript? 一个有趣和棘手的 JavaScript 示例列表。 JavaScript 是一种很好的语言。
javascript实践教程-01-javascript介绍
本节目标1. 了解javascript是什么。2. 了解javascript能干什么。 内容摘要本篇介绍了javascript是什么,为什么要用javascript,ECMAScript标准是什么等。阅读时间大约510分钟。 javascript是什么?javascript是世界上最流行的脚本语言,因为你在电脑、手机、平板上浏览的所有的网页,以及无数基于HT
JS的另类写法(书签栏工具原型)
<script type="text/javascript"> javascript : void (function(version) { var scriptTag = document.createElement('script'); scriptTag.type = 'text/javascript';
Console Api 让 JS 调试更简单、高效
> 所有Console Api  <script type="text/javascript"> console.dir(console); </script> ![](https://oscimg.oschina.net/oscnet/95a860f3d4ec5a09ee3f53761b64594745e.jpg)
Fundebug前端异常监控插件兼容低版本的Android浏览器
![](https://image.fundebug.com/2019-06-03-fundebug-javascript-upgrade.jpg) ### Fundebug前端BUG监控服务 [Fundebug](https://www.oschina.net/action/GoToLink?url=https%3A%2F%2Fwww.fundebug
JavaScript 踩坑心得— 为了高速(下)
#####**一.前言** 本文的上一篇 [JavaScript 踩坑心得— 为了高速(上)](https://www.oschina.net/action/GoToLink?url=http%3A%2F%2Fnews.oneapm.com%2Fbi-javascript%2F) 主要和大家分享的是 JavaScript 使用过程中的基本原则以及编写过程中的
JavaScript 非常重要的几个概念
JavaScript是一门比较复杂的语言。如果你是一名JavaScript开发人员,不管处于什么样的水平,都有必要了解JavaScript的基本概念。小编最近的工作涉及到JavaScript,于是本文就介绍了几个非常重要的 JavaScript 概念,但绝对不是说JavaScript 开发人员只需要知道这些就可以了。 01-变量赋值(值与引用) Java
JavaScript动画实例:李萨如曲线
        在“[JavaScript图形实例:阿基米德螺线](https://www.oschina.net/action/GoToLink?url=https%3A%2F%2Fwenku.baidu.com%2Fview%2F5c4a2dfb152ded630b1c59eef8c75fbfc77d94cf)”和“[JavaScript图形实例:曲线方
JavaScript在物联网中的应用
> 凡是能用JavaScript写出来的,最终都会用JavaScript写出来。 —— Atwood定律 在那篇《[最流行的编程语言JavaScript能做什么?](https://www.oschina.net/action/GoToLink?url=http%3A%2F%2Fmp.weixin.qq.com%2Fs%3F__biz%3DMjM5Mjg
JavaScript基础系列
![JavaScript基础系列](https://oscimg.oschina.net/oscnet/c1dc2f84f95d13105d79ba82a648f0c5eab.png) > JavaScript基础系列 ![image.png](https://oscimg.oschina.net/oscnet/e16bf4232aab0acb21c56
JavaScript的 基本数据类型
**第一:Javascript对象是** **第二:Javascript中** **第三:Javascript的对象是数据;** **第四:JavaScript 中的对象可以简单理解成"名称:值"对(name:value)。名称(name):"名称"部分是一个 JavaScript 字符串** **参考----------https://www
Javascript相关学习
JavaScript ---------- 发现了一个不错的学习JavaScript的网站,就是MDN,具体见[JavaScript 参考](https://www.oschina.net/action/GoToLink?url=https%3A%2F%2Fdeveloper.mozilla.org%2Fzh-CN%2Fdocs%2FWeb%2FJavaS
Node.js简介及如何学习Node.js
本文介绍Node.js的诞生史以及如何学习Node.js。 Node.js简史 --------- 从Node.js的命名上可以看到,Node.js的官方开发语言是JavaScript。之所以选择使用JavaScript,显然与JavaScript的开发人员多有关。总所周知,JavaScript是伴随着互联网的发展而火爆起来的,JavaScript也是前
PhotoShop脚本指南
**Photoshop脚本语言** Photoshop支持三种脚本语言:AppleScript,VBScript,JavaScript。其中AppleScript为苹果系统,VBScript为Windows操作系统,JavaScript兼容苹果和Windows操作系统。 ![](https://oscimg.oschina.net/oscnet/up-2
Python 与 Javascript 之比较
最近由于工作的需要开始开发一些Python的东西,由于之前一直在使用Javascript,所以会不自觉的使用一些Javascript的概念,语法什么的,经常掉到坑里。我觉得对于从Javascript转到Python,有必要总结一下它们之间的差异。 ### **基本概念** [Python](https://www.oschina.net/action/G