搜索二叉树(BST)可以是一颗空树,若其左子树不为空,则左子树上所有节点均小于或者等于它的根节点的值,若其右子树不为空,则右子树上所有节点均大于或者等于它的根节点的值,左右子树叶分别为搜索二叉树。

搜索二叉树(BST)

定义节点

首先定义节点,传入节点存储数据,以及其左子树长子节点与其右子树长子节点,一个返回实例节点数据的函数。

function Node(data, left, right) {
    this.data = data
    this.right = right
    this.left = left
    this.show = show
}

function show() {
    return this.data
}

定义搜索二叉树

定义搜索二叉树,初始化根节点为null,定义插入节点函数,定义删除节点函数,定义遍历函数(中序,前序,后序),定义查找函数,定义获取最大、最小节点数据函数。

function BST() {
    this.root = null
    this.insert = insert
    this.inOrder = inOrder
    this.preOrder = preOrder
    this.postOrder = postOrder
    this.find = find
    this.getMin = getMin
    this.getMax = getMax
    this.remove = remove
}

向搜索二叉树中插入节点

首先创建一个新节点,将数据保存到该节点;
然后查找BST中是否拥有根节点,如果没有,那就是一颗新树,该节点就是根节点,如果该节点不是根节点,就需要遍历BST,找到适当插入节点的位置。
插入节点的算法:
(1)设根节点为当前节点。
(2)如果待插入节点保存的数据小于当前节点,则设新的当前节点为原节点的左节点;反之执行第四步。
(3)如果当前节点为空,就将新的节点插入这个位置,退出循环;反之,继续执行下次循环。
(4)设新的当前节点为原节点的右节点。
(3)如果当前节点为空,就将新的节点插入这个位置,退出循环;反之,继续执行下次循环。

function insert(data) {
    var node = new Node(data, null, null)
    if (this.root === null) {
        this.root = node
    } else {
        var current = this.root
        var parent = null
        while (true) {
            parent = current
            if (data < current.data) {
                current = current.left
                if (current === null) {
                    parent.left = node
                    break
                }
            } else {
                current = current.right
                if (current === null) {
                    parent.right = node
                    break
                }
            }
        }
    }
}

BST遍历

无论哪种遍历方法,都是采用递归。

中序

总结三个字,就是左根右

function inOrder(node) {
    if (!(node === null)) {
        inOrder(node.left)
        console.log(node.show())
        inOrder(node.right)
    }
}

前序

总结三个字,就是根左右

function preOrder(node) {
    if (!(node === null)) {
        console.log(node.show())
        preOrder(node.left)
        preOrder(node.right)
    }
}

后序

总结三个字,就是左右根

function postOrder(node) {
    if (!(node === null)) {
        postOrder(node.left)
        postOrder(node.right)
        console.log(node.show())
    }
}

查找

BST通常使用的三种类型的查找,查找最小值,查找最大值,以及查找特定值。

查找最大值

沿着BST左子树遍历,直到最后一个叶节点,返回该叶节点的数据。

function getMax() {
    var current = this.root
    if (!(current.left === null)) {
        current = current.left
    }
    return current.data
}

查找最小值

沿着BST右子树遍历,直到最后一个叶节点,返回该叶节点的数据。

function getMin() {
    var current = this.root
    if (!(current.right === null)) {
        current = current.right
    }
    return current.data
}

查找特定值

比较该值与当前节点的数据大小,如果不等,根据大小确定遍历方向,找到该值,返回保存该值得节点,没有找到,则返回null

function find(data) {
    var current = this.root
    while (current !== null) {
        if (current.data === data) {
            return current
        } else if (data < current.data) {
            current = current.left
        } else {
            current = current.right
        }
    }
    return null
}

删除节点

BST删除方法使用删除子节点函数removeNode

function remove(data) {
    root = removeNode(this.root, data)
}

删除节点使用递归的方法,判断当前节点为空,则返回null。如果不为空,继而判断当前节点数据与要删除数据的大小。
如果相等,判断当前节点的左右子节点是否存在,都不存在,直接返回null,仅左节点存在,返回左节点,仅右节点存在,返回右节点,都存在,则沿着右子树查找最小节点,将最小节点值赋给当前要删除节点,再将右子树最小节点删除。
如果不等,比较当前节点数据与要删除节点数据的大小,小于,当前节点的右节点递归调用removeNode函数,传值分别为当前节点右节点,以及要删除数据。大于,当前节点的左节点递归调用removeNode函数,传值分别为当前节点左节点,以及要删除数据。

function removeNode(node, data) {
    if (node === null) {
        return null
    }
    if (data === node.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 = getRightSmallest(node.right)
        node.data = tempNode.data
        node.right = remove(node.right, tempNode.data)
        return node
    } else if (data < node.data) { 
        node.left = removeNode(node.left, data)
        return node
    } else {
        noderight = removeNode(node.right, data)
        return node
    }
}

其中,getRightSmallest为寻找右子树中最小节点函数

getRightSmallest(node) {
    if (node === null) {
        return node
    } else {
        return getRightSmallest(node.left)
    }
}

总结

至此,搜索二叉树的基本功能都用js实现了,最近在笔试中遇到了很多算法和数据结构的问题,发现前端仅仅只会”前端”是不够的,任重而道远。