关于二分搜索树删除最小元素中root = removeMin（root）的问题。

Question

public E removeMin(){
	E ret = minmum();
	//removeMin(root);
	root = removeMin(root);
	return ret;
}

private Node removeMin(Node node){
	
	if(node.left == null){
		node = node.right;
		size --;
		return node;
	}
	
	node.left = removeMin(node.left);
	return node;
}

老师您好，请问一下关于删除二分搜索树最小元素的问题，这里面的删除逻辑我都懂，但是我不明白为什么在removeMin（）函数里面要root = removeMin（root）；我尝试过直接removeMin（root），调试后一般情况下是正常的，但是当树只有两个节点时就会删除不了，列如{5,6}，遍历后还是【5,6】，但是有了root = removeMin（root），就正常输出6了；removeMin（root）传入了root这个成员变量，那在执行完函数后root不是也会直接发生改变吗，为什么还要在将返回的node赋值给root呢？

Answer 1

liuyubobobo 2019-07-11 02:15:00

关键是再删除根节点的时候，发生了什么。

比如你的例子，我们现在的树中，有{5,6}两个节点，5是根节点。现在删除这个根节点，在removeMin中，node = node.right，此时node指向6，然后return。

如果在外面，不用root接住这个6，root根本没有改变。注意，node是传入函数的形参。在函数内部改变node，不会改变对正科二分搜索书产生任何改变。

这其实和我们递归过程，需要：node.left = removeMin(node.left); 用node.left接住返回结果，道理是一样的。

也可以参考这里：https://coding.imooc.com/learn/questiondetail/110970.html

继续加油！：）

• 提问者 慕少2402952 #1

  好的谢谢老师，我的问题出现在与对于传入函数的形参这里的知识的漏洞，现在已经补上了。