二叉查找树.md

/**
 * 时间:2019/3/29
 * 公众号: 「一个不甘平凡的码农」
 * 二叉查找树的增、删、改、查
 * 功能:
 * 1)插入数据
 * 2)查找数据
 * 3)删除数据
 * 4)查找最大值
 * 5)查找最小值
 * 6)前、中、后序遍历
 * @author 小鹿
 *
 */

//定义树节点
class Node{
    constructor(data){
        this.data = data;
        this.left = null;
        this.right = null;
    }

    //插入数据
    //步骤:
    // 1、判断是否为空树(是:将数据加入到第一个结点)
    // 2、循环根节点不等于 null
    // 3、判断与根节点的大小
    // 4、判断左/右子树是否为 null
    // 5、递归左子树/递归右子树
    insertValue = (tree,val) =>{
        //封装节点
        let newNode = new Node(val);

        //判断是否为空树
        if(tree === null) {
            tree = newNode;
            return true;
        }else{
            while(tree != null){
                //判断与根节点的大小
                if(newNode.data < tree.data){
                    //判断左子树是否为null
                    if(tree.left == null){
                        tree.left = newNode;
                        return true;
                    }else{
                        tree = tree.left;
                    }
                }else{
                    //val 大于根节点
                    if(tree.right == null){
                        tree.right = newNode;
                        return true;
                    }else{
                        tree = tree.right;
                    }
                }
            }
        }
    }


    //查找数据
    //步骤:
    // 1、判断树是否为 null
    // 2、判断查找数据于根节点大小
    // 3、递归左/右子树
    findData = (tree,val) =>{
        //判断树是否为 null
        if(tree == null){
            return false;
        }

        while(tree !== null){
            //判断查找值与根节点的大小
            if(val == tree.data){
                return tree.data;
            }else if(val < tree.data){
                if(tree.left == null){
                    return false;
                }else{
                    tree = tree.left;
                }
            }else{
                if(tree.right == null){
                    return false;
                }else{
                    tree = tree.right;
                }
            }
        }
    }

    //删除数据
    //步骤:
    // 1、定义两个节点(p用来存放删除节点,pp用来存放删除节点的父节点)
    // 2、遍历树查找要删除的节点(条件:找不到该值/找到了该值)
    // 2、判断是否找到该值
    // 3、判断要删除的树节点子节点个数(无子节点、一个子节点、两个子节点)
    //    1)情况一(节点的两个子节点都不等于null):两个子节点:在右子树先寻找最小值(同时记录最小值的父节点),做数值交换，
    // 然后让删除节点的p指针指向最小值,同时让删除节点的父节点指向删除值的父节点。转化为删除叶子节点问题。
    //    2)情况二(节点的其中一个结点为 null):用 child 存储删除节点的子节点
    //    3)情况三(删除叶子节点):让 child 存储 null
    // 4、对标记好的节点进行删除
    // 5、判断树中只剩下根节点
    // 6、判断父节点下哪个子节点删除了，让父节点直接指向 child
    deleteData = (p,val) =>{
        //定义父节点(记录删除节点的父节点)
        let pp = null;  

        //寻找该删除节点
        while(p !== null && p.data != val){
            //记录删除节点的父节点
            pp = p;
            //判断删除值与根节点大小关系
            if(val > p.data){
                p = p.right;
            }else{
                p = p.left;
            }
        }

        // 如果树为 null 或者找不到该删除节点
        if(p == null){
            return false;
        }

        //情况一:该删除节点有两个子节点
        if(p.left != null && p.right != null ){
            //寻找右子树最小节点(默认右子树最小节点)
            let minP = p.right;
            //记录最小值的父节点
            let minPP = p;
            //判断右子节点是否有左子树
            while(minP.left != null){
                //记录最小节点的父节点
                minPP = minPP;
                //找到最小节点
                minP = minP.left;
            }
            //节点值交换
            p.data = minP.data;
            //最小值节点交换,随之指向删除节点的指针和父节点的指针变换
            p = minP;
            //父节点交换
            pp = minPP;
        }

        //如果为情况一,经上述变换,成为了删除一个叶子节点(情况三)
        //情况二:删除节点是叶子节点或仅有一个节点
        let child = null;
        if(p.left != null){
            child = p.left;
        }else if(p.right != null){
            child = p.right;
        }else{
            //情况三:删除节点为叶子节点
            child = null;
        }

        //对删除节点进行删除操作
        if(pp == null){
            //树的根节点为 null(树中只有一个节点)
            this.tree = child;
        }else if(pp.left == p){
            //该删除节点在父节点的左边的情况
            pp.left = child;
        }else{
            //该删除节点在父节点的右边情况
            pp.right = child;
        }
    }
}

//求树中最大节点
treeMaxNode = (tree)=>{
    // 
    if(tree === null) return false;
    // 
    while(tree.right != null){
        tree = tree.right;
    }
    return tree.data;
}

//求树中最小节点
treeMinNode = (tree)=>{
    // 
    if(tree === null) return false;
    // 
    while(tree.left != null){
        tree = tree.left;
    }
    return tree.data;
}

//遍历二叉查找树
//前序遍历
preorderTraversal = (tree) =>{
    //判断树是否为空
    if(tree == null) return false;
    //根节点
    console.log(tree.data)
    //左子树
    this.preorderTraversal(tree.left)
    //右子树
    this.preorderTraversal(tree.right)
}

//中序遍历
inorderTraversal = (tree) =>{
    //判断树是否为空
    if(tree == null) return false;
    //左子树
    this.inorderTraversal(tree.left);
    //根节点
    console.log(tree.data)
    //右节点
    this.inorderTraversal(tree.right);
}

//后序遍历
postorderTraversal = (tree) =>{
    //判断树是否为空
    if(tree == null) return false;
    //左子树
    this.postorderTraversal(tree.left);
    //右子树
    this.postorderTraversal(tree.right);
    //根节点
    console.log(tree.data)
}

//测试
const tree = new Node(1);
console.log('------------------------------插入数据--------------------------')
tree.insertValue(tree,12)
tree.insertValue(tree,9)
tree.insertValue(tree,24)
tree.insertValue(tree,8)
tree.insertValue(tree,10)
tree.insertValue(tree,13)
tree.insertValue(tree,30)
tree.insertValue(tree,7)
inorderTraversal(tree);
console.log('-----------------------------查找数据--------------------------')
console.log(tree.findData(tree,30))
console.log('-----------------------------删除数据--------------------------')
console.log('--------------------------删除只有一个节点----------------------')
tree.deleteData(tree,8)
inorderTraversal(tree);
console.log('----------------------------删除叶子节点-----------------------')
tree.deleteData(tree,30)
inorderTraversal(tree);
console.log('---------------------------删除有两个节点----------------------')
tree.deleteData(tree,9)
inorderTraversal(tree);
console.log('------------------------------前序遍历-------------------------')
preorderTraversal(tree);
console.log('------------------------------中序遍历-------------------------')
inorderTraversal(tree);
console.log('------------------------------后序遍历-------------------------')
postorderTraversal(tree);
console.log('------------------------------求最大值-------------------------')
console.log(treeMaxNode(tree))
console.log('------------------------------求最小值-------------------------')
console.log(treeMinNode(tree))