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

Question

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

...          //二叉树的删除            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影响不了呢

Answer 1

没有仔细看代码，但是这里的node只是临时变量，把它置为null是没有用的。

比如

function setNull(value) {    value = null;}var foo = new Object()foo.bar = "bar"setNull(foo);// foo 还是原来的值console.log(foo);

Answer 2

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