我会给您算法,您可以尝试自己编写代码。
您可以使用Stack
遍历树。
因此,这就是您的迭代方式:
-
push
要堆叠的树
- 循环直到堆栈不为空
-
pop
一个节点
- 空检查。如果为
null
,则为continue
。
-
push
到Stack
上的左右子树
现在,在迭代过程中,您只需要检查弹出的节点是否是您要查找的节点即可。
是?检查是否有孩子。
- 有孩子吗?照常实现子级抢夺逻辑以进行递归删除
- 没有孩子(也称为叶节点)吗?只需将其分配给
null
休息
不?继续迭代
尽管我觉得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);
}
我希望我回答了你的问题。
,
由于可以获取指向变量的指针,因此在C / C ++中进行BST操作要比在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,dataItem);
} else if (val > 0) {
return remove(node,dataItem);
} else {
node = removeNode(node);
if (right) {
parent.right = node;
} else {
parent.left = node;
}
return true;
}
}
我暂时省略了方法removeNode
,现在,我们可以使第二种方法迭代:
private boolean remove(Node<E> parent,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
,则它只能返回另一个节点,否则,我们必须找到一个节点来替换topnode,并且它可以是该节点中最右边的节点。 left
子树,或right
子树的leftmode节点。
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;
}
本文链接:https://www.f2er.com/3100199.html