JavaScript 二叉树

像我这种野生程序员连各大公司校招笔试都过不了，主要是数据结构和算法薄弱，今天小米出了道二叉树，考二叉树的分层遍历，我当然是不会做，然后就没有然后了。

节点定义

二叉树节点定义：

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

给 Node 添加一个获得当前节点数据的方法：

1
2
3

Node.prototype.getData = function() {
    return this.data;
};

二叉树定义

定义二叉树，初始根节点为 null：

1
2
3

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

插入

二叉树的插入规则：

是否有根节点，没有则设插入节点为根节点2. 比当前节点值小，转 3，否则转 43. 是否有左叶子节点，没有则设插入节点为当前节点左叶子节点，否则设其左叶子节点为当前节点，转 24. 是否有右叶子节点，没有则设插入节点为当前结点右叶子节点，否则设其右叶子节点为当前节点，转 2

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

获取最小值

在二叉树中，由于较小值都是在左节点，所以遍历完左节点即可

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

获取最大值

在二叉树中，由于较大值都是在右节点，所以遍历完右节点即可

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

获取节点数量

总节点 = 左节点 + 右节点 + 1

BST.prototype.countNode = function(node) {
    if (!node) return 0;
    return this.countNode(node.left) + this.countNode(node.right) + 1;
}

中序遍历

规则是先遍历左节点，然后到根节点，最后到右节点，图示(来自 Wikipedia)：

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

先序遍历

规则是从根节点开始，先左节点，再右节点，图示(来自 Wikipedia)：

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

后序遍历

规则是从左节点开始，再右节点，最后到根节点，图示(来自 Wikipedia)：

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

分层遍历广度查询(Breadth First Search)

分层遍历相对复杂，它是一层一层进行遍历的，图示(来自 Wikipedia)：

具体思路是先定义一个数组，然后把各层节点在每次循环压入这个数组，每次循环都将这一层节点的值打印出来，同时设置循环结束条件为当前结点为最后节点。

BST.prototype.levelTraverse = function(node) {
    if (!node) return;
    let q = [node],
        current = 0,
        last = 1;
    while (current < q.length) {
        last = q.length;
        let A = [];
        while (current < last) {
            A.push(q[current].getData());
            if (q[current].left) {
                q.push(q[current].left);
            }
            if (q[current].right) {
                q.push(q[current].right);
            }
            current++;
        }
        console.log(A.toString());
    }
}

查找

查找其实相对简单，毕竟查找数值与当前结点，小则循环到左节点，大则循环到右节点，等于则返回，查找不到返回 null。

BST.prototype.find = function(data) {
    let current = this.root;
    while (current) {
        if (Object.is(data, current.getData())) {
            return current;
        } else if (data < current.getData()) {
            current = current.left;
        } else {
            current = current.right;
        }
    }
    return null;
}

删除

这里有个视频讲解非常详细，不过要自备梯子：Delete a node from Binary Search Tree

BST.prototype.deleteNode = function(node, data) {
    if (!node) {
        return node;
    } else if (data < node.data) {
        node.left = this.deleteNode(node.left, data);
    } else if (data > node.data) {
        node.right = this.deleteNode(node.right, data);
    } else {
        if ((!node.left) && (!node.right)) {
            node = null;
        } else if (!node.left) {
            node = node.right;
        } else if (!node.right) {
            node = node.left;
        } else {
            let temp = node.right.getMin();
            node.data = temp;
            node.right = this.deleteNode(node.right, temp);
        }
    }
    return node;
}

BST.prototype.delete = function(data) {
    this.root = this.deleteNode(this.root, data);
}

全部代码在 Github。