专栏首页趣谈前端js中的二叉树以及二叉搜索树的实现及应用

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算法和数据结构,可以长按关注哦~

更多推荐

趣谈前端

Vue、React、小程序、Node

前端 算法|性能|架构|安全

本文分享自微信公众号 - 趣谈前端(beautifulFront),作者:徐小夕

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-08-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • javascript进阶必备的二叉树知识

    每当放完小长假,我都会习惯性的反思和复盘一下自己的技术,尤其是端午节。为什么我会写二叉树的文章呢?其实这涉及到程序员的一个成长性的问题。对于0-3年的前端程序员...

    徐小夕
  • 复盘node项目中遇到的13+常见问题和解决方案

    笔者之前陆陆续续接手过几个nodejs项目, 也参与过几个有点意思的nodejs开源项目, 最近把其中遇到的一些问题和解决方案做一个梳理, 避免大家继续踩坑. ...

    徐小夕
  • 《前端5分钟》之使用解释器模式实现获取元素Xpath路径的算法

    定义听起来可能比较抽象,举个例子比如我们常见的网站多语言,要实现多语言我们首先要预定语言的类型,提前设计不同语言的语料库,然后我们会根据配置和统一的变量...

    徐小夕
  • javascript进阶必备的二叉树知识

    每当放完小长假,我都会习惯性的反思和复盘一下自己的技术,尤其是端午节。为什么我会写二叉树的文章呢?其实这涉及到程序员的一个成长性的问题。对于0-3年的前端程序员...

    徐小夕
  • php实现映射操作实例详解

    映射,或者射影,在数学及相关的领域经常等同于函数。基于此,部分映射就相当于部分函数,而完全映射相当于完全函数。

    砸漏
  • 用js来实现那些数据结构13(树01-二叉搜索树的实现)

      前一篇文章我们学会了第一个非顺序数据结构hashMap,那么这一篇我们来学学树,包括树的概念和一些相关的术语以及二叉搜索树的实现。唉?为什么不是树的实现,不...

    zaking
  • winform如何保持TreeView节点展开和折叠的状态

    转载:http://blog.sina.com.cn/s/blog_6abcacf5010138q5.html

    跟着阿笨一起玩NET
  • AVL树探秘

    一、AVL树   AVL树是一种平衡查找树,在前面的两篇文章:二叉搜索树 和 红黑树 中都提到过。由于二叉搜索树在某些特殊情况下是不平衡的(任意一个结点深度过大...

    猿大白
  • 【剑指offer:两个链表的第一个公共节点】双解法

    题目提示了,空间复杂度可以降低到$O(1)$。这时候不能用哈希表,可以使用快慢指针的思路来处理。整体思路如下:

    心谭博客
  • 二叉查找树

    二叉查找树是一种数据结构,它是具有以下性质的二叉树: 1.若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值; 2.若右子数不空,则右子树上所有...

    小飞侠xp

扫码关注云+社区

领取腾讯云代金券