1.创建搜索二叉树

包括根节点root
root下面存在 key, left, right
left小于key, right大于key

  1. // 搜索二叉树
  2. function BinarySearchTree() {
  3.   // 节点
  4.   function Node(key) {
  5.     this.key = key
  6.     this.left = null
  7.     this.right = null
  8.   }
  9. }
  10. // 1.创建搜索二叉树
  11. let bst = new BinarySearchTree()

2.添加节点

节点Node：包含key, left, right
insert：从root开始，比较当前节点的key与新node的key

  1. 创建一个newNode
  2. 从root开始比较，如果newNode.key > key，如果存在left，则newNode继续与leftNode比较
  3. 如果不存在left，则newNode变成该节点的left

  4. right则相反，如果newNode.key < key，比较rightNode ```javascript // 搜索二叉树 function BinarySearchTree() { // 节点 function Node(key) { this.key = key this.left = null this.right = null } // 属性 this.root = null // 插入：对外给用户调用 BinarySearchTree.prototype.insert = function(key) { // 1.根据key创建节点 let newNode = new Node(key)

    // 2.判断根节点是否有值 if (this.root === null) { this.root = newNode } else { this.insertNode(this.root, newNode) } } /**

    • node: 比较的node
    • newNOde: 插入的node
    • 从根root开始比较，左边小，右边大 */ BinarySearchTree.prototype.insertNode = function(node, newNode) { if (newNode.key < node.key) { // 向左查找 // 两种情况：1.没有子节点，2.有子节点，继续比较 if (node.left === null) { node.left = newNode // 递归的结束条件 } else { this.insertNode(node.left, newNode) // 递归 } } else { // 向右查找 if (node.right === null) { node.right = newNode } else { this.insertNode(node.right, newNode) } } } }

// 测试代码 // 1.创建搜索二叉树 let bst = new BinarySearchTree() bst.insert(11) bst.insert(7)

console.log(bst);

  3. <a name="XlPYe"></a>
  4. ### 3. 遍历二叉树
  6. - 先序遍历
  7. - 后序遍历
  9. <a name="oVUEW"></a>
  10. #### 1. 先序遍历
  11. 先处理当前节点key<br />先遍历左子节点，<br />再遍历右子节点
  12. ```javascript
  13. /**
  14.  * 先序遍历
  15.  * 先处理当前经过的节点
  16.  * 再遍历左子树，再遍历右子树
  17.  */
  18. BinarySearchTree.prototype.preOrderTraversal = function(handler) {
  19.   this.preOrderTraversalNode(this.root, handler)
  20. }
  21. // 私有方法：遍历节点
  22. BinarySearchTree.prototype.preOrderTraversalNode = function(node, handler) {
  23.   if (node !== null) { // 递归的结束条件
  24.     // 处理经过的节点上的 key
  25.     handler(node.key)
  27.     // 递归，处理进过节点的左子节点
  28.     this.preOrderTraversalNode(node.left, handler)
  30.     // 递归：处理经过节点的右子节点
  31.     this.preOrderTraversalNode(node.right, handler)
  32.   }
  33. }

测试创建并遍历：

let bst = new BinarySearchTree()
bst.insert(11)
bst.insert(7)
bst.insert(9)
bst.insert(20)
bst.insert(3)
bst.insert(15)

let resStr = ""
bst.preOrderTraversal((key) => {
  resStr += key + " "
})
console.log(resStr); // 11, 7, 3, 9, 20, 15

2.中序遍历

先处理左子节点
再处理当前节点key
再处理右子节点

// 2.中序遍历
BinarySearchTree.prototype.midOrderTraversal = function(handler) {
  this.midOrderTraversalNNode(this.root, handler)
}
BinarySearchTree.prototype.midOrderTraversalNNode = function(node, handler) {
  if (node !== null) {
    // 1.先处理左子节点
    this.midOrderTraversalNNode(node.left, handler)
    // 2.处理节点
    handler(node.key)
    // 3.处理右子树中的节点
    this.midOrderTraversalNNode(node.right, handler)
  }
}
// 3, 7, 9, 11, 15, 20

s

3.后序遍历

  1. 先处理左子节点
  2. 再处理右子节点
  3. 再处理当前节点
    // 3.后序遍历
BinarySearchTree.prototype.postOrderTraversal = function(handler) {
this.postOrderTraversalNode(this.root, handler)
}
BinarySearchTree.prototype.postOrderTraversalNode = function(node, handler) {
if (node !== null) {
 // 1.处理左子树节点
 this.postOrderTraversalNode(node.left, handler)
 // 2.处理右子树中的节点
 this.postOrderTraversalNode(node.right, handler)
 // 3.处理当前节点
 handler(node.key)
}
}

4.获取最大值和最小值

  1. 寻找最大值

通过while循环，一直去寻找最右边的节点，直到node.right为null，返回当前的node.key

BinarySearchTree.prototype.max = function() {
  // 1.获取根节点
  let node = this.root
  // 2.依次向右不断的查找，直到节点为null
  let key = null
  while (node !== null) {
    key = node.key
    node = node.right
  }
  return key
}
  1. 寻找最小值

一直寻找最左边的节点，直到node.left为null

BinarySearchTree.prototype.min = function() {
  let node = this.root
  let key = null
  while(node !== null) {
    key = node.key
    node = node.left
  }
  return key
}

5.搜索

从根节点开始对比传入的key值，如果比根节点小则继续比对left，大则比对right，相等则搜索成功，一直到node为空则说明没有搜索到

// 搜索
BinarySearchTree.prototype.search = function(key) {
 return this.searchNode(this.root, key) 
}
BinarySearchTree.prototype.searchNode = function(node, key) {
  // 传入的 node 为空 退出递归
  if (node === null) {
    return false
  }

  // 判断 node 节点 的值和传入的 key 的大小
  if (node.key > key) { // 传入的 key 较小，向左边继续查找
    return this.searchNode(node.left, key)
  } else if (node.key < key) { // 传入的 key 较大，向右边继续查找
    return this.searchNode(node.right, key)
  } else { // 相同
    return true
  }
}

6.删除节点

  1. 先找到删除的节点，如果没有找到，则无需删除
  2. 找到要删除的节点
    1. 删除叶子节点（最后一层，无子节点）
    2. 删除只有一个子节点的节点
    3. 删除有两个子节点的节点

1.找到需要删除的节点

找到对应key的节点，然后记录父节点，以及自身属于父节点的left或者right，删除父节点上绑定的left或者right

// 删除节点
BinarySearchTree.prototype.remove = function(key) {
  // 1.寻找要删除的节点
  // 1.1 定义变量，保存一些信息
  let current = this.root // 记录当前节点
  let parent = null // 记录parent节点

  // 找到需要删除的节点
  while(current.key !== key) {
    parent = current
    // 比对左右子节点
    if (key < current.key) {
      isLeftChild = true
      current = current.left
    } else {
      isLeftChild = false
      current = current.right
    }

    // 没有找到 key
    if (current === null) {
      return false
    }
  }
}

2.情况一：删除的节点是叶子节点

删除正好是叶子节点，如果只有一层，根节点也是叶子节点

// 1.删除的节点是叶子节点（最后一层）
if (current.left === null && current.right === null) {
  if (current === this.root) {
    this.root = null
  } else if (isLeftChild) {
    parent.left = null
  } else {
    parent.right = null
  }
}

3.情况二：删除的节点存在一个子节点

  • 删除的节点是根节点，直接将子节点作为根节点
  • 删除的节点非根节点，并且包含一个左子节点
    • 将左子节点直接作为父节点的左子节点
  • 删除的节点非根节点，并且包含一个右子节点
    • 将右子节点作为父节点的右子节点
      // 2.删除的节点有一个子节点
// 2.1 只有左子节点
else if (current.right === null) {
// 判断 current 是否是 root 节点
if (current === this.root) {
this.root = current.left
}
// 如果自身是父节点的左子节点
else if (isLeftChild) {
parent.left = current.left
// 如果自身是父节点的右子节点
} else {
parent.right = current.left
}
} else if (current.left === null) {
if (current === this.root) {
this.root = current.right
}
else if (isLeftChild) {
parent.left = current.right
} else {
parent.right = current.right
}
}