BSTI.js

/*
 * 定义节点
 */
function Node(data) {
    this.data = data;
    this.left = null;
    this.right = null;
    this.show = show;
}

// 输出数据
function show() {
    return this.data;
}

/*
 * 定义二叉树
 */
module.exports = function BST() {
    this.root = null;
    this.insert = insert;
    this.insertNode = insertNode;
    this.preOrderTraversal = preOrderTraversal;
    this.preOrderTranversalNode = preOrderTranversalNode;
    this.inOrderTraversal = inOrderTraversal;
    this.inOrderTraversalNode = inOrderTraversalNode;
    this.postOrderTraversal = postOrderTraversal;
    this.postOrderTraversalNode = postOrderTraversalNode;
    this.getMin = getMin;
    this.getMax = getMax;
    this.search = search;
    this.remove = remove;
    this.getSuccessor = getSuccessor;
}

// 插入数据
function insert(data) {
    // 根据data创建对应的node
    var newNode = new Node(data);
    // 判断根节点是否有值
    if (this.root === null) {
        this.root = newNode;
    } else {
        // 插入该节点
        this.insertNode(this.root, newNode);
    }
}

// 判断插入节点位置，并插入该数据
function insertNode(node, newNode) {
    // 判断节点插入位置
    // 首先判断是否小于该节点的值
    if (newNode.data < node.data) {
        // 如果该节点没有左子树
        if (node.left === null) {
            node.left = newNode;
        } else {
            // 该节点左子树还有节点，进行递归判断
            this.insertNode(node.left, newNode);
        }
    } else {
        // 准备向右子树插入数据
        if (node.right === null) {
            // node的右子树上没有内容
            node.right = newNode;
        } else {
            // 该节点右子树还有节点，进行递归判断
            this.insertNode(node.right, newNode);
        }
    }
}

// 遍历方法
// 先序遍历
// handler为数据展示的方式
function preOrderTraversal(handler) {
    this.preOrderTranversalNode(this.root, handler);
}
function preOrderTranversalNode(node, handler) {
    if (node !== null) {
        handler(node.data);
        this.preOrderTranversalNode(node.left, handler);
        this.preOrderTranversalNode(node.right, handler);
    }
}
// 中序遍历
function inOrderTraversal(handler) {
    this.inOrderTraversalNode(this.root, handler);
}
function inOrderTraversalNode(node, handler) {
    if (node !== null) {
        this.inOrderTraversalNode(node.left, handler);
        handler(node.data);
        this.inOrderTraversalNode(node.right, handler);
    }
}
// 后续遍历
function postOrderTraversal(handler) {
    this.postOrderTraversalNode(this.root, handler);
}
function postOrderTraversalNode(node, handler) {
    if (node !== null) {
        this.postOrderTraversalNode(node.left, handler);
        this.postOrderTraversalNode(node.right, handler);
        handler(node.data);
    }
}


// 获取最大值和最小值
function getMin() {
    var node = this.root;
    while (node.left !== null) {
        node = node.left;
    }
    return node.data;
}
function getMax() {
    var node = this.root;
    while (node.right !== null) {
        node = node.right;
    }
    return node.data;
}

// 搜索值
/*
function search(data) {
    return this.searchNode(this.root, data);
}
// 递归的写法
function searchNode(node, data) {
    // 如果传入的node为null,那么就退出递归
    if (node === null) {
        return false;
    }
    // 判断node节点的值和传入的data大小
    if (node.data > data) { 
        // 传入的data较小, 向左边继续查找
        return this.searchNode(node.left, data);
    } else if (node.data < data) { 
        // 传入的data较大, 向右边继续查找
        return this.searchNode(node.right, data)
    } else { 
        // 相同, 说明找到了data
        return true
    }
}
*/
function search(data) {
    var node = this.root;
    while (node !== null) {
        if (node.data > data) {
            node = node.left;
        } else if (node.data < data) {
            node = node.right;
        } else {
            return true;
        }
    }
    return false;
}

// 删除节点

function remove(data) {
    // 定义临时保存的变量
    var current = this.root;
    var parent = this.root;
    var isLeftChild = true;
    // 开始查找节点
    while (current.data !== data) {
        parent = current;
        if (data < current.data) {
            isLeftChild = true;
            current = current.left;
        } else {
            isLeftChild = false;
            current = current.right;
        }
        // 如果发现current已经指向null, 那么说明没有找到要删除的数据
        if (current === null) return false;
    }
    // 删除的结点是叶结点
    if (current.left === null && current.right === null) {
        if (current == this.root) {
            this.root == null;
        } else if (isLeftChild) {
            // 如果是左子树，则置左子树为null
            parent.left = null;
        } else {
            parent.right = null;
        }
    }
    // 删除有一个子节点的节点
    else if (current.right === null) {
        if (current == this.root) {
            this.root = current.left;
        } else if (isLeftChild) {
            // 如果是左子树，则将父树的左子树指向子树的子树
            parent.left = current.left;
        } else {
            parent.right = current.left;
        }
    } else if (current.left === null) {
        if (current == this.root) {
            this.root = current.right;
        } else if (isLeftChild) {
            parent.left = current.right;
        } else {
            parent.right = current.right;
        }
    }
    // 删除有两个节点的节点
    else {
        // 获取后继节点
        var successor = this.getSuccessor(current);
        // 判断是否是根节点
        if (current == this.root) {
            this.root = successor;
        } else if (isLeftChild) {
            parent.left = successor;
        } else {
            parent.right = successor;
        }
        // 将删除节点的左子树赋值给successor
        successor.left = current.left;
    }
    return true;
}

// 找后继的方法
function getSuccessor(delNode) {
    // 使用变量保存临时的节点 
    var successorParent = delNode; // 后继节点的父节点
    var successor = delNode;    // 后继节点
    var current = delNode.right; // 要从右子树开始找
    // 寻找节点
    while (current !== null) {
        successorParent = successor;
        successor = current;
        // 向左查找
        current = current.left;
    }
    // 如果后继系节点不等于删除节点的右节点
    // 替换节点，把后继节点的右子树赋给其父节点左子树
    // 后继节点的右子树变成删除节点的右子树
    if (successor != delNode.right) {
        successorParent.left = successor.right;
        successor.right = delNode.right;
    }
    return successor;
}