删除二分搜索树的最大/小值的非递归实现
来源：6-11 删除二分搜索树的最大元素和最小元素
liujie151376
2019-04-17
以下是我的删除最大/小值的非递归实现,但是测试的时候发现当只有一个根节点时, 期望得到删除后root = null, 实际root并没有被删除掉.请问是哪里出现了问题呢?
public E removeMinNonRecusive() {
if (root == null) {
throw new IllegalArgumentException("can not remove from an empty tree!");
}
Node cur = root;
Node parent = root;
while (cur.left != null) {
parent = cur;
cur = cur.left;
}
Node right = cur.right;
parent.left = right;
cur.right = null;
size--;
return cur.data;
}
写回答
2回答
-
和链表一样。
回忆一下，我们链表删除是怎么做的？
如果只有一个头结点，直接删除；否则，找到待删除节点的前一个节点，才能正确删除我们想删除的那个节点。
为什么也要对头结点单独判断？因为头结点没有前一个节点。所以，我们统一逻辑的方式，是使用一个虚拟头结点，本质上，就是给头节点也做了一个“头结点的前一个节点”，这样，删除头结点的逻辑，和删除任何一个节点的逻辑，就都统一了：）
你的代码同理，只不过是在树上而已。要删除最小节点，我们要找到最小节点的父亲节点。但是整棵树只有一个根节点，这个根节点没有父亲节点啊！所以，对这种情况，要单独处理。
只有一个节点的树，这个测试用例足够小。使用单步跟踪的方式，一步一步去看，看看你的代码到底发生了什么？这种情况，这个根节点为什么没有删除？这可是进步的根源哦。
加油！：）
212019-04-17 -
liujie151376
提问者
2019-04-17
//附上最终的删除二分搜索树最小节点的非递归实现。 public E removeMinNonRecursive() { if (root == null) { throw new IllegalArgumentException("can not remove from an empty tree!"); } // 说明 root 就是要被删除的节点 if (root.left == null){ E data = root.data; root = root.right; size--; return data; } Node cur = root; Node parent = root; while (cur.left != null) { parent = cur; cur = cur.left; } Node right = cur.right; parent.left = right; cur.right = null; size--; return cur.data; }10
相似问题