基础数据结构--手动实现二叉查找树及其相关方法

二叉树和二叉查找树

• 二叉树是一种特殊的保存数据的数据结构。二叉树每个节点的子节点不允许超过两个。可以写出高效的程序在树中插入、查找和删除数据。
• 二叉查找树是一种特殊的二叉树。相对较小的值保存在左节点中，较大的值保存在右节点中。

实现二叉查找树

//  先创建一个节点对象
function Node (data, left, right) {
    this.data = data
    this.left = left
    this.right = right
    this.show = show
    //  记数
    this.count = 1
}
function show () {
    return this.data
}
//  创建二叉查找树
function BST () {
    //  初始化根节点为null
    this.root = nul
    //  插入节点
    this.insert = insert
    //  遍历二叉树
    this.inOrder = inOrder
    //  查找指定元素
    this.find = find
    //  查找最小值
    this.getMin = getMin
    //  查找最大值
    this.getMax = getMax
    //  删除节点
    this.remove = remove
    //  更新记数
    this.update = update
}
function insert (data) {
    //  创建一个节点
    var n = new Node(data, null , null)
    //  如果根节点不存在，就把当前节点当作根节点
    if (!this.root) {
        this.root = n
    } else {
        //  否则将根节点设为当前节点
        var current = this.root
        var parent
        while(true) {
            parent = current
            //  如果，插入的数据小于当前节点数据
            //  将插入的数据放到左节点，否则放到右节点
            if (data < current.data) {
                current = current.left
                if (current === null) {
                    parent.left = n
                    break
            } else {
                current = current.right
                if (current === null) {
                    parent.right = n
                    break
                }
            }
        }
    }
}
//  遍历二叉查找树的方式有三种：
//  中序：中序遍历按照节点上的键值，以升序访问 BST 上的所有节点。
//  先序：先序遍历先访问根节点，然后以同样方式访问左子树和右子树。
//  后序：后序 遍历先访问叶子节点，从左子树到右子树，再到根节点。
function inOrder (node) {
    if (!(node === null)) {
        inOrder(node.left)
        inOrder(node.right)
    }
}
// 二叉查找树上查找
// (1)给定值：需要比较该值和当前节点上的值的大小。通过比较，就能确定如果给定值不在当前节点时，该向左遍历还是向右遍历。
// (2)最小值：最小值总在左子节点上，只需要遍历左子节点即可
// (3)最大值：最小值总在右边子节点上，只需要遍历右子节点即可
function find (data) {
    let current = this.root
    while(current !== null) {
        if (current.data === data) {
            return current
        } else if (current.data > data) {
            return current.left
        } else {
            return current.right
        }
    }
    return null
}
function getMin () {
    let current = this.root
    while (!(current.left === null)) {
        current = current.left
    }
    return current.data
}
function getMax () {
    let current = this.root
    while (!(current.right === null)) {
        current = current.right
    }
    return current.data
}
//  删除节点，要先找到要删除的节点
function remove (data) {
    root = removeNode(this.root, data)
}
function removeNode (node, data) {
    if (node === null) {
        return null
    }
    if (node.data === data) {
        // 没有子节点的节点
        if (node.left == null && node.right == null) {
            return null
        }
        // 没有左子节点的节点
        if (node.left == null) {
            return node.right
        }
        // 没有右子节点的节点
        if (node.right == null) {
            return node.left
        }
        //  如果有俩个子节点，要么查找待删除节点左子树上的最大值，要么查找其右子树上的最小值
        var tempNode = getSmallest(node.right)
        node.data = tempNode.data
        node.right = removeNode(node.right, tempNode.data)
        return node
    } else if (node.data < data) {
        node.left = removeNode(node.left, data)
        return node
    } else {
        node.right = removeNode(node.right, data)
        return node
    }
}
function getSmallest (node) {
    let current = node
    while (!(current.left === null)) {
        current = current.left
    }
    return current.data
}
function update () {
    var grade = this.find(data)
    grade.count++
    return grade
}

二叉树和二叉查找树的基本不是很复杂，但是想要用好二叉树，会很不容易。且行且珍惜。