java二叉搜索树

Question

我有一个关于如何从节点（root）中删除子项的问题？既然我不能调用remove，如果我让这个孩子为null，那个孩子的孩子会上升吗？像，我是否将它初始化为空？或者我会指向孩子的孩子吗？

Answer 1

在传统的二叉搜索树，取出一个节点可以取决于有多少孩子有不同的后果节点有：

• 没有孩子的节点可以简单地移除
• 节点与一个孩子可以被删除，节点将被其唯一的孩子取代。无论儿童是左侧还是右侧，这都适用。
• 有两个孩子的节点有一个稍微复杂的规则：你必须找到节点的有序继任或有序前身被删除，其sucessor的或前任的值替换当前节点的值，然后删除后继者或前任者（根据这些规则）。

Answer 2

这功课吗？没有什么不对......我们只是想帮助人们学习而不是告诉他们答案。

如果您只是将子节点设置为空，您将失去有关孩子孩子的任何信息。

Answer 3

一个标准的树类将知道它的子类，通常被卡在一个数组或集合中 - 在二叉树的情况下，你只有两个直接子元素，所以一个固定大小的数组将会工作。因此，他们通常会实施某种“removeMe”方法，让孩子从该列表中移除孩子。

如上所述，如果您要移除的孩子有孩子，这会变得复杂。

Answer 4

蒂姆的回答似乎最好。但是，是的，你会想要做三件事之一，具体取决于你的孩子是什么样的孩子。如果你让一个孩子为空，那么孩子的孩子就不会向上移动，因为你失去了对孩子的引用。相反，您需要确定您移除的孩子的左侧或右侧儿童是否应设置为指向您移除孩子的指针。在将之前的'节点指针（左侧或右侧）设置为要移除的节点的子节点（左侧或右侧）之后，您将不再具有对该节点的引用，所以它们不需要将其设置为null（可以'牛逼访问它了。除非你写某种双向链接BST的，这就是在这种情况下，没有经典的BST）

Answer 5

此代码应帮助您

public Node<T> getParentOf(Node<T> child){ 
    findParentOf(this.root, child); 
    return temp; 
} 

private void findParentOf(Node<T> ROOT, Node<T> child){ 
    if(ROOT.hasLeft()){ 
     findParentOf(ROOT.left, child); 
    } 

    if(ROOT.left == child || root.right == child){ 
     temp = ROOT; 
    } 

    if(ROOT.hasRight()){ 
     findParentOf(ROOT.right, child); 
    } 
} 


private void replaceNode(Node<T> original, Node<T> newNode){ 
    Node<T> tempParent = getParentOf(original); 
    if(original == tempParent.left){ 
     tempParent.left = newNode; 
    }else if(original == tempParent.right){ 
     tempParent.right = newNode; 
    } 
} 

private void traverseChildrenAndAdd(Node<T> newParent, Node<T> oldParent){ 
    newParent.insert(oldParent.data); 
    if(oldParent.hasLeft()){ 
     traverseChildrenAndAdd(newParent,oldParent.left); 
    } 



    if(oldParent.hasRight()){ 
     traverseChildrenAndAdd(newParent,oldParent.right); 
    } 
} 
private void deleteNode(Node<T> ROOT, Node<T> d){ 
    if(d.data.compareTo(ROOT.data) < 0){ 
     deleteNode(ROOT.left, d); 
    }else if(d.data.compareTo(ROOT.data) > 0){ 
     deleteNode(ROOT.right, d); 
    }else if(d == this.root){ 
     if(this.root.hasLeft()){ 
      traverseChildrenAndAdd(root.left, root.right); 
      root = root.left; 
     }else if(root.hasRight()){ 
      root = root.right; 
     }else{ 
      root = null; 
     } 
    }else{ 
     if(ROOT.hasLeft()&&ROOT.hasRight()){ 
      Node<T> successor = getMinNode(ROOT); 
      replaceNode(successor, successor.right); 
     }else if(ROOT.hasLeft() || ROOT.hasRight()){ 
      if(ROOT.hasLeft()){ 
       replaceNode(ROOT, ROOT.left); 
      }else{ 
       replaceNode(ROOT, ROOT.right); 
      } 
     }else{ 
      replaceNode(ROOT, null); 
     } 
    } 
} 

public void remove(T data){ 
    deleteNode(this.root, new Node<T>(data)); 
} 

Answer 6

你可以做这样的事情（伪代码）：

给定树“root”的根节点和要删除的节点或某些数据“x”，请执行以下操作：

if x < root 
     recurse to left child 
if x > root 
     recurse to right child 
else //node found 
     find the min item of the node right child //min item should be left most leaf node node 
     replace the value of the node you want to delete with min nodes value 
     now delete the min node 
return root; 

代码：

delete(Node root, Object x){ 
    if(root == null){ 
     return null; 
    } 

    if(data < root.data){ 
     root = delete(root.left); 
    }else if(root.data < data){ 
     root = delete(root.right); 
    }else{ 
     if(root.left != null && root.right != null){ 
      Object tmp = findMin(root.right); 
      root.data = tmp; 
      root.right = delete(root.right, tmp); 
     }else{ 
      return (root.left != null) ? root.left : root.right;  
     } 
    } 
return root; 

}