JavaScript 中的二叉树以及二叉搜索树的实现及应用

徐小夕 等级 451 0 0

接下来让我们一起来探讨js数据结构中的树。这里的树类比现实生活中的树,有树干,树枝,在程序中树是一种数据结构,对于存储需要快速查找的数据非有用,它是一种分层数据的抽象模型。一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点以及零个或多个子节点。如下所以为一个树结构:)

JavaScript 中的二叉树以及二叉搜索树的实现及应用

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

二叉树和二叉搜索树介绍

二叉树中的节点最多只能有2个子节点,一个是左侧子节点,一个是右侧子节点,这样定义的好处是有利于我们写出更高效的插入,查找,删除节点的算法。

二叉搜索树是二叉树的一种,但是它只允许你在左侧子节点存储比父节点小的值,但在右侧节点存储比父节点大的值。接下来我们将按照这个思路去实现一个二叉搜索树。

JavaScript 中的二叉树以及二叉搜索树的实现及应用

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

使用中序遍历可以实现对树进行从小到大排序的功能。

2. 先序排序

``` js
// 先序排序 --- 优先于后代节点的顺序访问每个节点
   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算法和数据结构,可以长按关注趣谈前端~

更多推荐

收藏
评论区

相关推荐

前端学数据结构与算法:二叉树的四种遍历方式及其应用
前言 上一章我们从0到1的实现了一颗二叉搜索树,以及理解了二叉搜索树的特性与基本操作,这一章介绍关于二叉树的更多操作,也就是树的遍历,对树的每个节点进行访问。主要包括前序遍历、中序遍历、后序遍历、层序遍历,前面三种也叫深度优先遍历(DFS),最后的层序遍历也叫广度优先遍历(BFS),理解这四种遍历方式的不同,再遇到树相关的算法问题时,也就能更加游刃有余。这
JavaScript 中的二叉树以及二叉搜索树的实现及应用
接下来让我们一起来探讨js数据结构中的树。这里的树类比现实生活中的树,有树干,树枝,在程序中树是一种数据结构,对于存储需要快速查找的数据非有用,它是一种分层数据的抽象模型。一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点以及零个或多个子节点。如下所以为一个树结构:) (https://imghelloworld.osscnbe
如何优雅的使用javascript递归画一棵结构树
递归和尾递归 简单的说,递归就是函数自己调用自己,它做为一种算法在程序设计语言中广泛应用。其核心思想是把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的
《前端实战总结》之使用解释器模式实现获取元素Xpath路径的算法
前端领域里基于javascript的设计模式和算法有很多,在很多复杂应用中也扮演着很重要的角色,接下来就介绍一下javascript设计模式中的解释器模式,并用它来实现一个获取元素Xpath路径的算法。 上期回顾 《前端实战总结》之迭代器模式的N1种应用场景(https://juejin.im/post/6844904008616771591)
前端进阶之从零到一实现单向 & 双向链表
前言 前端工程师对于算法和数据结构这块的知识的掌握程度,是进阶高级工程师的非常重要的标志之一,为了总结一下数据结构和算法方面的知识,笔者今天继续把链表这一块的知识补上,也作为自己知识体系的一个梳理,笔者早在去年就写过一篇关于使用javascript实现二叉树和二叉搜索树的文章,如果感兴趣或者想进阶高级的朋友们可以参考学习一下: JavaScript 中的二
javascript进阶必备的二叉树知识
前言 每当放完小长假,我都会习惯性的反思和复盘一下自己的技术,尤其是端午节。为什么我会写二叉树的文章呢?其实这涉及到程序员的一个成长性的问题。对于03年的前端程序员来说,可能很少有机会涉及到数据结构和算法的工作中,除非去大厂或者做架构相关的工作。但是很多工作23年的前端工程师,业务工作已经相对熟悉了,各种技术或多或少也都使用过,那么在这个阶段,对于每个有
彻底搞懂系列B-树、B+树、B-树、B*树
(https://blog.csdn.net/chai471793/article/details/99563704)平衡二叉树 概念 平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树的数据结构; 特点 平衡二叉树是采用二分法思维把数据按规则组装成一个树形结构的数据,用这个树形结构的数据减少无关数据的检索,大大
算法笔记:B树
B树广泛应用于各种文件系统,文件系统中,数据都是按照数据块来进行读取操作。结合二叉树的优点和文件系统的特点,于是就有了B树: btree(https://imghelloworld.osscnbeijing.aliyuncs.com/imgs/ae3caa193bc4c55f0519114b15313721.png) B树当中每个节点存储
React之集成测试 – 测试概览
你可以用像测试其他 JavaScript 代码类似的方式测试 React 组件。现在有许多种测试 React 组件的方法。大体上可以被分为两类: 渲染组件树 在一个简化的测试环境中渲染组件树并对它们的输出做断言检查。 运行完整应用 在一个真实的浏览器环境中运行整个应用(也被称为“端到端(endtoend)”测试)。本章节主要专
【Flutter实战】布局类组件简介
4.1 布局类组件简介布局类组件都会包含一个或多个子组件,不同的布局类组件对子组件排版(layout)方式不同。我们在前面说过Element树才是最终的绘制树,Element树是通过Widget树来创建的(通过Widget.createElement()),Widget其实就是Element的配置数据。在Flutter中,根据Widget是否
二叉树创建后,如何使用递归和栈遍历二叉树?
0. 前言前文主要介绍了树的相关概念和原理,本文主要内容为二叉树的创建及遍历的代码实现,其中包括递归遍历和栈遍历。 1. 二叉树的实现思路 1.0. 顺序存储——数组实现前面介绍了满二叉树和完全二叉树,我们对其进行了编号——从 0 到 n 的不中断顺序编号,而恰好,数组也有一个这样的编号 —— 数组下标,只要我们把二者联合起来,数组就能存储二叉树了。那么非满
js实现二叉树、二叉查找树
树是一种数据结构,该章节讨论二叉树(二叉树的每个节点的子节点不允许超过两个),二叉树中有又分为完全二叉树和不完全二叉树..... 不在本章节赘述相关概念,感兴趣可以去查阅《数据结构》。 你将会获得: 1.如何使用js实现二叉查找树。 2.学会前、中、后序遍历。 3.了解相关实现原理 阅读时长5min,可选择直接调试代码 特点    二叉查找树中序遍历后
动图图解二叉查找树的基本原理及其实现
本文为系列专题的第 12 篇文章。1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 1. 是什么?二叉查找树(Binary Search Tree)必须满足以下特点: 若左子树不为空,则左子树的所有结点值皆小于根结点值 若右子树不为空,则右子树的所有结点值皆大于根结点值 左右子树也是二叉排序树如下图,是一颗二叉查找树:如果你对二叉查找树进行中序
手把手教你实现一个Vue无限级联树形表格(增删改)
前言平时我们可能在做项目时,会遇到一个业务逻辑。实现一个无限级联树形表格,什么叫做无限级联树形表格呢?就是下图所展示的内容,有一个祖元素,然后下面可能有很多子孙元素,你可以实现添加、编辑、删除这样几个功能。资源 JavaScript框架:vue.js UI框架:Element UI 源码这里需要重点说明的是,主要使用了递归的算法以及给数
高级java面试题,附答案+考点
蚂蚁金服一面1. 两分钟的自我介绍2. 二叉搜索树和平衡二叉树有什么关系,强平衡二叉树(AVL 树)和弱平衡二叉树 (红黑树)有什么区别3. B 树和 B+树的区别,为什么 MySQL 要使用 B+树4. HashMap 如何解决 Hash 冲突5. epoll 和 poll 的区别,及其应用场景6. 简述线程池原理,FixedThreadPoo