第5章 树

二叉搜索树(BST)

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

class BinarySearchTree {
    constructor() {
        this.root = null;
    }

    //1.向树中插入一个新的键
    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);
            } else {
                this.insertNode(node.left, key);
            }
        } else {
            if (node.right === null) {
                node.right = new Node(key);
            } else {
                this.insertNode(node.right, key);
            }
        }
    }

    //2.先序遍历
    preOrderTraverse() {
        this.preOrderTraverseNode(this.root);
    }

    preOrderTraverseNode(node) {
        if (node !== null) {
            console.log(node.key);
            this.preOrderTraverseNode(node.left);
            this.preOrderTraverseNode(node.right);
        }
    }

    //3.中序遍历
    inOrderTraverse() {
        this.inOrderTraverseNode(this.root);
    }

    inOrderTraverseNode(node) {
        if (node !== null) {
            this.inOrderTraverseNode(node.left);
            console.log(node.key);
            this.inOrderTraverseNode(node.right);
        }
    }

    //4.后序遍历
    postOrderTraverse() {
        this.postOrderTraverseNode(this.root);
    }

    postOrderTraverseNode(node) {
        if (node !== null) {
            this.postOrderTraverseNode(node.left);
            this.postOrderTraverseNode(node.right);
            console.log(node.key);
        }
    }

    //5.最小值
    min() {
        return this.minNode(this.root);
    }

    minNode(node) {
        let current = node;
        while (current != null && current.left != null) {
            current = current.left;
        }
        return current;
    }

    //6.最大值
    max() {
        return this.maxNode(this.root);
    }

    maxNode(node) {
        let current = node;
        while (current != null && current.right != null) {
            current = current.right;
        }
        return current;
    }

    //7.搜索一个特定的值
    search(key) {
        return this.searchNode(this.root, key);
    }

    searchNode(node, key) {
        if (node == null) {
            return false;
        }
        if (key > node.key) {
            return this.searchNode(node.right, key);
        } else if (key < node.key) {
            return this.searchNode(node.left, key);
        } else {
            return true;
        }
    }

    //8.从树中移除某个键
    remove(key) {
        this.root = 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 {
            //key == node.key
            //第一种情况——移除的是叶子节点
            if (node.left == null && node.right == null) {
                node = null;
                return node;
            }

            //第二种情况——移除有一个叶子节点的节点
            if (node.left == null) {
                node = node.right;
                return node;
            } else if (node.right == null) {
                node = node.left;
                return node;
            }

            //第三种情况——移除有两个叶子节点的节点
            const aux = this.minNode(node.right);
            node.key = aux.key;
            node.right = this.removeNode(node.right, aux.key);
            return node;
        }
    }
}

自平衡树(AVL)

红黑树

二叉堆

堆排序