• 数据结构之数组
• 数据结构之队列
• 数据结构之栈
• 数据结构之链表
• 数据结构之树
• 数据结构之图

基础概念

1. 树是一种非顺序数据结构
2. 根节点是没有父节点的节点
3. 一个节点允许有祖先和后代
4. 节点的深度 = 祖先节点的个数 = 自身层数-1

通常我们指的树是二叉搜索树，这种树的特性是每个节点都只有两个子节点，且左子节点比父节点小，右子节点比父节点大。这种特性有助于我们在树中插入、删除和查找元素

JavaScript 构建一颗树

树的类有以下实例方法:

1. insert 插入节点
2. preOrderTraverse 先序遍历
3. inOrderTraverse 中序遍历
4. postOrderTraverse 后序遍历
5. min 查找并返回最小节点
6. max 查找并返回最大节点
7. has 查找树是否有某个节点
8. delete 移除节点

树的类有以下静态方法:

1. createNode 创建一个节点
2. traverse 遍历一棵树
3. minNode 查找一颗树的最小节点
4. maxNode 查找一颗树的最大节点

后面会补充各个方法

class BinarySearchTree {
  /**
   * 初始化有一个根节点
   */
  constructor(key) {
    this.root = BinarySearchTree.createNode(key)
  }

  /**
   * 插入节点
   * @param {Number} key 需要插入的节点的值
   */
  insert(key) {}

  /**
   * 先序遍历
   * @param {Function} callback 回调函数
   */
  preOrderTraverse(callback) {}

  /**
   * 中序遍历
   * @param {Function} callback 回调函数
   */
  inOrderTraverse(callback) {}

  /**
   * 后序遍历
   * @param {Function} callback 回调函数
   */
  postOrderTraverse(callback) {}

  /**
   * 查找并返回最小节点
   */
  mix() {}

  /**
   * 查找并返回最大节点
   */
  max() {}

  /**
   * 查找树是否有某个节点
   * @param {Number} key 需要查找的节点的值
   */
  has(key) {}

  /**
   * 移除节点
   * @param {Number} key 需要移除的节点的值
   */
  delete(key) {}

  /**
   * 创建一个节点
   * @param {Number} key 节点的值
   */
  static createNode(key) {}

  /**
   * 静态方法，遍历一棵树
   * @param {Node} root 树的根节点
   * @param {Number} type 遍历类型，1先序遍历，2中序遍历，3后序遍历
   * @param {Function} callback 回调函数，回调函数接受 key，leftKey，rightKey，node四个参数
   */
  static traverse(root, type, callback) {}

  /**
   * 查找一棵树的最小节点
   * @param {Node} root 树的根节点
   */
  static minNode(root) {}

  /**
   * 查找一棵树的最大节点
   * @param {Node} root 树的根节点
   */
  static maxNode(root) {}
}

插入节点

树的大部分方法的核心都是递归思想，插入节点比较简单，具体看代码注释。

class BinarySearchTree {
  // ...

  /**
   * 插入节点
   * @param {Number} key 需要插入的节点的值
   */
  insert(key) {
    // 初始化一个节点
    const newNode = BinarySearchTree.createNode(key)

    /**
     * 插入函数
     * @param {Node} curNode 当前节点
     * @param {Node} newNode 需要被插入的节点
     */
    const insertNode = function(curNode, newNode) {
      // 1. 如果要插入的节点比当前节点的值小，插入到当前节点的左边
      // 2. 如果要插入的节点比当前节点的值大，插入到当前节点的右边
      if (newNode.key < curNode.key) {
        // 1. 如果当前节点的左子节点不存在，则新节点就做为左子节点
        // 2. 否则就继续递归下去
        curNode.left === null ? (curNode.left = newNode) : insertNode(curNode.left, newNode)
      } else {
        // 1. 如果当前节点的右子节点不存在，则新节点就做为右子节点
        // 2. 否则就继续递归下去
        curNode.right === null ? (curNode.right = newNode) : insertNode(curNode.right, newNode)
      }
    }

    // 插入
    // 1. 如果插入的是根节点，则根节点为新插入的节点
    // 2. 如果插入的不是根节点，那么就执行插入函数
    this.root.key === null ? (this.root = newNode) : insertNode(this.root, newNode)
  }

  /**
   * 生成一个树节点
   * @param {Number} key 节点的值
   */
  static createNode(key) {
    key = key || null
    function Node(key) {
      this.key = key
      this.left = null
      this.right = null
    }
    return new Node(key)
  }

  // ...
}

树的遍历

树有三种遍历方式，分别是先序遍历，中序遍历，和后序遍历，无论是哪种遍历，思路都是递归。树的递归都是分左子树和右子树一直递归下去，跳出条件都是直到空为止。

类型	特点	应用
先序遍历	祖先到后代遍历，遍历过程是根 -> 左 -> 右	打印文档的结构
中序遍历	由小到大遍历，遍历过程是左 -> 根 -> 右	树排序
后序遍历	后代到祖先遍历，遍历过程是左 -> 右 -> 根	计算目录及其子目录大小

先序遍历:

我们先写一个简单的先序遍历，甚至整个函数只需要一行代码即可。

我们的目标是输入一个根节点，输出一个遍历后的数组。我们先来分析一下：

1. 整个过程是一个递归，也就是说左右子树如果有值，就递归下去；没有值，则跳出。
2. 如果子树没有值则跳出，而最终输出结果又是数组，即 if(!root) return []
3. 如果左右子树有值，那就递归下去，即 preOrderTraverse(root.left) 和 preOrderTraverse(root.right)
4. 因为先序遍历是 根 -> 左 -> 右 的遍历顺序，所以递归的每个子树的返回值应该是 [root, left, right] 的顺序

组合一下代码:

const preOrderTraverse = root => {
  if (root) {
    return [root.key, ...preOrderTraverse(root.left), ...preOrderTraverse(root.right)]
  } else {
    return []
  }
}

精简成一行:

/**
 * 简单版先序遍历
 * @param {Node} root 树的根节点
 */
const preOrderTraverse = root => {
  return root ? [root.key, ...preOrderTraverse(root.left), ...preOrderTraverse(root.right)] : []
}

中序遍历:

与先序遍历类似，只是返回的顺序不同，中序遍历的顺序是 左 -> 根 -> 右

/**
 * 简单版中序遍历
 * @param {Node} root 树的根节点
 */
const inOrderTraverse = root => {
  return root ? [...inOrderTraverse(root.left), root.key, ...inOrderTraverse(root.right)] : []
}

后序遍历:

与先序遍历类似，只是返回的顺序不同，中序遍历的顺序是 左 -> 右 -> 根

/**
 * 简单版中序遍历
 * @param {Node} root 树的根节点
 */
const postOrderTraverse = root => {
  return root ? [...postOrderTraverse(root.left), ...postOrderTraverse(root.right), root.key] : []
}

带回调的遍历:

上面的方法已经能满足对一颗树进行遍历并且返回遍历后的值了，但是我们还希望在遍历的过程中对每一个节点都执行一个回调函数。

正如 [].forEach(item => {}) 一样，遍历到每一项都能执行一个回调。我们希望在树的回调函数中，能拿到当前遍历的值 key，左子树的值 leftKey，右子树的值 rightKey 以及当前节点 node 的相关信息

注意： 回调即遍历到当前节点的时候就执行，所以要注意回调和递归之间的执行顺序

1. 先序列遍历是 根 -> 左 -> 右 的遍历顺序，也就是说在递归之前就已经遍历到当前节点了，所以回调需要在递归前执行。
2. 中序遍历是 左 -> 根 -> 右 的遍历顺序，也就是说递归了左子树后就遍历到了当前节点，所以回调需要在左子树递归后，右子树递归前执行。
3. 后序遍历是 左 -> 右 -> 根 的遍历顺序，也就是说在左右子树都递归完了才遍历到当前节点，所以回调需要在左右子树递归完之后执行。

具体解释请看代码中的注释

/**
 * 带回调的先序遍历
 * @param {Node} root 树的根节点
 * @param {Function} callback 回调函数，回调函数接受 key，leftKey，rightKey，node四个参数
 */
const preOrderTraverse = (root, callback) => {
  // 跳出条件与简单版一样，没有值则跳出
  if (!root) return []

  // 定义回调需要的几个值
  // 当前节点 node 即 root，无需定义
  const key = root.key
  const leftKey = root.left ? root.left.key : null
  const rightKey = root.right ? root.right.key : null

  // 因为是先序遍历，回调需要在递归前执行
  callback(key, leftKey, rightKey, root) // *1
  // 左子树递归
  const preLeft = BinarySearchTree.traverse(root.left, type, callback) // *2
  // 右子树递归
  const preRight = BinarySearchTree.traverse(root.right, type, callback) // *3
  // 和简单版一样，返回 根 -> 左 -> 右 的遍历顺序
  return [root.key, ...preLeft, ...preRight] // *4
}

带回调的中序遍历，带回调的后序遍历与上面的代码类似，只是 *1，*2，*3 三行代码的顺序不同罢了。此外 *4 返回的顺序也不同

整合后的遍历:

我们把上述的遍历整合一下，写到树的类中。

1. 我们希望树的类有先序遍历，中序遍历，后序遍历的实例方法，可以通过 tree.preOrderTraverse(callback) 来遍历一棵树，并且支持回调函数。
2. 树的类还能提供一个静态的遍历方法，可以通过 BinarySearchTree.traverse(root, type, callback) 的方式来遍历一棵树，接收三个参数，root 是树的根节点，type 是遍历方法，callback 是回调函数

class BinarySearchTree {
  // ...
  // 实例的方法都很简单，其实就是执行静态遍历方法 traverse

  /**
   * 先序遍历
   * @param {Function} callback 回调函数
   */
  preOrderTraverse(callback) {
    return BinarySearchTree.traverse(this.root, 1, callback)
  }

  /**
   * 中序遍历
   * @param {Function} callback 回调函数
   */
  inOrderTraverse(callback) {
    return BinarySearchTree.traverse(this.root, 2, callback)
  }

  /**
   * 后序遍历
   * @param {Function} callback 回调函数
   */
  postOrderTraverse(callback) {
    return BinarySearchTree.traverse(this.root, 3, callback)
  }

  /**
   * 静态遍历方法
   * @param {Node} root 树的根节点
   * @param {Number} type 遍历类型，1先序遍历，2中序遍历，3后序遍历
   * @param {Function} callback 回调函数，回调函数接受 key，leftKey，rightKey，node四个参数
   */
  static traverse(root, type, callback) {
    // 这里与上文中 “带回调的遍历” 是一样的
    if (!root) return []
    const key = root.key
    const leftKey = root.left ? root.left.key : null
    const rightKey = root.right ? root.right.key : null

    // 根据不同的遍历类型，进行不同的遍历，注意回调与递归之间的执行顺序，以及不同遍历返回的排序也不同
    switch (type) {
      // 先序遍历
      case 1:
        callback(key, leftKey, rightKey, root)
        const preLeft = BinarySearchTree.traverse(root.left, type, callback)
        const preRight = BinarySearchTree.traverse(root.right, type, callback)
        return [root.key, ...preLeft, ...preRight]
      // 中序遍历
      case 2:
        const inLeft = BinarySearchTree.traverse(root.left, type, callback)
        callback(key, leftKey, rightKey, root)
        const inRight = BinarySearchTree.traverse(root.right, type, callback)
        return [...inLeft, root.key, ...inRight]
      // 后序遍历
      case 3:
        const postLeft = BinarySearchTree.traverse(root.left, type, callback)
        const postRight = BinarySearchTree.traverse(root.right, type, callback)
        callback(key, leftKey, rightKey, root)
        return [...postLeft, ...postRight, root.key]
      default:
        break
    }
  }

  // ...
}

树的查询

二叉树有个特点，那就是最左边的节点肯定是最小值，最右边的节点肯定是最大值。根据这个特性我们可以很轻松找出树的最大值和最小值。

树的最小值

1. 我们希望树的类提供一个静态的查找最小值的方法，如 BinarySearchTree.minNode(root)
2. 提供一个查找当前树实例最小值的方法，如 tree.min()

其实查找实例最小值就是把实例的根扔到 BinarySearchTree.minNode() 中执行一次

/**
 * 查找一棵树的最小值
 * @param {Node} root 树的根节点
 */
const minNode = root => {
  if (!root) return null
  // 一直找到最左节点
  while (root && root.left !== null) root = root.left
  return root
}

/**
 * 查找并返回最小节点
 */
const min = () => {
  return BinarySearchTree.minNode(this.root).key
}

树的最大值

与树的最小值类似

/**
 * 查找一棵树的最大值
 * @param {Node} root 树的根节点
 */
const maxNode = root => {
  if (!root) return null
  // 一直找到最右节点
  while (root && root.right !== null) root = root.right
  return root
}

/**
 * 查找并返回最小节点
 */
const max = () => {
  return BinarySearchTree.maxNode(this.root).key
}

查找树的特定节点

/**
 * 查找树是否有某个节点
 * @param {Number} key 需要查找的节点的值
 */
const has = key => {
  const searchNode = (root, key) => {
    // 如果找不到，返回 false
    if (root === null) return false
    // 如果找到了，返回 true
    if (key === root.key) return true
    // 递归左右子树
    return key < root.key ? searchNode(root.left, key) : searchNode(root.right, key)
  }
  return searchNode(this.root, key)
}

整合代码

class BinarySearchTree {
  // ...

  /**
   * 查找并返回最小节点
   */
  min() {
    return BinarySearchTree.minNode(this.root).key
  }

  /**
   * 查找并返回最大节点
   */
  max() {
    return BinarySearchTree.maxNode(this.root).key
  }

  /**
   * 查找树是否有某个节点
   * @param {Number} key 需要查找的节点的值
   */
  has(key) {
    const searchNode = (root, key) => {
      if (root === null) return false
      if (key === root.key) return true
      return key < root.key ? searchNode(root.left, key) : searchNode(root.right, key)
    }
    return searchNode(this.root, key)
  }

  /**
   * 查找一棵树的最小值
   * @param {Node} root 树的根节点
   */
  static minNode(root) {
    if (!root) return null
    while (root && root.left !== null) root = root.left
    return root
  }

  /**
   * 查找一棵树的最大值
   * @param {Node} root 树的根节点
   */
  static maxNode(root) {
    if (!root) return null
    while (root && root.right !== null) root = root.right
    return root
  }

  // ...
}

移除节点

这是树类中最复杂的方法。我们先分类讨论，整理一下思路。假设我们要从树 Tree 中删除节点 X

首先有个大前提: BST 树的特性是根节点比左节点大，比右节点小。

第一步: 找出要删掉的 X

1. X 比 Tree 的根节点小，那我们就从 Tree 的左子树中找 X，并且这个过程是递归的
2. X 比 Tree 的根节点大，那我们就从 Tree 的右子树中找 X，这个过程也是递归的
3. 如果整棵树都找不到 X，那删除失败，返回 false
4. 如果找到了 X，删除并返回 true

第二部: 删掉 X

1. X 没有子节点，令 X 为 null 即可
2. X 只有一个子节点，那么这个子节点代替 X（删掉 X 意味着他的唯一子节点就要代替自己的位置）
3. X 有两个子节点，我们需要从左右子节点（子树）中找到一个值代替 X
   > 1. 我们要从右边子树中找到用于替换 X 的值，因为 根据大前提 ，左子树任意节点的值肯定比 X 的值小，他们不能代替 X
   > 2. 找到右边子树的最小节点，因为 根据大前提 ，当它替换掉 X 的时候，能保证比 X 左子树所有值都大，比 X 右子树所有值都小

class BinarySearchTree {
  // ...

  /**
   * 移除节点
   * @param {Number} key 需要移除的节点的值
   */
  delete(key) {
    let result = false // 是否删除成功

    /**
     * 用于递归的删除方法
     * @param {Node} node 当前树的根节点
     * @param {Number} key 删除的值
     */
    const _delete = (node, key) => {
      // 如果当前节点是空的，返回空
      if (node === null) return null

      // 目标删除节点的值比当前节点的值小，继续从左子树中找
      if (key < node.key) {
        node.left = _delete(node.left, key)
        return node
      }

      // 目标删除节点的值比当前节点的值大，继续从右子树中找
      if (key > node.key) {
        node.right = _delete(node.right, key)
        return node
      }

      // 找到要删除的目标节点
      if (key === node.key) {
        result = true
        // 第一种情况: 这个节点没有子节点，删掉当前节点
        if (node.left === null && node.right === null) {
          node = null
          return node
        }

        // 第二种情况: 这个节点只有一个子节点，子节点代替当前节点
        if (node.left === null && node.right !== null) {
          node = node.right
          return node
        }
        if (node.right === null && node.left !== null) {
          node = node.left
          return node
        }

        // 第三种情况: 这个节点有两个子节点，从左右子节点（子树）中找到一个值代替当前节点
        const rightSubTreeMinNode = BinarySearchTree.minNode(node.right) // 找到右子树的最小节点
        node.key = rightSubTreeMinNode.key // 右子树的最小节点的值赋给当前节点
        node.right = _delete(node.right, rightSubTreeMinNode.key) // 找到右子树最小节点，删掉
        return node
      }
    }
    this.root = _delete(this.root, key)
    return result
  }

  // ...
}

总结

至此，JavaScript 版的搜索二叉树的类已经完成了，完整代码如下

class BinarySearchTree {
  /**
   * 初始化有一个根节点
   */
  constructor(key) {
    this.root = BinarySearchTree.createNode(key)
  }

  /**
   * 插入节点
   * @param {Number} key 需要插入的节点的值
   */
  insert(key) {
    const newNode = BinarySearchTree.createNode(key)
    const insertNode = function(curNode, newNode) {
      if (newNode.key < curNode.key) {
        curNode.left === null ? (curNode.left = newNode) : insertNode(curNode.left, newNode)
      } else {
        curNode.right === null ? (curNode.right = newNode) : insertNode(curNode.right, newNode)
      }
    }
    this.root.key === null ? (this.root = newNode) : insertNode(this.root, newNode)
  }

  /**
   * 先序遍历
   * @param {Function} callback 回调函数
   */
  preOrderTraverse(callback) {
    return BinarySearchTree.traverse(this.root, 1, callback)
  }

  /**
   * 中序遍历
   * @param {Function} callback 回调函数
   */
  inOrderTraverse(callback) {
    return BinarySearchTree.traverse(this.root, 2, callback)
  }

  /**
   * 后序遍历
   * @param {Function} callback 回调函数
   */
  postOrderTraverse(callback) {
    return BinarySearchTree.traverse(this.root, 3, callback)
  }

  /**
   * 查找并返回最小节点
   */
  min() {
    return BinarySearchTree.minNode(this.root).key
  }

  /**
   * 查找并返回最大节点
   */
  max() {
    return BinarySearchTree.maxNode(this.root).key
  }

  /**
   * 查找树是否有某个节点
   * @param {Number} key 需要查找的节点的值
   */
  has(key) {
    const searchNode = (root, key) => {
      if (root === null) return false
      if (key === root.key) return true
      return key < root.key ? searchNode(root.left, key) : searchNode(root.right, key)
    }
    return searchNode(this.root, key)
  }

  /**
   * 移除节点
   * @param {Number} key 需要移除的节点的值
   */
  delete(key) {
    let result = false
    const _delete = (node, key) => {
      if (node === null) return null
      if (key < node.key) {
        node.left = _delete(node.left, key)
        return node
      }
      if (key > node.key) {
        node.right = _delete(node.right, key)
        return node
      }
      if (key === node.key) {
        result = true
        if (node.left === null && node.right === null) {
          node = null
          return node
        }
        if (node.left === null && node.right !== null) {
          node = node.right
          return node
        }
        if (node.right === null && node.left !== null) {
          node = node.left
          return node
        }
        const rightSubTreeMinNode = BinarySearchTree.minNode(node.right)
        node.key = rightSubTreeMinNode.key
        node.right = _delete(node.right, rightSubTreeMinNode.key)
        return node
      }
    }
    this.root = _delete(this.root, key)
    return result
  }

  /**
   * 生成一个树节点
   * @param {Number} key 节点的值
   */
  static createNode(key) {
    key = key || null
    function Node(key) {
      this.key = key
      this.left = null
      this.right = null
    }
    return new Node(key)
  }

  /**
   * 静态遍历方法
   * @param {Node} root 树的根节点
   * @param {Number} type 遍历类型，1先序遍历，2中序遍历，3后序遍历
   * @param {Function} callback 回调函数，回调函数接受 key，leftKey，rightKey，node四个参数
   */
  static traverse(root, type, callback) {
    if (!root) return []
    const key = root.key
    const leftKey = root.left ? root.left.key : null
    const rightKey = root.right ? root.right.key : null
    switch (type) {
      case 1:
        callback(key, leftKey, rightKey, root)
        const preLeft = BinarySearchTree.traverse(root.left, type, callback)
        const preRight = BinarySearchTree.traverse(root.right, type, callback)
        return [root.key, ...preLeft, ...preRight]
      case 2:
        const inLeft = BinarySearchTree.traverse(root.left, type, callback)
        callback(key, leftKey, rightKey, root)
        const inRight = BinarySearchTree.traverse(root.right, type, callback)
        return [...inLeft, root.key, ...inRight]
      case 3:
        const postLeft = BinarySearchTree.traverse(root.left, type, callback)
        const postRight = BinarySearchTree.traverse(root.right, type, callback)
        callback(key, leftKey, rightKey, root)
        return [...postLeft, ...postRight, root.key]
      default:
        break
    }
  }

  /**
   * 查找一棵树的最小节点
   * @param {Node} root 树的根节点
   */
  static minNode(root) {
    if (!root) return null
    while (root && root.left !== null) root = root.left
    return root
  }

  /**
   * 查找一棵树的最大节点
   * @param {Node} root 树的根节点
   */
  static maxNode(root) {
    if (!root) return null
    while (root && root.right !== null) root = root.right
    return root
  }
}

测试用例:

// 初始化测试
const tree = new BinarySearchTree(11)
console.log('初始化测试', tree)

// 插入测试
tree.insert(9)
tree.insert(15)
tree.insert(3)
console.log('插入测试', tree)

// 先序遍历测试
const preList = tree.preOrderTraverse((key, leftKey, rightKey, node) => {
  console.log('先序遍历回调', key, leftKey, rightKey, node)
})
console.log('先序遍历测试', preList)

// 中序遍历测试
const inList = tree.inOrderTraverse((key, leftKey, rightKey, node) => {
  console.log('中序遍历回调', key, leftKey, rightKey, node)
})
console.log('中序遍历测试', inList)

// 后序遍历测试
const postList = tree.postOrderTraverse((key, leftKey, rightKey, node) => {
  console.log('后序遍历回调', key, leftKey, rightKey, node)
})
console.log('后序遍历测试', postList)

// 查找最小值测试
const min = tree.min()
console.log('查找最小值测试', min)

// 查找最大值测试
const max = tree.max()
console.log('查找最大值测试', max)

// 查找特定值测试
const has9 = tree.has(9)
const has100 = tree.has(100)
console.log('查找特定值9', has9)
console.log('查找特定值100', has100)

// 删除测试
const delete9 = tree.delete(9)
const delete100 = tree.delete(100)
console.log('删除9', delete9)
console.log('删除100', delete100)
console.log('删除9后查找9', tree.has(9))