二叉树的删除为什么一定要返回更新后的子节点?

作者站长头像
站长
· 阅读数 14

二叉树的删除为什么一定要返回更新后的子节点

...          //二叉树的删除
            remove(key) {
                this.removeNode(this.root, key)
            }
            removeNode(node, key) {
                if (node == null) {
                    return null
                }
                if (this.compareFn(key, node.key) === Compare.less) {
                    //本人疑惑的地方//tip2
                    this.removeNode(node.left, key)
                } else if (this.compareFn(key, node.key) === Compare.bigger) {
                    this.removeNode(node.right, key)
                } else {
                    //tip1
                    node = null
                }
            }
        }

        var mytree = new BST()
        mytree.insert(4)
        mytree.insert(5)
        mytree.insert(1)
        mytree.remove(1)

我看到大家都是以下这么写二叉树的删除的,不明白的是我在tip2处将node.left传入removeNode函数之后,按照JavaScript复杂数据类型变量存的是栈中的地址,那么我在tip1处将key为1的这个节点赋值为null,也就是mytree.root.left这个节点赋值为Null之后,为什么它最终没有被赋值为null,而是要采用下面tip3的方式才能实现删除呢

removeNode(node,key){
            if(node==null){
                return null
            }
            if(this.compareFn(key,node.key)===Compare.less){
                //都采用了赋值的方式,把更新后的子节点赋值给父节点要修改的地方 
                //tip3
                node.left = this.removeNode(node.left,key)
                return node
            }else if(this.compareFn(key,node.key)===Compare.bigger){...

1.以下是比较官方的写法

       const Compare = {
           less:-1,
           bigger:1,
           equ:0
       }
       class Node{
           constructor(key){
            this.key = key
            this.left = null
            this.right = null
           }
       }

       class BST {
           constructor(){
               this.root = null
           }

           insert(key){
                if(this.root==null){
                    this.root = new Node(key)
                }else{
                    this.insertNode(this.root,key)
                }
           }

           compareFn(a,b){
               if(a===b){
                   return Compare.equ
               }
               return a<b?Compare.less:Compare.bigger
           }
           insertNode(node,key){
            if(this.compareFn(key,node.key)===Compare.less){
                if(node.left==null){
                    node.left = new Node(key)
                }else{
                    this.insertNode(node.left,key)
                }
            }else{
                if(node.right==null){
                    node.right = new Node(key)
                }else{
                    this.insertNode(node.right,key)
                }
            }
           }


           //中序遍历
           inOrderMap(callback){
             this.inOrderMapNode(this.root,callback)
           }

           inOrderMapNode(node,callback){
             if(node!=null){
                 this.inOrderMapNode(node.left,callback)
                 callback(node.key)
                 this.inOrderMapNode(node.right,callback)
             }
           }
           //先序遍历
           preOrderMap(callback){
             this.preOrderMapNode(this.root,callback)
           }

           preOrderMapNode(node,callback){
             if(node!=null){
                 callback(node.key)
                 this.preOrderMapNode(node.left,callback)
                 this.preOrderMapNode(node.right,callback)
             }
           }

           //后序遍历
           postOrderMap(callback){
             this.postOrderMapNode(this.root,callback)
           }

           postOrderMapNode(node,callback){
             if(node!=null){
                 
                 this.postOrderMapNode(node.left,callback)
                 this.postOrderMapNode(node.right,callback)
                 callback(node.key)
             }
           }

           min(){
               return this.minNode(this.root)
           }

           minNode(node){
             let current = node
             while(current!=null && current.left!=null){
                 current = current.left
             }
             return current
           }

           max(){
               return this.maxNode(this.root)
           }

           maxNode(node){
             let current = node
             while(current!=null && current.right!=null){
                 current = current.right
             }
             return current
           }

           search(key){
            return this.searchNode(this.root,key)
           }

           searchNode(node,key){
                if(node===null){
                    return false
                }
                if(this.compareFn(key,node.key) === Compare.less){
                    return this.searchNode(node.left,key)
                }else if(this.compareFn(key,node.key) === Compare.bigger){
                    return this.searchNode(node.right,key)
                }else{
                    return true
                }
           }

           remove(key){
             this.root = this.removeNode(this.root,key)
           }

           removeNode(node,key){
            if(node==null){
                return null
            }
            if(this.compareFn(key,node.key)===Compare.less){
                node.left = this.removeNode(node.left,key)
                return node
            }else if(this.compareFn(key,node.key)===Compare.bigger){
                node.right = this.removeNode(node.right,key)
                return node
            }else{
                if(node.left==null && node.right==null){
                    node= null
                    return node
                }

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

                //找到最小,
                const target = this.minNode(node.right)   
                node.key = target.key

                node.right = this.removeNode(node.right,target.key)
                return node
            }
           }
       }

       var mytree = new BST()

       mytree.insert(3)
       mytree.insert(2)
       mytree.insert(5)
       mytree.insert(4)
       mytree.insert(6)

2.以下是我不明白的,为什么出错的写法的半成品

        const Compare = {
            less: -1,
            bigger: 1,
            equal: 0
        }

        class Node {
            //这个key就是树节点的值,同时也是这个节点的中值
            constructor(key) {
                this.key = key
                this.left = null
                this.right = null
            }
        }

        class BST {
            constructor() {
                this.root = null
            }

            insert(key) {
                if (this.root == null) {
                    this.root = new Node(key)
                } else {
                    //这种写法是很普遍的,每次操作都单拎出来一个处理函数,这个处理函数必然是要传入根节点从头开始一个个下去找来操作的,insert就是对外开放的接口,而insertNode就是内部操作的函数,实际上也是因为这一部分是我们需要递归处理的函数,所以你必须单开一个操作,又比如二叉树的遍历,删除,查找如果你要选择递归的方法,都是要重新封装一个处理函数去不断的递归他的
                    this.insertNode(this.root, key)
                }
            }

            compareFn(a, b) {
                if (a === b) {
                    return Compare.equal
                }
                return a < b ? Compare.less : Compare.bigger
            }

            insertNode(node, key) {
                if (this.compareFn(key, node.key) === Compare.less) {
                    if (node.left == null) {
                        node.left = new Node(key)
                    } else {
                        this.insertNode(node.left, key)
                    }
                } else {
                    if (node.right == null) {
                        node.right = new Node(key)
                    } else {
                        this.insertNode(node.right, key)
                    }
                }
            }

            //中序遍历
            inOrderMap(callback) {
                this.inOrderMapNode(this.root, callback)
            }
            inOrderMapNode(node, callback) {
                if (node != null) {
                    this.inOrderMapNode(node.left, callback)
                    callback(node.key)
                    this.inOrderMapNode(node.right, callback)
                }
            }

            //先序遍历
            preOrderMap(callback) {
                this.preOrderMapNode(this.root, callback)
            }
            preOrderMapNode(node, callback) {
                if (node != null) {
                    callback(node.key)
                    this.preOrderMapNode(node.left, callback)
                    this.preOrderMapNode(node.right, callback)
                }
            }

            //后序遍历
            postOrderMap(callback) {
                this.postOrderMapNode(this.root, callback)
            }
            postOrderMapNode(node, callback) {
                if (node != null) {
                    this.postOrderMapNode(node.left)
                    this.postOrderMapNode(node.right)
                    callback(node.key)
                }
            }

            //最小的肯定在最最左边,其实这里可以不用封住
            min() {
                return this.minNode(this.root)
            }
            minNode(node) {
                let current = node
                while (current != null && current.left != null) {
                    current = current.left
                }
                return current
            }
            //最大的肯定在最最右边,其实这里可以不用封住
            max() {
                return this.maxNode(this.root)
            }
            maxNode(node) {
                let current = node
                //写这个current!=null并不是多此一举,因为如果根节点为null的话,null.undefined这种不符合规矩.会报错的,无法访问一个null的属性
                while (current != null && current.right != null) {
                    current = current.right
                }
                return current
            }
            //这个查询查的是有没有这个值,而不是返回这个值的节点,如果要返回这个值的节点,可以用current来承载,最后返回current
            search(key) {
                return this.searchNode(this.root, key)
            }
            searchNode(node, key) {
                if (node === null) {
                    return false
                }
                if (this.compareFn(key, node.key) === Compare.less) {
                    return this.searchNode(node.left, key)
                } else if (this.compareFn(key, node.key) === this.compareFn.bigger) {
                    return this.searchNode(node.right, key)
                } else {
                    return true
                }
            }

            //二叉树的删除
            remove(key) {
                this.removeNode(this.root, key)
            }
            removeNode(node, key) {
                if (node == null) {
                    return null
                }
                if (this.compareFn(key, node.key) === Compare.less) {
                    this.removeNode(node.left, key)
                } else if (this.compareFn(key, node.key) === Compare.bigger) {
                    this.removeNode(node.right, key)
                } else {
                    node = null
                }
            }
        }

        var mytree = new BST()
        mytree.insert(4)
        mytree.insert(5)
        mytree.insert(1)
        mytree.remove(1)

3.以下是我在调试的过程中的观察,在插入4,5,1,删除1的最后一步这里,node和要删除的节点的确是指向的同一个节点,为什么赋值为null影响不了呢二叉树的删除为什么一定要返回更新后的子节点?

回复
1个回答
avatar
test
2024-06-23

answer image先看上面这段代码你能理解为什么node没有被赋值为null吗?当你把这个node传给一个函数的时候并且在函数内部对传入的参数做修改的话你想想是不是等同于上面这样;的确引用类型存储的是指针,但是你对变量的赋值修改的是指针的指向,并不会修改另一个变量的指针answer image

回复
likes
适合作为回答的
  • 经过验证的有效解决办法
  • 自己的经验指引,对解决问题有帮助
  • 遵循 Markdown 语法排版,代码语义正确
不该作为回答的
  • 询问内容细节或回复楼层
  • 与题目无关的内容
  • “赞”“顶”“同问”“看手册”“解决了没”等毫无意义的内容