在删除方法中 更改代码顺序，打印结果会报错，求解。

Question

正确的代码：

Node successor = maximumNode(node.left);
successor.left = removeMax(node.left);//size ++;
successor.right = node.right;
node.left = node.right = null;//size --
return successor;

=====================

报错的代码：

Node successor = maximumNode(node.left);
successor.right = node.right;
successor.left = removeMax(node.left);//size ++;
node.left = node.right = null;//size --
return successor;

测试用例：

public static void main(String[] args) {
   BST<Integer> bst = new BST<>();
   int[] arr = {50, 28, 58, 22, 29, 54, 60, 52, 56};
   for(int i = 0 ; i < 9 ; i ++){
       bst.add(arr[i]);
   }
   System.out.println(bst);
   bst.remove(50);
   System.out.println(bst);
}

交换了两行代码的顺序，就会报错，求解，谢谢老师。

Answer 1

liuyubobobo 2018-06-09 04:24:11

removeMax(node.left) 中的逻辑是沿着node.left的右孩子一直向右找，直到无法继续向右。

如果你先让successor.right = node.right，successor就是node.left最右的孩子，现在让他的右节点又指向了node.right，这将导致在removeMax(node.left)的过程中，一直向右寻找出错。

如果还想不明白，你给出的数据集足够小。在bst.remove(50);这句话上加断点，然后跟进程序里，看一看程序到底发生了什么？只有自己不断地debug，不断地实际找到自己逻辑上的漏洞，编程能力才能真正提高哦：）

加油！

• 提问者 慕九州3339786 #1

  非常感谢