数据结构 二叉搜索树 BinarySearchTree

二叉树中的节点最多只能由两个子节点，一个是左侧子节点，一个是右侧子节点。这些定义有助与我们写出更高效的操作树的算法。二叉树在计算机科学中的应用非常广泛。

二叉搜索树是二叉树中的一种，但是它只允许在左侧节点存储比父节点小的值，在右侧节点存储比父节点大的值。

和链表一样，我们通过指针来表示节点之间的关系，不同于之前将节点本身称作为节点或项，这里我们称其为键。键是树相关术语中对节点的称呼。

二叉搜索树的功能

插入，查找，中序遍历，前序遍历，后序遍历，最小值，最大值，移除

中序遍历：以从最小到最大的顺序访问所有节点（左子树，根节点，右子树）

先序遍历：以优先于后代节点的顺序访问每个节点（根节点，左子树，右子树）

后序遍历：先访问节点的后代节点，在访问节点本身（左子树，右子树，根节点）

二叉搜索树的实现

// BinarySearchTree.js

// 构造一个节点
const Node = function (key) {
  this.key = key;
  this.left = null;
  this.right = null;
};

function BinarySearchTree() {
  this.root = null;
}

module.exports = BinarySearchTree;

插入

// 插入
BinarySearchTree.prototype.insert = function (key) {
  var newNode = new Node(key);
  if (this.root === null) {
    this.root = newNode;
  } else {
    insertNode(this.root, newNode);
  }
  // 定义一个节点插入函数
  function insertNode(node, newNode) {
    if (newNode.key < node.key) {
      if (node.left == null) {
        node.left = newNode;
      } else {
        insertNode(node.left, newNode);
      }
    } else {
      if (node.right == null) {
        node.right = newNode;
      } else {
        insertNode(node.right, newNode);
      }
    }
  }
};

删除

// 移除
BinarySearchTree.prototype.remove = function (key) {
  this.root = removeNode(this.root, key);
  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) {
        return null;
      }
      // 第二种情况，只有一个子节点的节点
      if (node.left === null) {
        return node.right;
      } else if (node.right === null) {
        return node.left;
      }
      // 第三种情况，两个子节点的情况
      let aux = findMinNode(node.right); // 找到右子树的最小值，替换
      node.key = aux.key;
      node.right = removeNode(node.right, aux.key); // 删除右子树的最小值的节点
      return node;
    }
  }

  function findMinNode(node) {
    if (node) {
      while (node && node.left !== null) {
        node = node.left;
      }
      return node;
    }
    return null;
  }
};

遍历

// 前序遍历
BinarySearchTree.prototype.preOrderTraverseNode = function (callback) {
  traverse(this.root, callback);
  function traverse(node, callback) {
    if (node !== null) {
      callback(node.key);
      traverse(node.left, callback);
      traverse(node.right, callback);
    }
  }
};

// 中序遍历
BinarySearchTree.prototype.inOrderTraverseNode = function (callback) {
  traverse(this.root, callback);
  function traverse(node, callback) {
    if (node !== null) {
      traverse(node.left, callback);
      callback(node.key);
      traverse(node.right, callback);
    }
  }
};

// 后序遍历
BinarySearchTree.prototype.postOrderTraverseNode = function (callback) {
  traverse(this.root, callback);
  function traverse(node, callback) {
    if (node !== null) {
      traverse(node.left, callback);
      traverse(node.right, callback);
      callback(node.key);
    }
  }
};

其他

// 最小值
BinarySearchTree.prototype.min = function () {
  let node = this.root;
  if (node) {
    while (node && node.left !== null) {
      node = node.left;
    }
    return node.key;
  }
  return null;
};

// 最大值
BinarySearchTree.prototype.max = function () {
  let node = this.root;
  if (node) {
    while (node && node.right !== null) {
      node = node.right;
    }
    return node.key;
  }
  return null;
};

// 搜索
BinarySearchTree.prototype.search = function (key) {
  return searchNode(this.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;
    }
  }
};

测试

const BinarySearchTree = require("./BinarySearchTree.js");

const tree = new BinarySearchTree();
tree.insert(5);
tree.insert(4);
tree.insert(6);
tree.insert(3);
tree.insert(7);
tree.insert(2);
tree.insert(8);
tree.insert(1);
tree.insert(9);

console.log("前序遍历");
tree.preOrderTraverseNode((value) => {
  console.log(value);
});

console.log("中序遍历");
tree.inOrderTraverseNode((value) => {
  console.log(value);
});

console.log("后序遍历");
tree.postOrderTraverseNode((value) => {
  console.log(value);
});

console.log("min", tree.min()); // 1
console.log("max", tree.max()); // 9
console.log("search(6):", tree.search(6)); // true
console.log("search(2)", tree.search(2)); // false
tree.remove(6);
console.log("search(6):", tree.search(6)); // false