前端中常见数据结构小结

常见数据结构的 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