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

徐小夕 等级 767 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算法和数据结构,可以长按关注趣谈前端~

更多推荐

收藏
评论区

相关推荐

JavaScript 中的二叉树以及二叉搜索树的实现及应用
接下来让我们一起来探讨js数据结构中的树。这里的树类比现实生活中的树,有树干,树枝,在程序中树是一种数据结构,对于存储需要快速查找的数据非有用,它是一种分层数据的抽象模型。一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点以及零个或多个子节点。如下所以为一个树结构:) (https://imghelloworld.osscnbe
前端进阶之从零到一实现单向 & 双向链表
前言 前端工程师对于算法和数据结构这块的知识的掌握程度,是进阶高级工程师的非常重要的标志之一,为了总结一下数据结构和算法方面的知识,笔者今天继续把链表这一块的知识补上,也作为自己知识体系的一个梳理,笔者早在去年就写过一篇关于使用javascript实现二叉树和二叉搜索树的文章,如果感兴趣或者想进阶高级的朋友们可以参考学习一下: JavaScript 中的二
javascript进阶必备的二叉树知识
前言 每当放完小长假,我都会习惯性的反思和复盘一下自己的技术,尤其是端午节。为什么我会写二叉树的文章呢?其实这涉及到程序员的一个成长性的问题。对于03年的前端程序员来说,可能很少有机会涉及到数据结构和算法的工作中,除非去大厂或者做架构相关的工作。但是很多工作23年的前端工程师,业务工作已经相对熟悉了,各种技术或多或少也都使用过,那么在这个阶段,对于每个有
React之集成测试 – 测试概览
你可以用像测试其他 JavaScript 代码类似的方式测试 React 组件。现在有许多种测试 React 组件的方法。大体上可以被分为两类: 渲染组件树 在一个简化的测试环境中渲染组件树并对它们的输出做断言检查。 运行完整应用 在一个真实的浏览器环境中运行整个应用(也被称为“端到端(endtoend)”测试)。本章节主要专
手把手教你实现一个Vue无限级联树形表格(增删改)
前言平时我们可能在做项目时,会遇到一个业务逻辑。实现一个无限级联树形表格,什么叫做无限级联树形表格呢?就是下图所展示的内容,有一个祖元素,然后下面可能有很多子孙元素,你可以实现添加、编辑、删除这样几个功能。资源 JavaScript框架:vue.js UI框架:Element UI 源码这里需要重点说明的是,主要使用了递归的算法以及给数
DS博客作业05
#1.本周学习总结 ##1.思维导图 ![](https://oscimg.oschina.net/oscnet/7226aa2f8d9507a45bebcc4789d5f40ccee.png) ##2.谈谈你对树结构的认识及学习体会 相对于之前的栈和队列,树的学习难度明显. 相较于之前的线性结构, 树更多的需要应用递归思维. 循环结构用多了之后,
Jade模板引擎入门教程
Jade是一款高性能简洁易懂的模板引擎,Jade是Haml的Javascript实现,在服务端(NodeJS)及客户端均有支持。 功能 客户端支持 超强的可读性 灵活易用的缩进 块扩展 代码默认经过编码处理以增强安全性 编译及运行时的上下文错误报告 命令行编译支持 HTML5模式(使用!!!5文档类型) 可选的内存缓存 联合动态和静态标记类 利用过滤器解析树
Java实现 LeetCode 814 二叉树剪枝 (遍历树)
814\. 二叉树剪枝 ----------- 给定二叉树根结点 root ,此外树的每个结点的值要么是 0,要么是 1。 返回移除了所有不包含 1 的子树的原二叉树。 ( 节点 X 的子树为 X 本身,以及所有 X 的后代。) 示例1: 输入: \[1,null,0,0,1\] 输出: \[1,null,0,null,1\] 解释:
dtree详细资料
作者:diaoyf  |  文章来源:http://programmerdigest.cn dTree是一个免费的JavaScript树形菜单,使用简单,界面制作的也很专业。 dtree树形菜单 所谓“兵无常势,水无常形”,不同的项目需求,造成菜单树的各种变化,因此在介绍dTree的同时,本文着重讲述如何改造dTree,以达到为不同项目所用的目的。
Unity 行为树
**引言** 在代码里面动态的操作单颗行为树 以及 管理所有的行为树,也是一个很重要的事情。 * * * **一、操作单颗树** 这是我们项目里面,一个敌人绑定了行为树,自动创建的behavior tree 脚本。 ![](https://oscimg.oschina.net/oscnet/7da4eb8863129cc1a0a9461b2b
C语言实现的基于Huffman哈夫曼编码的数据压缩与解压缩
**实验目的** 了解文件的概念 掌握线性链表的插入、删除等算法 掌握Huffman树的概念及构造方法 掌握二叉树的存储结构及遍历算法 利用Huffman树及Huffman编码,掌握实现文件压缩的一般原理 **参考博文和源码下载地址:** [https://write-bug.com/article/1281.html](https://www
Eclipse更改默认字符集 设置UTF
#### eclipse 中UTF-8设置 1.windows->Preferences   打开"首选项"对话框; 2.然后,general->Workspace,右 侧Text file encoding,选择Other,改变为UTF-8。 3.Web->打开,把CSS、HTML、JSP、JavaScript、XML等设置为UTF-8。 或在这里
React的虚拟DOM
上一篇文章中,DOM树的信息可以用JavaScript对象来表示,反过来,可以根据这个用JavaScript对象表示的树结构来真正构建一颗DOM树。 用JavaScript对象表示DOM信息和结构,当状态变更的时候,重新渲染这个JavaScript的对象结构,当然这样做,其实并没有更新到真正的页面上。 但是可以用新渲染的对象树和旧的树进行对比,记录这两棵树
Springmvc异步上传文件
<script src="js/jquery.js" type="text/javascript"></script><script src="js/jquery.ext.js" type="text/javascript"></script><script src="js/jquery.form.js" type="text/javascript"
Vue diff 算法
一、虚拟 DOM (virtual dom) ----------------------   diff 算法首先要明确一个概念就是 diff 的对象是虚拟DOM(virtual dom),更新真实 DOM 是 diff 算法的结果。   注:virtual dom 可以看作是一个使用 JavaScript 模拟了 DOM结构 的树形结构,这个树结构包含