二叉树（Binary tree）

二叉搜索树（Binary Search Tree）

什么是二叉搜索数？

二叉搜索树，又成二叉查找树，二叉排序树。

若任意结点的左子树不空，则左子树上所有结点的值都不大于它的根结点的值。

若任意结点的右子树不空，则右子树上所有结点的值都不小于它的根结点的值。

任意结点的左、右子树也分别为二叉搜索树

复杂度

如果有n个元素，则复杂度为：O(logn)

方法

插入

// 二叉搜索树（Binary Search Tree）
function BinarySearchTree() {

    // 节点对象类
    function Node(key) {
        this.key = key
        this.left = null
        this.right = null
    }
    // 属性
    this.root = null

    // 方法1：插入
    BinarySearchTree.prototype.insert = function (key) {
        // 先根据key创建节点
        var newNode = new Node(key)
        if (this.root == null) {
            this.root = newNode
        } else {
            insertNode(this.root, newNode)
        }

        function insertNode(node, newNode) {
            if (node.key > newNode.key) {
                // 两个节点对比，如果新节点比对比的节点小，则向左查找
                if (node.left == null) {
                    // 如果左边没有节点，直接把新节点给左边的节点
                    node.left = newNode
                } else {
                    // 如果左边有节点，再次比较左节点和新节点的大小
                    insertNode(node.left, newNode)
                }
            } else {
                // 如果新节点比对比的节点大，则向右查找
                if (node.right == null) {
                    // 如果右边没有节点，直接把新节点给右边的节点
                    node.right = newNode
                } else {
                    // 如果右边有节点，再次比较右节点和新节点的大小
                    insertNode(node.right, newNode)
                }
            }
        }
    }
}

var bst = new BinarySearchTree()
bst.insert(11)
bst.insert(7)
bst.insert(15)
bst.insert(5)
bst.insert(3)
bst.insert(9)
// ...
console.log(bst)

查找

树的遍历

先序查找

遍历过程：

访问根节点

先序遍历左节点

先序遍历右节点

// 先序遍历
BinarySearchTree.prototype.preOrder = function (cb) {
    preOrderNode(this.root, cb)

    function preOrderNode(node, cb) {
        if (node != null) {
            cb(node)
            preOrderNode(node.left, cb)
            preOrderNode(node.right, cb)
        }
    }
}

中序查找

// 中序遍历
BinarySearchTree.prototype.preOrder = function (cb) {
    preOrderNode(this.root, cb)

    function preOrderNode(node, cb) {
        if (node != null) {
            preOrderNode(node.left, cb)
            cb(node)
            preOrderNode(node.right, cb)
        }
    }
}

后序查找

// 后序遍历
BinarySearchTree.prototype.preOrder = function (cb) {
    preOrderNode(this.root, cb)

    function preOrderNode(node, cb) {
        if (node != null) {
            preOrderNode(node.left, cb)
            preOrderNode(node.right, cb)
            cb(node)
        }
    }
}

搜索

最大值

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

最小值

// 最小值
BinarySearchTree.prototype.min = function () {
    var node = this.root
    var res
    while (node != null) {
        res = node
        node = node.left
    }
    return res
}

指定值

// 指定值，给一个key，查找对应的节点，如果找到，返回对应节点，找不到返回false
BinarySearchTree.prototype.search = function (key) {
    var node = this.root
    var res = false
    while (node != null) {
        // 如果传进来的key比对比的节点key值大，则向右查找
        if (node.key < key) {
            node = node.right
        } else if (node.key > key) {
            node = node.left
        } else {
            return node
        }
    }
    return res
}