JavaScript 二叉树

[Checkson]

背景

树 是计算机科学中经常用到的一种数据结构。树是一种非线性的数据结构，以分层的方式存储数据。树被用来存储具有层级关系的数据，比如文件系统中的文件；树还被用来存储有序列表。这里将研究一种特殊的树：二叉树。选择树而不是那些基本的数据结构，是因在二叉树上进行查找非常快（而在链表上查找则不是这样），为二叉树添加或删除元素也非常快（而对数组执行添加或删除操作则不是这样）。

定义

在认识 二叉树 之前，我们先看看 树 的定义。

树由一组以边连接的节点组成。而我们日常使用的文件系统（以Mac OS为例），也是一种树状结构，如下图所示：

在图中，每一个方框就是一个节点，连接方框的线叫做边。节点代表了该文件系统中的各个文件，边描述了各个文件之间的关系。

另外，树最顶端的节点叫做 根节点，如果一个节点连接了多个节点，那么我们称他为 父节点，它下面的节点称为 子节点。一个节点可以拥有0个或者多个节点，没有任何子节点的节点我们称为 叶子节点。

二叉树 是一种特殊的树，其原因是它的子节点不能超过两个。二叉树具有特殊的计算性质，使得在它们之上的一些操作异常高效。下面将详细讨论。

二叉树和二叉查找树

二叉树 不允许其节点超过连个子节点。通过控制树中每一个子节点的个数限定为2，可以写出高效的程序在树中插入、查找、删除数据。

二叉树中的一个父节点的两个子节点，分别称为 左节点 和 右节点。在一些特定的二叉树中，左节点包含一组特定的值，右节点也包括一组特定的值。下面展示了一颗二叉树：

我们这里只讨论一种特殊的二叉树：二叉查找树，也叫 二叉搜索树。二叉查找树是一种特殊的二叉树，相对较小的值保存在左节点中，相对较大的值保存在右节点中。基于这个特性，使得二叉查找树的查找效率很高，对于数值型和非数值类型的数据，比如文本单词或者字符，都是如此。

二叉查找树（BST）类的实现

完整代码地址。

二叉查找树由树节点组成。我们先要定义一个Node对象。

function Node (data, left, right) {
    this.data = data;
    this.left = left;
    this.right = right;
}

Node对象既保存数据，也保存其子节点（左节点和右节点）的引用（指针）。

接下来，我们构建BST类。

完整代码地址。

1. 构造函数

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

2. 插入节点操作

BST.prototype.insert = function (data) {
    var node = new Node(data, null, null);
    if (!this.root) {
        this.root = node;
        return;
    }
    var current = this.root,
        parent;
    do {
        parent = current;
        if (data < current.data) {
            current = current.left;
            if (!current) {
                parent.left = node;
                break;
            }
        } else {
            current = current.right;
            if (!current) {
                parent.right = node;
                break;
            }
        }
    } while (true);
}

3. 中序遍历

BST.prototype.inOrder = function (node) {
    if (node) {
        this.inOrder(node.left);
        console.log(node.data);
        this.inOrder(node.right);
    }
}

4. 先序遍历

BST.prototype.preOrder = function (node) {
    if (node) {
        console.log(node.data);
        this.preOrder(node.left);
        this.preOrder(node.right);
    }
}

5. 后序遍历

BST.prototype.postOrder = function (node) {
    if (node) {
        this.postOrder(node.left);
        this.postOrder(node.right);
        console.log(node.data);
    }
}

6. 获取最小值

BST.prototype.getMin = function () {
    if (!this.root) {
        return null;
    }
    var current = this.root;
    while (current.left) {
        current = current.left;
    }
    return current.data;
}

7. 获取最大值

BST.prototype.getMax = function () {
    if (!this.root) {
        return null;
    }
    var current = this.root;
    while (current.right) {
        current.right;
    }
    return current.data;
}

8. 查找二叉查找树中给定的值

BST.prototype.find = function (data) {
    var current = this.root;
    while (current) {
        if (current.data === data) {
            return current;
        } else if (current.data > data) {
            current = current.left;
        } else {
            current = current.right;
        }
    }
    return null;
}

9. 在二叉查找树上删除节点

• 首先，判断当前是否包含待删除的数据，如果包含，删除该节点；如果不包含，则比较当前节点上的数据和待删除的数据。如果待删除数据小于当前 节点上的数据，则移至当前节点的左子节点继续比较；如果删除数据大于当前节点上的数 据，则移至当前节点的右子节点继续比较。
• 如果待删除节点是叶子节点(没有子节点的节点)，那么只需要将从父节点指向它的链接 指向 null。
• 如果待删除节点只包含一个子节点，那么原本指向它的节点久得做些调整，使其指向它的 子节点。
• 如果待删除节点包含两个子节点，正确的做法有两种:要么查找待删除节点左子树 上的最大值，要么查找其右子树上的最小值。这里我们选择后一种方式。

BST.prototype.remove = function (data) {
    this.removeNode(this.root, data);
}

BST.prototype.removeNode = function (node, data) {
    if (!node) {
        return null;
    }
    if (data === node.data) {
        if (!node.left && !node.right) {
            return null;
        } else if (!node.left) {
            return node.right;
        } else if (!node.right) {
            return node.left;
        } else {
            var tempNode = this.getSmallestNode(node.right);
            node.data = tempNode.data;
            node.right = this.removeNode(node.right, tempNode.data);
        }
    } else if (data < node.data) {
        node.left = this.removeNode(node.left, data);
    } else {
        node.right = this.removeNode(node.right, data);
    }
    return node;
}

// 获取给定子树最小值的节点
BST.prototype.getSmallestNode = function (node) {
    if (!node) {
        return null;
    }
    while (node.left) {
        node = node.left;
    }
    return node;
}

参考链接

平衡二叉树,AVL树之图解篇
3 分钟理解完全二叉树、平衡二叉树、二叉查找树
平衡二叉查找树（AVL）的查找、插入、删除