JavaScript二叉搜索树/二叉排序树/二叉查找树的封装

前言

最近在学习二叉树，复盘和总结一下这个东东。不说了都是泪，奉劝各位在学校的课程上认认真真学习数据结构，这是个好东西

正文

二叉搜索树/二叉排序树/二叉查找树，英文:BST,Binary Search tree，其实这三个名字是同一个二叉树，这里就用二叉搜索树来说。

二叉搜索树

二叉搜索树是什么，这可能要结合性质(生成条件)来说

1.二叉搜索树是一个二叉树，可以为空
2.如果不为空，需要满足以下的性质
 1. 非空左子树的所有键值小于根节点的键值
 2. 非空右子树的所有键值大于根节点的键值
 3. 左、 右子树本身也是二叉搜索树
总结的话就是，对于每一个节点来说，键值小的的左边，键值大的在右边(小左大右)。

我们来看一张图，可以更好的理解

以根节点5为例，比它小的都在左子树，比它大的都在右子树
其他的子节点也一样，这就是一个二叉搜索树

代码实现

结合上面的图我们可以看到，其实二叉树是由节点构成的，节点里有键值和指向左右的两个箭头，所以可以看成一个节点有三个属性,我们先创建一个BinarySearchTree类

BinarySearchTree类

 function BinarySearchTree() {
             //创建一个节点类
            function Node(key) {
                // 一个节点有三个属性，一个是键，另外两个是指向左右两边的节点
                this.key = key
                this.left = null
                this.right = null
            }

            //根节点
            this.root = null
     }

方法

接下来就是方法，下面的方法用了递归思想，第一个是插入节点的方法

insert(key): 向树中插入一个新的键

原理:通过递归的方法，新Node和根节点，其他节点进行比较，新Node大于就放右边，小于就放左边，
每个节点都要比较，直到为空
    BinarySearchTree.prototype.insert = function (key) {
        // 创建一个要插入的键
        var newNode = new Node(key)

        // 先判断是否有根节点，如果没有，那插入的键就成为根节点
        if (this.root == null) {
            this.root = newNode
        } else {
            this.insertNode(this.root, newNode)
        }

    }
    // 递归函数
    BinarySearchTree.prototype.insertNode = function (node, newNode) {
        // node是指要比较的那个节点

        if (newNode.key > node.key) { //向右查找
            // 因为要插入到右边，那就要判断右边是否有节点

            if (node.right == null) { //如果没有，插入的节点就成为右节点
                node.right = newNode
            } else { //如果有，那就需要在进行递归判断，再次调用这个函数，直到上一步骤失败
                this.insertNode(node.right, newNode)
            }
        } else { //向左查找 操作同上
            if (node.left == null) {
                node.left = newNode
            } else {
                this.insertNode(node.left, newNode)
            }
        }
    }

这里先不测试，结合后面的遍历一起测试

preOrderTraverse: 通过先序遍历遍历所有节点

理解其中一个，其他的遍历也差不多会明白

原理：先访问根节点，在访问其左子树，在访问右子树
    BinarySearchTree.prototype.preOrderTraverse = function (handler) {
        // 从根节点开始遍历
        this.preOrderTraverseNode(this.root, handler)
    }
    // 先序遍历递归函数
    BinarySearchTree.prototype.preOrderTraverseNode = function (node, handler) {
        if (node != null) { //判断经过的节点是否为空
            handler(node.key) 
            //因为是遍历，所有要看到结果，用一个函数来处理，将经过的节点加入到字符串
    
            //如果有左节点，在执行我们的遍历函数，将节点加入到字符串中，一直到左节点为空
            this.preOrderTraverseNode(node.left, handler)

            // 如果最后一个左节点为叶子节点，就在判断它是否还有右节点
            // 如果有，就继续递归执行函数。
            // 如果没有，那么当前节点就完成了上一次递归调用，开始判断上一个节点的递归函数
            this.preOrderTraverseNode(node.right, handler)

        }
    }

inOrderTraverse: 通过中序(升序)遍历遍历所有节点

其实就只是改变调用顺序，后序遍历也是

原理:先访问左子树，在访问根节点，在访问右子树，对树进行排序操作如果是数字的话，就小到大排列
    BinarySearchTree.prototype.inOrderTraverse = function (handler) {
        this.inOrderTraverseNode(this.root, handler)
        // 为什么是this.root，因为只能从根节点开始进入
    }
    // 中序遍历递归函数
    BinarySearchTree.prototype.inOrderTraverseNode = function (node, handler) {
        if (node != null) {
            // 从根节点开始进入，如果他有左节点，就会不断进行递归，会一直遍历到最左叶子节点

            // 到了最左叶子节点，就结束将该节点加入到字符串中，在判断是否有右节点
            // 没有就回到上个函数，那么函数里的左节点判断就结束麻，将当前节点加入字符串，在判断右边
            // ....
            // 如果进入到一个新支，有左节点，有因为递归调用，所有函数又来到最左叶子节点

            //可以把根节点的左边看成一个左节点的函数判断，所有判断结束，中间就打印根节点，所以是中序遍历
            this.inOrderTraverseNode(node.left, handler)
            handler(node.key)
            this.inOrderTraverseNode(node.right, handler)
        }
    }

postOrderTraverse: 通过后序遍历遍历所有节点

这里就不在注释说明了

原理:先访问左子树，在访问右子树，在访问根节点
    BinarySearchTree.prototype.postOrderTraverse = function (handler) {
        this.postOrderTraverseNode(this.root, handler)
    }
    BinarySearchTree.prototype.postOrderTraverseNode = function (node, handler) {
        if (node != null) {
            // 其实道理差不多，就不在说了
            this.postOrderTraverseNode(node.left, handler)
            this.postOrderTraverseNode(node.right, handler)
            handler(node.key)
        }
    }

min: 返回树中最小的值键

这个没啥好说的，就是你想的那样

BinarySearchTree.prototype.min = function () {
        var node = this.root //获取根节点
        // var key=null    创建一个key来返回值
        // 依次向右不断查找，因为node一直有值，所以会循环，直到node=null
        while (node != null) {
            key = node.key
            node = node.left
        }
        return key
    }

max: 返回树中最大的值键

    BinarySearchTree.prototype.max = function () {
        var node = this.root //
        var key = null
        while (node != null) {
            key = node.key
            node = node.right
        }
        return key
    }

search(key): 在树中查找一个键，如果节点存在，返回true

BinarySearchTree.prototype.search = function (key) {
        return this.searchNode(this.root, key)
    }
//递归
BinarySearchTree.prototype.searchNode = function (node, key) {
        if (node === null) { //判断根节点是否为空，以及后面递归的节点
            return false
        }

        if (key > node.key) {
            // 递归之后，key继续和后面的节点比较
            return this.searchNode(node.right, key)
        } else if (key < node.key) {
            return this.searchNode(node.left, key)
        } else {
            return true
        }
    }

测试

var bst = new BinarySearchTree()
    // 测试插入
    bst.insert(7)
    bst.insert(66)
    bst.insert(5)
    bst.insert(17)
    bst.insert(11)
    bst.insert(3)

    // 测试先序
    let res1 = ''
    bst.preOrderTraverse(function (key) {
        res1 += key + ' '
    })
    console.log(res1)
    //测试中序
    res2 = ''
    bst.inOrderTraverse(function (key) {
        res2 += key + ' '
    })
    console.log(res2)
    //测试后序
    res2 = ''
    bst.postOrderTraverse(function (key) {
        res2 += key + ' '
    })
    console.log(res2)
    //大小
    console.log(bst.min())
    console.log(bst.max())
    //查找
    console.log(bst.search(2))
    console.log(bst.search(66))

树图和结果图

总结

其实还有一个方法，就是remove，这个方法有点难，到时候在写一篇单独发

想出二叉搜索树的真是神仙,牛皮。没啥总结，我觉得注释就是我的总结