javascript算法之二叉搜索树的示例代码

什么是二叉树

二叉树就是树的每个节点最多只能有两个子节点

什么是二叉搜索树

二叉搜索树在二叉树的基础上，多了一个条件，就是二叉树在插入值时，若插入值比当前节点小，就插入到左节点，否则插入到右节点；若插入过程中，左节点或右节点已经存在，那么继续按如上规则比较，直到遇到一个新的节点。

二叉搜索树的特性

二叉搜索树由于其独特的数据结构，使得其无论在增删，还是查找，时间复杂度都是O(h)，h为二叉树的高度。因此二叉树应该尽量的矮，即左右节点尽量平衡。

二叉搜索树的构造

要构造二叉搜索树，首先要构造二叉树的节点类。由二叉树的特点可知，每个节点类都有一个左节点，右节点以及值本身，因此节点类如下：

class Node { constructor(key) {  this.key = key;  this.left = null;  this.right = null; }}

接着构造二叉搜索树

class Tree{ constructor(param = null) {  if (param) {   this.root = new Node(param);  } else {   this.root = null;  } }}

这里this.root就是当前对象的树。

二叉搜索树的新增

由二叉搜索树左子树比节点小，右子树别节点大的特点，可以很简单的写出二叉搜索树新增的算法，如下：

insert(key) { if (this.root === null) {  this.root = new Node(key); } else {  this._insertNode(this.root, key); }}_insertNode(node, key) { if (key < node.key) {  if (node.left === null) {   node.left = new Node(key);{1}  } else {   this._insertNode(node.left, key);{2}  } } else if (key > node.key) {  if (node.right === null) {   node.right = new Node(key);{3}  } else {   this._insertNode(node.right, key);{4}  } }}

如上代码先判断新增的key与当前节点的key大小，如果小，就递归遍历左子节点，直到找到一个为null的左子节点；如果比当前节点大同理。如上代码{1}{2}{3}{4}之所以能改变this.root的值，是由于JavaScript函数是按值传递，而当参数是非基本类型时，例如这里的对象，其对象的值为内存，因此每次都会直接改变this.root的内容。

二叉搜索树的遍历

二叉搜索树分为先序、中序、后序三种遍历方式。

inOrderTraverse(callback) { this._inOrderTraverse(this.root, callback);}_inOrderTraverse(node, callback) { if (node) {  this._inOrderTraverse(node.left, callback);  callback(node.key);  this._inOrderTraverse(node.right, callback); }}

如上是中序遍历。

这里需要理解的一点是递归。要知道，函数的执行可以抽象为一种数据结构——栈。针对函数的执行，会维护一个栈，来存储函数的执行。函数在每一次递归时，都会将当前的执行环境入栈并记录执行的位置。以上述代码为例，有如下一个数据