二叉树找到最大最小值，删除任意节点，查找节点

逃离我推掉我的手 2022-05-28 07:11 156阅读 0赞

结合上一篇文章，我们继续深入研究二叉树的操作。

#### 获得最大最小值 ####

在二叉树中找到最大最小值，并没什么难得。因为二叉树独特的结构，最左边的叶子节点值最小。最右边的叶子节点值最大。

//获得最小值
    function getMin(node) { 
        var current = node;
        while (!(current.left == null)){
            current = current.left;
        }
        return current;
    }
    
    
    function getMax(node) { 
        var current = node;
        while (!(current.right == null)){
            current = current.right;
        }
        return current;
    }

#### 删除任意节点。 ####

这个问题要区分，删除的节点是否有叶子节点。  
然后采用递归的方式，删除掉任意节点。

//删除某个节点
    function removeNode(node,deleteNode) {
        if(node == null ){
            return null;
        }
        if(node.data == deleteNode){
            if(node.left == null && node.right == null){ //如果是叶子节点
                node.data = null;
                return null;
            }else if(node.right == null){ //如果只有左子节点
                return node.left;
            }else if(node.left === null){
       //如果只有右子节点
                return node.right;
            }else{
                var tempNode = bst.getMin(node.right);
                node.data = tempNode.data;
                //删除右侧最小值
                node.right = removeNode(node.right,tempNode.data);
                return node;
            }
        }else if(node.data < deleteNode){
            node.right = removeNode(node.right,deleteNode);
            return node;//当前节点没有问题，右边节点可能被替换掉
        }else{
            node.left = removeNode(node.left,deleteNode);
            return node;//当前节点没有问题，左边节点可能被替换掉
        }
    }

#### 查找任意节点 ####

find与find2证明了递归和迭代，在某些场景下，其实是可以相互转化的

//查找给定的值，如果找到返回值，如果没找到返回null
    //用递归实现
    function find(node,value) {
        if(node != null){
            console.log(node.data);
            if(node.data == value){
                return node.data;
            }
            return find(node.left,value) || find(node.right,value);
            // return find(node.right,value);
        }
    }
    //查找给定的值，如果找到返回值，如果没找到返回null
    //用迭代实现
    function find2(value) {
        var current = this.root;
        while (current != null){
            console.log(current.data)
            if(current.data == value){
                return current.data;
            }else if(value < current.data){
                current = current.left;
            }else{
                current = current.right;
            }
        }
        return null;
    }