js中的二叉树

二叉树（Binary Tree）是n（n>=0）个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

每个二叉树都有自己的根节点，每个节点最多有两个子树，较小的值存在于左侧子树中，较大的值存在于右侧子树中。

正是由于这种特性，二叉树的查找和删除会非常快。

可以创建一个节点类，用于保存树的节点数据。

class BinaryNode {
    constructor(key, left = null, right = null) {
        this.key = key
        this.left = left
        this.right = right
    }
}

首先实现二叉树的添加节点方法insert(key)。

insert(key) {
    const node = new BinaryNode(key)
    if (this.root === null) {
        this.root = node
    } else {
        let current = this.root

        while (true) {
            if (key < current.key) {
                if (current.left === null) {
                    current.left = node
                    break
                }
                current = current.left
            } else {
                if (current.right === null) {
                    current.right = node
                    break
                }
                current = current.right
            }
        }
    }
}

首先判断根节点是否为空，为空说明二叉树还是空的，直接赋值给根节点即可。然后遍历二叉树，较小的值遍历左侧，较大的值遍历右侧，直到遍历返回结果为空，说明遍历到了最终的子节点，然后插入该元素即可。

然后是删除节点，这个方法是二叉树中实现最复杂的，因为要考虑到很多种不同的情况。

_removeNode(node, key) {

    if (node === null) {
        return null
    }

    if (key < node.key) {
        node.left = this._removeNode(node.left, key)
        return node
    } else if (key > node.key) {
        node.right = this._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
        } else {
            const minNode = this._findMinNode(node.right)
            node.key = minNode.key
            node.right = this._removeNode(node.right, minNode.key)
            return node
        }
    }
}

1、 当删除节点为空，直接返回空。
2、 当值小于当前节点值时，递归当前节点的左侧节点，然后将左侧递归的结果返回。
3、 当值大于当前节点值时，递归当前节点的右侧节点，然后将右侧递归的结果返回。
4、 当值和当前节点的值相等时，这里又要考虑到四种情况。
5、 第一种情况，当为单个节点时，即没有左右节点，直接将该节点置为空，返回空即可。
6、 第二种情况，当左侧节点不存在时，就返回右侧节点。
7、 第三种情况，当右侧节点不存在时，返回左侧节点。
8、 第四种情况，当节点有左右节点时，这是，需要找到右侧节点的最小节点，然后删除这个最小节点，返回这个最小节点即可。

_findMinNode(node)的实现

_findMinNode(node) {
    while (node.left) {
        node = node.left
    }
    return node
}

全部代码实现如下

class BinaryNode {
    constructor(key, left = null, right = null) {
        this.key = key
        this.left = left
        this.right = right
    }
}

class BinaryTree {
    constructor() {
        this.root = null
    }

    insert(key) {
        const node = new BinaryNode(key)
        if (this.root === null) {
            this.root = node
        } else {
            let current = this.root

            while (true) {
                if (key < current.key) {
                    if (current.left === null) {
                        current.left = node
                        break
                    }
                    current = current.left
                } else {
                    if (current.right === null) {
                        current.right = node
                        break
                    }
                    current = current.right
                }
            }
        }
    }

    remove(key) {
        return this._removeNode(this.root, key)
    }

    _removeNode(node, key) {

        if (node === null) {
            return null
        }

        if (key < node.key) {
            node.left = this._removeNode(node.left, key)
            return node
        } else if (key > node.key) {
            node.right = this._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
            } else {
                const minNode = this._findMinNode(node.right)
                node.key = minNode.key
                node.right = this._removeNode(node.right, minNode.key)
                return node
            }
        }
    }

    _findMinNode(node) {
        while (node.left) {
            node = node.left
        }
        return node
    }

    getHead() {
        return this.root
    }

    //先序遍历
    preOrder(node) {
        if (node) {
            console.log(`key: ${node.key}`);
            this.preOrder(node.left)
            this.preOrder(node.right)
        }
    }

    //中序遍历
    inOrder(node) {
        if (node) {
            this.inOrder(node.left)
            console.log(`key: ${node.key}`);
            this.inOrder(node.right)
        }
    }

    //后序遍历
    postOrder(node) {
        if (node) {
            this.postOrder(node.left)
            this.postOrder(node.right)
            console.log(`key: ${node.key}`);
        }
    }

    min() {
        let current = this.root
        while (current.left) {
            current = current.left
        }
        return current.key
    }

    max() {
        let current = this.root
        while (current.right) {
            current = current.right
        }
        return current.key
    }
}

测试效果

const bst = new BinaryTree()
bst.insert(10)
bst.insert(12)
bst.insert(15)
bst.insert(8)
bst.insert(6)
bst.postOrder(bst.inOrder(bst.getHead()))

//输出:
// key: 6
// key: 8
// key: 10
// key: 12
// key: 15