二叉搜索树

前端 0 399 0
发表于: 2021-02-18 00:42:41

简介: 暂无~

二叉树(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)

查找

树的遍历

先序查找

遍历过程:

  1. 访问根节点
  2. 先序遍历左节点
  3. 先序遍历右节点
// 先序遍历
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
}
数据结构和算法

最后更新于:2021-02-20 08:56:24

欢迎评论留言~
0/400
支持markdown
Comments | 0 条留言
按时间
按热度
目前还没有人留言~