删除不理解

Question

这里有左子树为空 右子树为空 那么左子树不为空且要删除的节点不是最小点而是在中间

Answer 1

liuyubobobo 2018-09-12 09:39:34

抱歉，我没有特别理解你的问题。。。

在我们的删除逻辑中：https://github.com/liuyubobobo/Play-with-Data-Structures/blob/master/06-Binary-Search-Tree/12-Remove-Elements-in-BST/src/BST.java 

首先要注意，我们在递归的过程中，真正进入250行的if才会进行删除。待删除节点一定是当前递归函数中的node节点，即当前遍历的子树的根节点。

否则会在242-249行继续寻找待删除节点究竟在哪里。

当然有可能找不到，即在239-240行进行处理（返回空）。

如果当前已经找到了待删除节点，即为node，则：

252-258行处理的是待删除的节点的左子树为空的情况，处理完就会返回；

260-266行处理的是待删除的节点的右子树为空的情况，处理完就会返回；

268-278行处理的是待删除的节点的左右子树均不为空的情况，处理完就会返回；

以上三种情况已经穷尽了待删除节点node的所有可能：）

• HyperionAngel #1

  老师好，删除结点时左右子树均为空的情况下维护了两次size变量，但实际只删除了一个结点。这点不太清楚，望解惑

• liuyubobobo 回复 HyperionAngel #2

  只删除了一次。在左右子树均为空的时候，在252-258行判断左子树为空，进入相应的逻辑，之后就会return，不会进入260-266行。自己创建一个简单的测试用例跟踪试试看？两个节点的树，删除一下叶子节点就能看出来：）