好吧，我已经研究了好几天了，每次我想我已经把它写下来了，我就开始写代码，我已经到了一个地步，我就是不知道该怎么做。
该树不是递归的，所以我可以真正跟踪所有内容，直到我开始尝试修改它，使其使用惰性删除而不是真正的删除。（现在它清空了它删除的节点）
我设法弄清楚了：
- 我在节点类中添加了一个标志，将它们设置为已删除
- 我已经实现了一个有效的搜索方法，它甚至可以注册我的节点是否被删除（懒惰地）
- 我知道树类的其余部分应该将标记为已删除的节点处理为不存在
我不知道的是：
- 我看了很多资源，有人说你只需要设置节点的deleted标志设置为true。这是否意味着我不必担心他们的标志设置后的链接吗
- 这样做是否很肤浅？与中一样，如果将标志设置为删除，即使方法确实找到了什么，也不要让方法报告找到了什么
- 我应该用什么方法更改为使用延迟删除？只使用delete（）方法
- 如果我只更改删除方法，其他方法是如何处理的
- 搜索方法看起来不错吗
这是其余的代码，这样你就可以看到我在使用什么了。我真的很沮丧，因为我真的知道如何完全删除节点，比这个愚蠢的懒惰删除实现要好得多。这是他们在书中教的！lol
请帮忙…：（
搜索方法
下面是我的搜索方法：
public String search(E data){
Node<E> current = root;
String result = "";
while(current != null){
if(data.compareTo(current.e) < 0){
current = current.left;
}
else if (data.compareTo(current.e) > 0){
current = current.right;
}
else{
if (current.isDeleted == false){
return result += "Found node with matching data that is not deleted!";
}
else{
return result += "Found deleted data, not usable, continuing searchn";
}
}
}
return result += "Did not find non-deleted matching node!";
}
树类
树代码（真正的删除方法在最后被注释掉了，所以我可以用延迟删除来代替它）：
将mybinary打包为三个示例；
公共类MyBinaryTree>{
private Node<E> root = null;
public class Node<E> {
public boolean isDeleted = false;
public E e = null;
public Node<E> left = null;
public Node<E> right = null;
}
public boolean insert(E e) {
// if empty tree, insert a new node as the root node
// and assign the elementy to it
if (root == null) {
root = new Node();
root.e = e;
return true;
}
// otherwise, binary search until a null child pointer
// is found
Node<E> parent = null;
Node<E> child = root;
while (child != null) {
if (e.compareTo(child.e) < 0) {
parent = child;
child = child.left;
} else if (e.compareTo(child.e) > 0) {
parent = child;
child = child.right;
} else {
if(child.isDeleted){
child.isDeleted = false;
return true;
}
return false;
}
}
// if e < parent.e create a new node, link it to
// the binary tree and assign the element to it
if (e.compareTo(parent.e) < 0) {
parent.left = new Node();
parent.left.e = e;
} else {
parent.right = new Node();
parent.right.e = e;
}
return true;
}
public void inorder() {
System.out.print("inorder: ");
inorder(root);
System.out.println();
}
private void inorder(Node<E> current) {
if (current != null) {
inorder(current.left);
System.out.printf("%3s", current.e);
inorder(current.right);
}
}
public void preorder() {
System.out.print("preorder: ");
preorder(root);
System.out.println();
}
private void preorder(Node<E> current) {
if (current != null) {
System.out.printf("%3s", current.e);
preorder(current.left);
preorder(current.right);
}
}
public void postorder() {
System.out.print("postorder: ");
postorder(root);
System.out.println();
}
private void postorder(Node<E> current) {
if (current != null) {
postorder(current.left);
postorder(current.right);
System.out.printf("%3s", current.e);
}
}
public String search(E data){
Node<E> current = root;
String result = "";
while(current != null){
if(data.compareTo(current.e) < 0){
current = current.left;
}
else if (data.compareTo(current.e) > 0){
current = current.right;
}
else{
if (current.isDeleted == false){
return result += "Found node with matching data that is not deleted!";
}
else{
return result += "Found deleted data, not usable, continuing searchn";
}
}
}
return result += "Did not find non-deleted matching node!";
}
public boolean delete(E e) {
}
// an iterator allows elements to be modified, but can mess with
// the order if element not written with immutable key; it is better
// to use delete to remove and delete/insert to remove or replace a
// node
public java.util.Iterator<E> iterator() {
return new PreorderIterator();
}
private class PreorderIterator implements java.util.Iterator<E> {
private java.util.LinkedList<E> ll = new java.util.LinkedList();
private java.util.Iterator<E> pit= null;
// create a LinkedList object that uses a linked list of nodes that
// contain references to the elements of the nodes of the binary tree
// in preorder
public PreorderIterator() {
buildListInPreorder(root);
pit = ll.iterator();
}
private void buildListInPreorder(Node<E> current) {
if (current != null) {
ll.add(current.e);
buildListInPreorder(current.left);
buildListInPreorder(current.right);
}
}
// check to see if their is another node in the LinkedList
@Override
public boolean hasNext() {
return pit.hasNext();
}
// reference the next node in the LinkedList and return a
// reference to the element in the node of the binary tree
@Override
public E next() {
return pit.next();
}
@Override
public void remove() {
throw new UnsupportedOperationException("NO!");
}
}
}
// binary search until found or not in list
// boolean found = false;
// Node<E> parent = null;
// Node<E> child = root;
//
// while (child != null) {
// if (e.compareTo(child.e) < 0) {
// parent = child;
// child = child.left;
// } else if (e.compareTo(child.e) > 0) {
// parent = child;
// child = child.right;
// } else {
// found = true;
// break;
// }
// }
//
//
// if (found) {
// // if root only is the only node, set root to null
// if (child == root && root.left == null && root.right == null)
// root = null;
// // if leaf, remove
// else if (child.left == null && child.right == null) {
// if (parent.left == child)
// parent.left = null;
// else
// parent.right = null;
// } else
// // if the found node is not a leaf
// // and the found node only has a right child,
// // connect the parent of the found node (the one
// // to be deleted) to the right child of the
// // found node
// if (child.left == null) {
// if (parent.left == child)
// parent.left = child.right;
// else
// parent.right = child.right;
// } else {
// // if the found node has a left child,
// // the node in the left subtree with the largest element
// // (i. e. the right most node in the left subtree)
// // takes the place of the node to be deleted
// Node<E> parentLargest = child;
// Node<E> largest = child.left;
// while (largest.right != null) {
// parentLargest = largest;
// largest = largest.right;
// }
//
// // replace the lement in the found node with the element in
// // the right most node of the left subtree
// child.e = largest.e;
//
// // if the parent of the node of the largest element in the
// // left subtree is the found node, set the left pointer of the
// // found node to point to left child of its left child
// if (parentLargest == child)
// child.left = largest.left;
// else
// // otherwise, set the right child pointer of the parent of
// // largest element in the left subtreeto point to the left
// // subtree of the node of the largest element in the left
// // subtree
// parentLargest.right = largest.left;
// }
//
// } // end if found
//
// return found;
改变的是，您的树只根据实际使用的空间而增长，而从不收缩。如果您选择列表作为实现树的数据结构，而不是通常的构造Node E {V value; E right; E; left}，那么这将非常有用。我稍后再谈。
我看了很多资源，有人说你只需要设置节点的deleted标志设置为true。这是否意味着我不必担心他们的标志设置后的链接吗？
是的，如果你所说的链接是指node.left，node.right。Delete只是简单地标记为已删除，仅此而已。它不会改变任何其他内容，也不应该改变，因为即使x或y标记为删除，x.CompareTo(y)也必须仍然工作
这样做是否很肤浅？就像在一样，只是不要如果将标志设置为删除，即使方法确实找到了什么？
根据这个方法的定义，"something"是指没有删除标志的节点。对于树的用户来说，任何带有deleted标志的内容都是"nothing"。
我应该更改什么方法来使用延迟删除？只有delete（）方法
当然不是。您自己已经更改了搜索方法。让我们乘坐isEmpty()。您应该保留一个已删除节点的计数器和一个总节点。如果它们相等，则树为空。否则树就不是了。
你的算法有个小错误。当您插入并发现您降落在已删除的节点上时，您只需取消标记该节点。您还必须设置节点的值。毕竟，compareTo并不能保证所有字段都严格相等，只是保证对象是等价的。
if(child.isDeleted){
child.isDeleted = false;
child.e = e; <---- missing
return true;
}
可能还有其他人。
旁注：
如前所述，此方法有用的一个实例是由列表（比如数组列表）支持的树。利用该方法，位于位置i的元素的子元素位于位置2*i+1和2*i+2。通常，当删除带有子节点的节点p时，会将该节点替换为右子树的最左边节点q（或左子树中的最右边节点）。在这里，您可以将p标记为已删除，并交换已删除节点和最左边节点的值您的数组在内存中保持完整