二叉搜索树

[Betty985]

binary-search-tree 有效 二叉搜索树定义如下： 节点的左子树只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。

class BST{
    constructor(val,left,right){
       this.val = (val===undefined ? 0 : val)
       this.left = (left===undefined ? null : left)
       this.right = (right===undefined ? null : right)
    }
//     判断其是否是一个有效的二叉搜索树。
    isValidBST(root){
        // 借助辅助函数扩展参数列表
       return this.isValid(root,null,null)
    }
    isValid(root,min,max){
        if(root==null) return true
        else if(root.val<=min.val){
            return false
        }
        else if(root.val>=max.val){
            return false
        }
        return  this.isValid(root.left,null,root)&&this.isValid(root.right,root,null)
    }
    // 在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 
    // 如果节点不存在，则返回 null 。
    searchBST(root,val){
         if(root==null) return null
        while(root){
        if(root.val==val)
        return root
        root=root.val>val?root.left:root.right
    }
    return null
    }
    // 插入操作
    insertIntoBST(root=this,val){
        if(root==null) return new BST(val)
        if(root.val==val) {
            return new Error('val is on the bst')
        }
        else if(root.val>val) root.left=this.insertIntoBST(root.left,val)
        else if(root.val<val) root.right=this.insertIntoBST(root.right,val)
        return root
    }
    // 删除操作  默认用右子树的最小节点替换
    deleteNode(root,val,right=true){
        if(root==null) return null
        if(root.val==val){
            // 要删除的节点是叶子节点或者只有一个节点
            if(root.left==null) return root.right
            if(root.right==null) return root.left
            // 要删除的节点有两个子节点，用左边最大的元素或者右边最小的元素替换
            if(right){
                let node=this.getMin(root.right)
                root.val=node.val
                root.right=deleteNode(root.right,node.val)
            }else{
                let node=this.getMin(root.left)
                root.val=node.val
                root.left=deleteNode(root.left,node.val)
            }

        }else if(root.val<val){
            root.right=deleteNode(root.right,val)
        }
        else if(root.val>val){
            root.right=deleteNode(root.left,val)
        }
        return root
    }
    // 获取最小节点
    getMin(root){
        // 左子树不为空
        while(root.left){
            root=root.left
        }
        return root
    }
    // 获取最大节点
    getMax(root){
        // 右子树不为空
        while(root.right){
            root=root.right
        }
        return root
    }
// 层序遍历
levelOrder(root) {
    let res = []
    if (root == null) return res
    // 利用堆栈保存每层的节点
    let queue = [root]
    while (queue.length != 0) {
        let size = queue.length
        // 该层节点存放在这里
        res.push([]) for (let i = 0; i < size; i++) {
            let node = q.shift() res[res.length - 1].push(node.val) 
          if (node.left) q.push(node.left) 
         if (node.right) q.push(node.right)
        }
    }
    return res
}
}