前端中常见数据结构小结

常见数据结构的 JavaScript 实现系列

前端与数据结构

数据结构在开发中是一种编程思想的提炼,无关于用何种语言开发或者是哪种端开发。下列将笔者涉猎到的与前端相关的数据结构案例作如下总结:

数据结构

案例

FILO: 其它数据结构的基础,redux/koa2 中间件机制

队列

FIFO:其它数据结构的基础

链表

React 16 中的 Fiber 的优化

集合

对应 JavaScript 中的 Set

字典

对应 JavaScript 中的 Map

哈希表

一种特殊的字典,可以用来存储加密数据

DOM TREE / HTML TREE / CSS TREE

暂时没遇到,不过里面的 BFS/DFS 蛮常见

下文为增加字数,挑了篇上述的二叉树章节(字数太少不能发布),欢迎阅读原文。

二叉树

这幅图中有如下概念:

  • 根节点:一棵树最顶部的节点
  • 内部节点:在它上面还有其它内部节点或者叶节点的节点
  • 叶节点:处于一棵树根部的节点
  • 子树:由树中的内部节点和叶节点组成

此外这棵树是二叉树(树中最多有两个分支),同时它也是二叉搜索树(左侧子节点的数字小于父节点,右侧子节点的数字大于父节点)

二叉搜索树的实现

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

  let root = null

  // 插入元素
  // 实现思路:至顶向下插入,先判断顶点是否为空;顶点为空则直接在该处插入,若不为空,则通过比较顶点的 key 和插入元素的 key 判断该插入到顶点的左侧还是右侧,后面进行如上递归
  this.insert = function(key) {
    const node = new Node(key)
    if (root === null) {
      root = node
    } else {
      insertNode(root, node)
    }
    function insertNode(parent, node) {
      if (parent.key > node.key) {
        if (parent.left === null) {
          parent.left = node
        } else {
          insertNode(parent.left, node)
        }
      } else if (parent.key < node.key) {
        if (parent.right === null) {
          parent.right = node
        } else {
          insertNode(parent.right, node)
        }
      }
    }
  }

  // 中序遍历
  this.inOrderTraverse = function(cb) {
    inOrderTraverse(root, cb)
    function inOrderTraverse(node, cb) {
      if (node) {
        inOrderTraverse(node.left, cb)
        cb(node.key)
        inOrderTraverse(node.right, cb)
      }
    }
  }

  // 先序遍历
  this.preOrderTraverse = function(cb) {
    preOrderTraverse(root, cb)
    function preOrderTraverse(node, cb) {
      if (node) {
        cb(node.key)
        preOrderTraverse(node.left, cb)
        preOrderTraverse(node.right, cb)
      }
    }
  }

  // 后序遍历
  this.postOrderTraverse = function(cb) {
    postOrderTraverse(root, cb)
    function postOrderTraverse(node, cb) {
      if (node) {
        postOrderTraverse(node.left, cb)
        postOrderTraverse(node.right, cb)
        cb(node.key)
      }
    }
  }

  // 最大值:思路最右边
  this.max = function() {
    let maxResult = {}
    function getMax(node) {
      if (node && node.right) {
        maxResult = node.right
        getMax(node.right)
      }
    }
    getMax(root)
    return maxResult.key
  }

  // 最小值:思路最左边
  this.min = function() {
    let minResult = {}
    function getMin(node) {
      if (node && node.left) {
        minResult = node.left
        getMin(node.left)
      }
    }
    getMin(root)
    return minResult.key
  }

  // 查找指定元素
  this.search = function(key) {
    const searchKey = function(node) {
      if (!node) {
        return false
      }
      if (key > node.key) {
        return searchKey(node.right)
      } else if (key < node.key) {
        return searchKey(node.left)
      } else {
        return true
      }
    }

    return searchKey(root)
  }

  // 移除指定 key 值
  this.remove = function(key) {
    const removeKey = function(node, key) {
      if (key < node.key) {         // ① 如果 key 值在传入节点的左边
        node.left = removeKey(node.left, key)
        return node
      } else if (key > node.key) {  // ② 如果 key 值在传入节点的右边
        node.right = removeKey(node.right, key)
        return node
      } else {                      // ③ 如果找到了 key 值
        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
        }
        const minNode = findMinNode(node.right)          // 删除的节点下有两个分支
        node.key = minNode.key
        node.right = removeKey(node.right, minNode.key)
        return node
      }
    }

    // 查找最小的节点
    const findMinNode = function(node) {
      if (node.left) {
        return findMinNode(node.left)
      } else {
        return node
      }
    }

    removeKey(root, key)
  }
}

var tree = new BinarySearchTree()
tree.insert(11)
tree.insert(7)
tree.insert(15)
tree.insert(5)
tree.insert(3)
tree.insert(9)
tree.insert(8)
tree.insert(10)
tree.insert(13)
tree.insert(12)
tree.insert(14)
tree.insert(20)
tree.insert(18)
tree.insert(25)
tree.insert(6)

三种遍历方式的不同

  • 中序遍历:可用于二叉搜索树的排序
  • 先序遍历:可用于打印结构化的文档
  • 后序遍历:可用于查看文件夹目录

三种遍历的实现方式大同小异,可在上面代码中观察到实现的差异。

remove 的几种情况

remove 方法是二叉查找树中相对复杂的实现。思路仍然是递归。

如果要删除的 key 在传入节点的左侧,则递归调用 removeKey(node.left, key);

如果要删除的 key 在传入节点的右侧,则递归调用 removeKey(node.right, key);

如果要删除的 key 与传入节点相等,有如下三种情况:

①:删除的节点为根节点

②:删除的节点下有一个分支

③:删除的节点下有两个分支

这里的思路是找到当前节点的右分支中最小的节点,然后将该节点代替当前节点,同时移除当前节点的右分支中最小的节点

测试用例

var tree = new BinarySearchTree()
tree.insert(11)
tree.insert(7)
tree.insert(15)
tree.insert(5)
tree.insert(3)
tree.insert(9)
tree.insert(8)
tree.insert(10)
tree.insert(13)
tree.insert(12)
tree.insert(14)
tree.insert(20)
tree.insert(18)
tree.insert(25)
tree.insert(6)

var cb = (key) => console.log(key)

tree.inOrderTraverse(cb)   // 中序遍历: 3 5 6 7 8 9 10 11 12 13 14 15 18 20 25
tree.preOrderTraverse(cb)  // 先序遍历:11 7 5 3 6 9 8 10 15 13 12 14 20 18 25
tree.postOrderTraverse(cb) // 后序遍历:3 6 5 8 10 9 7 12 14 13 18 25 20 15 11

tree.max() // 25
tree.max() // 3

tree.search(6) // true
tree.search(1) // false

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏阿杜的世界

Java并发-CopyOnWriteArrayList前言CopyOnWriteArrayList API例子1:插入(删除)数据的同时进行遍历例子2:不支持一边遍历一边删除结论参考资料

今天我们一起学习下java.util.concurrent并发包里的CopyOnWriteArrayList工具类。当有多个线程可能同时遍历、修改某个公共数组时...

15830
来自专栏java一日一条

关于Java集合的小抄

在尽可能短的篇幅里,将所有集合与并发集合的特征,实现方式,性能捋一遍。适合所有”精通Java”其实还不那么自信的人阅读。

7310
来自专栏小灰灰

Java容器篇小结之List自问自答

I. List篇 0. 什么是List 看到这个有点懵逼,一时还真不知道怎么解释,能让完全没有接触过的人都能听懂 列表,什么是列表呢? 好比你到了一个村里,看...

22580
来自专栏Java工程师日常干货

对HashMap的思考及手写实现前言对HashMap的思考通过写一个迷你版的HashMap来深刻理解

HashMap是Java中常用的集合,而且HashMap的一些思想,对于我们平时解决业务上的一些问题,在思路上有帮助,基于此,本篇博客将分析HashMap底层设...

10420
来自专栏面朝大海春暖花开

oracle递归查询

这个子句主要是用于B树结构类型的数据递归查询,给出B树结构类型中的任意一个结点,遍历其最终父结点或者子结点。

49230
来自专栏微信公众号:Java团长

对HashMap的思考及手写实现

HashMap是Java中常用的集合,而且HashMap的一些思想,对于我们平时解决业务上的一些问题,在思路上有帮助,基于此,本篇博客将分析HashMap底层设...

9910
来自专栏岑玉海

hbase源码系列(五)Trie单词查找树

  在上一章中提到了编码压缩,讲了一个简单的DataBlockEncoding.PREFIX算法,它用的是前序编码压缩的算法,它搜索到时候,是全扫描的方式搜索的...

39580
来自专栏小灰灰

Java容器篇小结之Map自问自答

采用问答的方式对常见的问题进行整理小结 I. Map篇 0. 什么是Map 看到这个有点懵逼,一时还真不知道怎么解释,能让完全没有接触过的人都能听懂 想到生活...

206100
来自专栏codingforever

经典算法巡礼(七) -- 排序之堆排序

很多时候,我们需要处理有序的元素,但不一定要求它们全部有序,或是不一定要一次就将它们排序。比如你可能启动了若干个定时器,那么下一次处理定时器事件只需要考虑距离现...

8120
来自专栏calmound

Set Matrix Zeroes

问题:将数组中的某个值为0的元素所在行和列的其他值都为0 分析;遍历数组找到某一值为0然后遍历他的上下左右直到边界,要用while而不能用搜索,因为搜索过去新节...

34450

扫码关注云+社区

领取腾讯云代金券