我想知道如何将remove方法从递归转换为迭代。我的递归方法运行得很好，但我所有的迭代尝试都不是。我哪里出了问题？我该如何解决？
下面是我的递归方法：
public boolean remove(E someElement) {
return remove(root, someElement);
}
private boolean remove(Node<E> node, E dataItem) {
if (node == null) {
return false;
}
int val = dataItem.compareTo(node.data);
if (val < 0)
return remove(node.left, dataItem);
else if (val > 0)
return remove(node.right, dataItem);
else
return false;
}
BST操作在C/C++中比在Java中更容易迭代，因为可以获得指向变量的指针。
在Java中，您需要区别对待元素位于root的情况；在所有其他情况下，您正在考虑的节点要么在其父节点的左侧，要么在其右侧；因此，您可以将C的指针(或引用(替换为父节点和指示当前节点位于父节点哪一侧的布尔值：
public boolean remove(E someElement) {
if (root == null) {
return false;
}
int val = someElement.compareTo(root.data);
if (val < 0) {
return remove(root, false, someElement);
} else if (val > 0) {
return remove(root, true, someElement);
} else {
root = removeNode(root);
return true;
}
}
private boolean remove(Node<E> parent, boolean right, E dataItem) {
Node<E> node = right ? parent.right : parent.left;
if (node == null) {
return false;
}
int val = dataItem.compareTo(node.data);
if (val < 0) {
return remove(node, false, dataItem);
} else if (val > 0) {
return remove(node, true, dataItem);
} else {
node = removeNode(node);
if (right) {
parent.right = node;
} else {
parent.left = node;
}
return true;
}
}
我暂时省略了方法removeNode，现在，我们可以使第二种方法迭代：
private boolean remove(Node<E> parent, boolean right, E dataItem) {
while (true) {
Node<E> node = right ? parent.right : parent.left;
if (node == null) {
return false;
}
int val = dataItem.compareTo(node.data);
if (val < 0) {
right = false;
} else if (val > 0) {
right = true;
} else {
node = removeNode(node);
if (right) {
parent.right = node;
} else {
parent.left = node;
}
return true;
}
parent = node;
}
}
现在方法removeNode必须移除顶部节点，并在移除后返回新的顶部节点。如果left或right是null，它可以只返回另一个节点，否则，我们必须找到一个节点来替换顶部节点，它可以是left子树的最右侧节点，也可以是right子树的左侧模式节点。
private Node<E> removeNode(Node<E> parent) {
if (parent.left == null) {
return parent.right;
} else if (parent.right == null) {
return parent.left;
}
boolean right = random.nextBoolean();
Node<E> node = right ? parent.right : parent.left;
Node<E> last = removeLast(node, !right);
if (last == null) {
if (right) {
node.left = parent.left;
} else {
node.right = parent.right;
}
return node;
} else {
last.left = parent.left;
last.right = parent.right;
return last;
}
}
private Node<E> removeLast(Node<E> parent, boolean right) {
Node<E> node = right ? parent.right : parent.left;
if (node == null) {
return null;
}
while (true) {
Node<E> next = right ? node.right : node.left;
if (next == null) {
break;
}
parent = node;
node = next;
}
if (right) {
parent.right = node.left;
node.left = null;
} else {
parent.left = node.right;
node.right = null;
}
return node;
}
我会给你算法，你可以试着自己编码
您可以使用Stack来遍历树
以下是您的迭代方式：
push要堆叠的树- 循环，直到堆栈不为空
popa节点- 空检查。如果是
null，则是continue push将左右子树放到Stack上
现在在迭代过程中，您只需要检查弹出的节点是否就是您要查找的节点
是吗？检查它是否有孩子。
- 有孩子吗？像往常一样实现递归删除的子级抓取逻辑
- 没有子节点(也称为叶节点(？只需将其分配给
null
Break
否？继续迭代
尽管我觉得Trees本质上是递归的，使用递归只是一个更好的选择，可以促进对该数据结构的一般工作原理的概念理解。
如注释中所述，remove现在什么都不做，可以安全地用return false;替换。
假设在else的情况下，你想做一些合理的事情，比如在中
private boolean remove(Node<E> node, E dataItem) {
if (node == null) {
return false;
}
int val = dataItem.compareTo(node.data);
if (val < 0)
return remove(node.left, dataItem);
else if (val > 0)
return remove(node.right, dataItem);
else
return do_something(node);
}
标准策略是将其转换为尾部递归。将多个递归调用合并为一个，并将其作为函数中的最后一条语句：
private boolean remove(Node<E> node, E dataItem) {
if (node == null) {
return false;
}
int val = dataItem.compareTo(node.data);
if (val == 0) {
return do_something(node);
}
if (val < 0)
node = node.left;
else
node = node.right;
return remove(node);
}
到目前为止，只是重写了一个实现尾部递归形式的
现在，任何尾部递归函数
foo(args) {
if (interesting_condition(args)) {
return do_something_important(args);
}
args = recompute_arguments(args);
return foo(args);
}
可以机械地转换为迭代：
foo(args) {
while (!interesting_condition(args)) {
args = recompute_arguments(args);
}
return do_something_important(args);
}
我希望我回答了你的问题。