二叉查找树

二叉树(Binary tree)是每个节点最多只有两个分支(不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”和“右子树”。二叉树的分支具有左右次序,不能颠倒。

二叉树分很多种,而二叉查找树是其中比较经典的一款,也称二叉搜索树、有序二叉树、排序二叉树,是指一棵空树或者具有下列性质的二叉树:

  1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  2. 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  3. 任意节点的左、右子树也分别为二叉查找树;
  4. 没有键值相等的节点。

节点

每个二叉树的节点有它本身的值,同时都具有左子树和右子树,根据这个定义,我们得到:

/**
* 单个节点
*/

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

树的结构

每一颗二叉树都必须有一个根节点 root。

/**
* 二叉查找树
*/

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

添加一些方法

跟之前的链表一样,二叉查找树也会包含一些操作方法,比如 insert、remove...。

insert(插入节点)

根据二叉查找树的定义很容易推导出,将待插入的值从根节点的开始比较:

uml diagram

这里需要注意的一点是对root节点的判断,如果不存在,直接构建root节点。

class Tree {
...
static _insert(val, node) {
if (val < node.val) {
if (node.left) {
this._insert(val, node.left);
} else {
node.left = new Node(val);
}
} else {
if (node.right) {
this._insert(val, node.right);
} else {
node.right = new Node(val);
}
}
}

insert(val) {
if (!this.root) {
this.root = new Node(val);
return;
}

this.constructor._insert(val, this.root)
}
...
}

remove(移除节点)

这里比较复杂一点,根据二叉查找树的定义,节点间的相互关系总是以下规则,即:左子树的任意节点值 < 该节点的值 < 右子树的任意节点值,所以在移除某节点时,需要考虑右子树是否存在。如果右子树存在,将左子树移至右子树的最小节点下,然后用右子树替换被移除节点;若不存在直接用左子树替换被移除节点。

下面我用一张动画做出更好的说明:

移除节点原理

看完原理那就着手开干吧。

class Tree {
...
// 挂载的辅助函数
static _mountMinTree(tree, host) {
if (host.left) {
this._mountMinTree(tree, host.left)
} else {
host.left = tree
}
return host
}

static _remove(val, node) {
if (!node) {
return null;
}

if (val === node.val) { // 要删除的节点是当前节点
if (!node.right) { // 右子树不存在,直接用左子树替换当前节点流程结束
return node.left;
} else if (!node.left) { // 左子树不存在,直接用右子树替换当前节点流程结束
return node.right;
} else { // 右子树存在
return this._mountMinTree(node.left, node.right); // 取出左子树挂载到右子树的最小节点上,返回该右子树替换当前节点
}
} else if (val < node.val) { // 要删除的节点在左子树
node.left = this._remove(val, node.left);
return node;
} else { // 要删除的节点在右子树
node.right = this._remove(val, node.right);
return node;
}
}

// 移除节点
remove(val) {
this.root = this.constructor._remove(val, this.root);
}
...
}

以上是我最开始的思路,下面还有两种方式,是我一开始未曾想到的,由于二叉查找的树定义可知,右子树的最小节点总是大于左子树的最大节点,所以可以提取左子树的最大节点/右子树的最小节点直接替换当前节点即可。

同样用动画说明:

以右子树的最小节点值替换当前节点值 以左子树的最大节点值替换当前节点值

体现在算法上,区别只有return this._mountMinTree(node.left, node.right);这一行需要改写,以左图为例:

class Tree {
...
static _minNode(node) {
if (!node) {
return null;
}
while (node && node.left) {
node = node.left;
}
return node;
}

static _remove(val, node) {
...
} else { // 右子树存在
// return this._mountMinTree(node.left, node.right); // 取出左子树挂载到右子树的最小节点上,返回该右子树替换当前节点
const minNode = this._minNode(node.right); // 找到右子树最小节点
node.val = minNode.val; // 替换
node.right = this._remove(minNode.val, node.right); // 右子树删除最小节点
return node;
}
...
}

// 移除节点
remove(val) {
this.root = this.constructor._remove(val, this.root);
}
...
}

min/max(获取最小/最大值)

这个很简单,最小/最大值只需要循环查找左子树/右子树即可,参考上面的_minNode方法。

includes(包含)

跟数组的includes含义一样,判断是否存在指定值。

class Tree {
...
static _includes(val, node) {
if (!node) {
return false;
}
if (val === node.val) {
return true;
}
return this._includes(val, val < node.val ? node.left : node.right);
}

includes(val) {
return this.constructor._includes(val, this.root);
}
...
}

getMaxDepth(获取最大深度)

class Tree {
...
static _depth(node) {
if (!node) {
return 0
}
return Math.max(this._depth(node.left), this._depth(node.right)) + 1;
}

getMaxDepth() {
return this.constructor._depth(this.root);
}
...
}

遍历

遍历的方式有很多中,首先分广度优先遍历(breadth-first search,BFS)和深度优先遍历(depth-first search,DFS),深度优先遍历又分前序、中序、后序,下面逐一分析。

广度优先遍历

广度优先遍历

广度优先遍历的做事方式形容起来有点像画同心圆,先访问圆心点,然后标记离圆心紧邻的点,一层一层往外扩展,使用队列来操作是比较方便的:

  1. 从顶点开始,将顶点加入队列;
  2. 取出队列中的第一个节点,标记已访问;
  3. 找到第一个节点的子节点,将其加入队列;
  4. 将第一个节点从队列中移除,再次重复步骤2,直到队列中为空结束。
class Tree {
...
bfs() {
if (!this.root) {
return [];
}
const queue = [this.root];
const list = [];
while (queue.length) {
const node = queue.shift();
list.push(node.val);
if (node.left) {
queue.push(node.left);
}
if (node.right) {
queue.push(node.right);
}
}
return list;
}
...
}
深度优先遍历

深度优先遍历的做事方式形容起来就是“一条道走到黑”,对于每一个节点,在它有子节点的情况下,总是会深挖子节点,直到没有子节点后沿着原路回退到节点本身;根据节点、左子树、右子树间的访问顺序不同又细分出前序、中序、后序方法。

  • 前序遍历:节点 -> 左子树 -> 右子树;

    class Tree {
    ...
    dfsPre(node = this.root, list = []) {
    if (node) {
    list.push(node.val);
    this.dfsPre(node.left, list);
    this.dfsPre(node.right, list);
    }
    return list;
    }
    ...
    }
  • 中序遍历:左子树 -> 节点 -> 右子树;

    class Tree {
    ...
    dfsIn(node = this.root, list = []) {
    if (node) {
    this.dfsIn(node.left, list);
    list.push(node.val);
    this.dfsIn(node.right, list);
    }
    return list;
    }
    ...
    }
  • 后序遍历:左子树 -> 右子树 -> 节点;

    class Tree {
    ...
    dfsPost(node = this.root, list = []) {
    if (node) {
    this.dfsPost(node.left, list);
    this.dfsPost(node.right, list);
    list.push(node.val);
    }
    return list;
    }
    ...
    }

后记

对于树的操作,我对移除操作有些疑惑,包括后来也查询了一些资料,清一色都是后面两种方案,让我一度产生对自己想到的第一种方法的正确性产生过怀疑,不过总结下来理论上应该是没错的,变换后的结果也是符合二叉查找树的定义的,只要算法上不出错就不会问题......吧?