JS实现二叉搜索树

作者: 小小的开发人员 | 来源:发表于2019-05-15 17:28 被阅读0次

上篇文章介绍了散列表，它是第一个非顺序数据结构。本篇学习另一种非顺序数据结构——树，它对于存储需要快速查找的数据非常有用。
树是一种分层数据的抽象模型。现实生活中最常见的树的例子是家谱，或是公司的组织架构图，如下图所示:

一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点(除了顶部的第一个节点的一个属性是深度，节点的深度取决于它的祖先节点的数量。比如，节点3有3个祖先节 9 点(5、7和11)，它的深度为3。
树的高度取决于所有节点深度的最大值。一棵树也可以被分解成层级。根节点在第0层，它的子节点在第1层，以此类推，上图中的树的高度为3(最大高度已在图中表示——第3层)。

二叉树和二叉搜索树
二叉树中的节点最多只能有两个子节点:一个是左侧子节点，另一个是右侧子节点，二叉树在计算机科学中的应用非常广泛。
二叉搜索树(BST)是二叉树的一种，但是它只允许你在左侧节点存储(比父节点)小的值，在右侧节点存储(比父节点)大(或者等于)的值。二叉搜索树将是我们在本章中要研究的数据结构。
跟前面一样，我们用JS来实现二叉搜索树：

向树中插入一个键

function BinarySearch() {

    let Node = function (key) { // 节点
        this.key = key // 键
        this.left = null // 左侧子节点
        this.right = null // 右侧子节点
    }
    let root = null // 根节点

    // 向树中插入一个新的键
    let insertNode = function (node, newNode) {
        if (newNode.key < node.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)
            }
        }
    }
    this.insert = function (key) {
        let newNode = new Node(key)
        if (root === null) { // 第一个键值
            root = newNode
        } else {
            insertNode(root, newNode)
        }
    }
let tree = new BinarySearch()
tree.insert(11)
tree.insert(7)
tree.insert(15)
tree.insert(5)
tree.insert(3)
tree.insert(9)
tree.insert(8)
tree.insert(10)
tree.insert(13)
tree.insert(12)
tree.insert(14)
tree.insert(20)
tree.insert(18)
tree.insert(25)

这时我们再插入一个值6，tree.insert(6)

树的遍历
遍历一棵树是指访问树的每个节点并对它们进行某种操作的过程。但是我们应该怎么去做呢? 应该从树的顶端还是底端开始呢? 从左开始还是从右开始呢? 访问树的所有节点有三种方式：中序、先序和后序。

中序遍历

  // 通过中序遍历方式遍历所有节点
    let inOrderTraverseNode = function (node, callback) {
        if (node != null) {
            inOrderTraverseNode(node.left, callback)
            callback(node.key)
            inOrderTraverseNode(node.right, callback)
        }
    }
    this.inOrderTraverse = function (callback) {
        inOrderTraverseNode(root, callback)
    }

先序遍历

  // 通过先序遍历方式遍历所有节点
    let preOrderTraverse = function (node, callback) {
        if (node !== null) {
            callback(node.key)
            preOrderTraverse(node.left, callback)
            preOrderTraverse(node.right, callback)
        }
    }
    this.preOrderTraverse = function (callback) {
        preOrderTraverse(root, callback)
    }

后序遍历

// 通过后序遍历方式遍历所有节点
    let postOrderTraverse = function (node, callback) {
        if (node !== null) {
            postOrderTraverse(node.left, callback)
            postOrderTraverse(node.right, callback)
            callback(node.key)
        }
    }
    this.postOrderTraverse = function (callback) {
        postOrderTraverse(root, callback)
    }

搜索树中的值

搜最小值与最大值

    // 返回树中最小的键
    let minNode = function (node) {
        if (node) {
            while(node && node.left !== null) {
                node = node.left
            }
            return node.key
        }
        return null
    }
    this.min = function () {
        return minNode(root)
    }

    // 返回树中最大的键
    let maxNode = function (node) {
        if (node) {
            while(node && node.right !== null) {
                node = node.right
            }
            return node.key
        }
        return null
    }
    this.max = function () {
        return maxNode(root)
    }

搜索特定值

     // 在树中查找一个键，如果节点存在，则返回true；如果节点不存在，则返回false
    let searchNode = function (node, key) {
        if (node === null) {
            return false
        }
        if (key < node.key) {
            return searchNode(node.left, key)
        } else if (key > node.key) {
            return searchNode(node.right, key)
        } else { // 相等
            return true
        }
    }
    this.search = function (key) {
        return searchNode(root, key)
    }

移除指定键

    // 从树中移除指定键
    let removeNode = function (node, key) {
        if (node === null) {
            return null
        }
        if (key < node.key) {
            node.left = removeNode(node.left, key)
            return node
        } else if (key > node.key) {
            node.right = removeNode(node.right, key)
            return node
        } else {
            if (node.left === null && node.right === null) {
                node = null
                return node
            }
            if (node.left === null) {
                node = node.right
                return node
            } else if (node.right === null) {
                node = node.left
                return node
            }
            let aux = minNode(node.right)
            node.key = aux.key
            node.right = removeNode(node.right, aux.key)
            return node
        }
    }
    this.remove = function (key) {
        root = removeNode(root, key)
    }

完整代码：

function BinarySearch() {

    let Node = function (key) { // 节点
        this.key = key // 键
        this.left = null // 左侧子节点
        this.right = null // 右侧子节点
    }
    let root = null // 根节点

    // 向树中插入一个新的键
    let insertNode = function (node, newNode) {
        if (newNode.key < node.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)
            }
        }
    }
    this.insert = function (key) {
        let newNode = new Node(key)
        if (root === null) { // 第一个键值
            root = newNode
        } else {
            insertNode(root, newNode)
        }
    }

    // 通过中序遍历方式遍历所有节点
    let inOrderTraverseNode = function (node, callback) {
        if (node != null) {
            inOrderTraverseNode(node.left, callback)
            callback(node.key)
            inOrderTraverseNode(node.right, callback)
        }
    }
    this.inOrderTraverse = function (callback) {
        inOrderTraverseNode(root, callback)
    }

    // 通过先序遍历方式遍历所有节点
    let preOrderTraverse = function (node, callback) {
        if (node !== null) {
            callback(node.key)
            preOrderTraverse(node.left, callback)
            preOrderTraverse(node.right, callback)
        }
    }
    this.preOrderTraverse = function (callback) {
        preOrderTraverse(root, callback)
    }

    // 通过后序遍历方式遍历所有节点
    let postOrderTraverse = function (node, callback) {
        if (node !== null) {
            postOrderTraverse(node.left, callback)
            postOrderTraverse(node.right, callback)
            callback(node.key)
        }
    }
    this.postOrderTraverse = function (callback) {
        postOrderTraverse(root, callback)
    }

    // 返回树中最小的键
    let minNode = function (node) {
        if (node) {
            while(node && node.left !== null) {
                node = node.left
            }
            return node.key
        }
        return null
    }
    this.min = function () {
        return minNode(root)
    }

    // 返回树中最大的键
    let maxNode = function (node) {
        if (node) {
            while(node && node.right !== null) {
                node = node.right
            }
            return node.key
        }
        return null
    }
    this.max = function () {
        return maxNode(root)
    }

    // 在树中查找一个键，如果节点存在，则返回true；如果节点不存在，则返回false
    let searchNode = function (node, key) {
        if (node === null) {
            return false
        }
        if (key < node.key) {
            return searchNode(node.left, key)
        } else if (key > node.key) {
            return searchNode(node.right, key)
        } else { // 相等
            return true
        }
    }
    this.search = function (key) {
        return searchNode(root, key)
    }

    // 从树中移除指定键
    let removeNode = function (node, key) {
        if (node === null) {
            return null
        }
        if (key < node.key) {
            node.left = removeNode(node.left, key)
            return node
        } else if (key > node.key) {
            node.right = removeNode(node.right, key)
            return node
        } else {
            if (node.left === null && node.right === null) {
                node = null
                return node
            }
            if (node.left === null) {
                node = node.right
                return node
            } else if (node.right === null) {
                node = node.left
                return node
            }
            let aux = minNode(node.right)
            node.key = aux.key
            node.right = removeNode(node.right, aux.key)
            return node
        }
    }
    this.remove = function (key) {
        root = removeNode(root, key)
    }
}
function printNode(value) {
    console.log(value)
}
let tree = new BinarySearch()
tree.insert(11)
tree.insert(7)
tree.insert(15)
tree.insert(5)
tree.insert(3)
tree.insert(9)
tree.insert(8)
tree.insert(10)
tree.insert(13)
tree.insert(12)
tree.insert(14)
tree.insert(20)
tree.insert(18)
tree.insert(25)
tree.insert(6)
tree.inOrderTraverse(printNode) // 3 5 6 7 8 9 10 11 12 13 14 15 18 20 25
tree.preOrderTraverse(printNode) // 11 7 5 3 6 9 8 10 15 13 12 14 20 18 25
tree.postOrderTraverse(printNode) // 3 6 5 8 10 9 7 12 14 13 18 25 20 15 11
console.log(tree.min()) // 3
console.log(tree.max()) // 25
console.log(tree.search(10)) // true
console.log(tree.search(100)) // false
tree.remove(25)
tree.inOrderTraverse(printNode) // 3 5 6 7 8 9 10 11 12 13 14 15 18 20

JS实现二叉搜索树

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读