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

徐小夕
• 阅读 1495

接下来让我们一起来探讨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算法和数据结构,可以长按关注趣谈前端~

更多推荐

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
白茶清欢 白茶清欢
3年前
js实现二叉树、二叉查找树
树是一种数据结构,该章节讨论二叉树(二叉树的每个节点的子节点不允许超过两个),二叉树中有又分为完全二叉树和不完全二叉树.....不在本章节赘述相关概念,感兴趣可以去查阅《数据结构》。你将会获得:1.如何使用js实现二叉查找树。2.学会前、中、后序遍历。3.了解相关实现原理阅读时长5min,可选择直接调试代码特点    二叉查找树中序遍历后
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
3个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
3年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Wesley13 Wesley13
3年前
B
BTreeBTree又叫做B树,和平衡二叉树不同的地方在于B树是多叉树(平衡多路查找树),Oracle和MongoDB的索引技术就是基于B树的数据结构,B树也可以看作是对23查找树的一种扩展。一个m阶的BTree有以下性质1.每个节点最多有m个子节点;2.每个非叶子节点(根节点除外)至少含有m/2个子节点;3.
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
菜园前端 菜园前端
1年前
什么是二叉树?
原文链接:什么是二叉树?树中每个节点最多只能有两个子节点,在JavaScript中一般都是通过Object来模拟二叉树。常用操作前序遍历中序遍历后序遍历前序遍历根左右。口诀:1.访问根节点2.对根节点的左子树进行前序遍历3.对根节点的右子树进行前序遍历通过
Python进阶者 Python进阶者
9个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这