javascript封装二叉搜索树（BST）

二叉搜索树(Binary Search Tree) 特点： 1、若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值 2、若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值.

如图示：

二叉搜索树的插入节点：

//插入数据
    BinarySearchTree.prototype.insert = function (key) {
        let newNode = new Node(key)  //创建新节点

        //判断跟节点是否有值
        if (this.root === null) {
            this.root = newNode
        } else {
            this.insertNode(this.root,newNode)
        }

    }

    //递归寻找适合的节点插入新节点
    BinarySearchTree.prototype.insertNode = function (node,newNode) {
        if (newNode.key < node.key) { //向左查找
            if (node.left === null) {
                node.left = newNode
            } else {
                this.insertNode(node.left,newNode)
            }
        } else { //向右查找
            if (node.right === null) {
                node.right = newNode
            } else {
                this.insertNode(node.right,newNode)
            }
        }
    }

二叉搜索树的三种遍历方式：

先序遍历：

javascript封装二叉搜索树（BST）

代码递归实现：

//先序遍历的递归函数
    BinarySearchTree.prototype.preOrderTraversalNode = function (node) {
        if (node !== null) {
            console.log(node.key) //打印遍历的节点的值
            this.preOrderTraversalNode(node.left) //处理左节点
            this.preOrderTraversalNode(node.right) //处理右节点
        }
    }

中序遍历

javascript封装二叉搜索树（BST）

代码递归实现：

//中序遍历的递归函数
    BinarySearchTree.prototype.midOrderTraversalNode = function (node) {
        if (node !== null) {
            this.midOrderTraversalNode(node.left)
            console.log(node.key)
            this.midOrderTraversalNode(node.right)
        }
    }

后序遍历

javascript封装二叉搜索树（BST）

代码递归实现：

//后序遍历的递归函数
    BinarySearchTree.prototype.postOrderTraversalNode = function (node) {

        if (node !== null) {
            this.postOrderTraversalNode(node.left)

            this.postOrderTraversalNode(node.right)
            console.log(node.key)
        }
    }

二叉搜索树的最大值和最小值：

//最小值
    BinarySearchTree.prototype.min = function () {
        let node = this.root

        while (node.left !== null) {
            node = node.left
        }
        return node.key
    }

    //最大值
    BinarySearchTree.prototype.max = function () {
        let node = this.root

        while (node.right !== null) {
            node = node.right
        }
        return node.key
    }

二叉搜索树寻找特定的值

//寻找特定的值
    BinarySearchTree.prototype.search = function (key) {
        return this.searchNode(this.root,key)
    }

    //递归寻找特定的值
    BinarySearchTree.prototype.searchNode = function (node,key) {
        if (node === null) { 
            return false
        }
        if (node.key > key) {
           return this.searchNode(node.left,key)
        } else if (node.key < key) {
            return this.searchNode(node.right,key)
        } else {
            return true
        }

删除节点：有三种情况 1、删除叶子节点 2、删除只有一个子节点的节点3、删除有两个子节点的节点

//删除节点
    BinarySearchTree.prototype.remove = function (key) {
        //1、找到要删除的节点
        //2、定义变量 保存信息
        let current = this.root
        let parent = null
        let isLeftChild = true //标记要删除的节点是父节点的左子节点还是右子节点

        //开始寻找删除的节点
        while (current.key !== key) {
            parent = current
            if (key < current.key) {
                isLeftChild = true
                current = current.left
            } else {
                isLeftChild = false
                current = current.right
            }
            if (current === null) return false //不存在 要删除的节点
        }

        //删除的是叶子节点
        if (current.left === null && current.right === null) {
            if (current === this.root) {
                this.root = null
            } else if (isLeftChild) {
                parent.left = null
            } else {
                parent.right = null
            }
        }

        //删除只有一个子节点的节点
       else if (current.right === null) { //current 没有右子节点
           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) { //current 没有左子节点
           if (current === this.root) {
               this.root = current.right
           } else if (isLeftChild) {
               parent.left = current.right
           } else {
               parent.right = current.right
           }
        }
       else { //删除的节点有两个子节点
           //获取后继节点
           let successor = this.getSuccessor(current)

            if (current === this.root) {
                this.root = successor
            } else if (isLeftChild) {
                parent.left = successor
            } else {
                parent.right = successor
            }
           //将删除节点的左子树 = current.left
            successor.left = current.left
        }
    }

    //寻找后继的办法
    BinarySearchTree.prototype.getSuccessor = function (delNode) {
        //定义变量 保存找到的后继
        let successor = delNode
        let current = delNode.right
        let successorParent = delNode

        //循环查找
        while (current !== null) { //找到delNode右边最小值的节点 为后继节点
            successorParent = successor
            successor = current
            current = current.left
        }
        //判断寻找的后继节点是否直接就是delNode的right节点
        if (successor !== delNode.right) {
            successorParent.left = successor.right
            successor.right = delNode.right
        }

        return successor
    }

整体代码

//封装二叉搜索树
function BinarySearchTree() {

    //内部节点类
    function Node(key) {
        this.left = null
        this.key = key
        this.right = null
    }

    this.root = null

    //插入数据
    BinarySearchTree.prototype.insert = function (key) {
        let newNode = new Node(key)  //创建新节点

        //判断跟节点是否有值
        if (this.root === null) {
            this.root = newNode
        } else {
            this.insertNode(this.root,newNode)
        }

    }

    //递归寻找适合的节点插入新节点
    BinarySearchTree.prototype.insertNode = function (node,newNode) {
        if (newNode.key < node.key) { //向左查找
            if (node.left === null) {
                node.left = newNode
            } else {
                this.insertNode(node.left,newNode)
            }
        } else { //向右查找
            if (node.right === null) {
                node.right = newNode
            } else {
                this.insertNode(node.right,newNode)
            }
        }
    }

    //先序遍历
    BinarySearchTree.prototype.preOrderTraversal = function () {
        this.preOrderTraversalNode(this.root)
    }

    //先序遍历的递归函数
    BinarySearchTree.prototype.preOrderTraversalNode = function (node) {

        if (node !== null) {
            console.log(node.key) //打印遍历的节点的值
            this.preOrderTraversalNode(node.left) //处理左节点
            this.preOrderTraversalNode(node.right) //处理右节点
        }

    }

    //中序遍历
    BinarySearchTree.prototype.midOrderTraversal = function () {
        this.midOrderTraversalNode(this.root)
    }

    //中序遍历的递归函数
    BinarySearchTree.prototype.midOrderTraversalNode = function (node) {

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

    //后序遍历
    BinarySearchTree.prototype.postOrderTraversal = function () {
        this.postOrderTraversalNode(this.root)
    }

    //后序遍历的递归函数
    BinarySearchTree.prototype.postOrderTraversalNode = function (node) {

        if (node !== null) {
            this.postOrderTraversalNode(node.left)

            this.postOrderTraversalNode(node.right)
            console.log(node.key)
        }
    }

    //最小值
    BinarySearchTree.prototype.min = function () {
        let node = this.root

        while (node.left !== null) {
            node = node.left
        }
        return node.key
    }

    //最大值
    BinarySearchTree.prototype.max = function () {
        let node = this.root

        while (node.right !== null) {
            node = node.right
        }
        return node.key
    }

    //寻找特定的值
    BinarySearchTree.prototype.search = function (key) {
        return this.searchNode(this.root,key)
    }

    //递归寻找特定的值
    BinarySearchTree.prototype.searchNode = function (node,key) {
        if (node === null) {
            return false
        }
        if (node.key > key) {
           return this.searchNode(node.left,key)
        } else if (node.key < key) {
            return this.searchNode(node.right,key)
        } else {
            return true
        }

    }

    //删除节点
    BinarySearchTree.prototype.remove = function (key) {
        //1、找到要删除的节点
        //2、定义变量 保存信息
        let current = this.root
        let parent = null
        let isLeftChild = true //标记要删除的节点是父节点的左子节点还是右子节点

        //开始寻找删除的节点
        while (current.key !== key) {
            parent = current
            if (key < current.key) {
                isLeftChild = true
                current = current.left
            } else {
                isLeftChild = false
                current = current.right
            }
            if (current === null) return false //不存在 要删除的节点
        }

        //删除的是叶子节点
        if (current.left === null && current.right === null) {
            if (current === this.root) {
                this.root = null
            } else if (isLeftChild) {
                parent.left = null
            } else {
                parent.right = null
            }
        }

        //删除只有一个子节点的节点
       else if (current.right === null) { //current 没有右子节点
           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) { //current 没有左子节点
           if (current === this.root) {
               this.root = current.right
           } else if (isLeftChild) {
               parent.left = current.right
           } else {
               parent.right = current.right
           }
        }
       else { //删除的节点有两个子节点
           //获取后继节点
           let successor = this.getSuccessor(current)

            if (current === this.root) {
                this.root = successor
            } else if (isLeftChild) {
                parent.left = successor
            } else {
                parent.right = successor
            }
           //将删除节点的左子树 = current.left
            successor.left = current.left
        }
    }

    //寻找后继的办法
    BinarySearchTree.prototype.getSuccessor = function (delNode) {
        //定义变量 保存找到的后继
        let successor = delNode
        let current = delNode.right
        let successorParent = delNode

        //循环查找
        while (current !== null) { //找到delNode右边最小值的节点 为后继节点
            successorParent = successor
            successor = current
            current = current.left
        }
        //判断寻找的后继节点是否直接就是delNode的right节点
        if (successor !== delNode.right) {
            successorParent.left = successor.right
            successor.right = delNode.right
        }

        return successor
    }
}

const  bst = new BinarySearchTree()

bst.insert(11)
bst.insert(7)
bst.insert(15)
bst.insert(5)
bst.insert(3)
bst.insert(9)
bst.insert(8)
bst.insert(10)
bst.insert(13)
bst.insert(12)
bst.insert(14)
bst.insert(20)
bst.insert(18)
bst.insert(25)
bst.insert(6)

//测试遍历

bst.preOrderTraversal()
bst.midOrderTraversal()
bst.postOrderTraversal()

console.log(bst.min());
console.log(bst.max());

console.log(bst.search(25))
console.log(bst.search(100))
console.log(bst.search(7))


bst.remove(7)
bst.remove(15)
bst.remove(10)
bst.postOrderTraversal()

javascript封装二叉搜索树（BST）

继续阅读

D. Ehab the Xorcist(构造+思维)

关于 underscore 中模板引擎的应用示例

查找算法之二分查找查找算法之二分查找

JAVA高效编程指南

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

【JavaScript语法】函数对象的浅拷贝、深拷贝

【数据结构】医院选址

JS--运算符

数组和类数组

[转]ISUP信令的IAM消息详细内容

jquery_126_demo

笔试面试题目：滑动窗口(二)

交通/城市相关的公开的数据集上学时整理的Xie et al., 2020收集的

数据结构与算法（27）——排序（二）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

Linux设备模型（中）之上层容器