刪除節點正確

Question

我有以下功能修剪樹數據結構：

public static void pruneTree(final ConditionTreeNode treeNode) { 

    final List<ConditionTreeNode> subTrees = treeNode.getSubTrees(); 

    for (ConditionTreeNode current : subTrees) { 
     pruneTree(current); 
    } 

    if(subTrees.isEmpty()) { 
     final ConditionTreeNode parent = treeNode.getParent(); 
     parent.removeConditionTreeNode(treeNode); 
    } 

    if (treeNode.isLeaf()) { 
     //this is the base case 
     if (treeNode.isPrunable()) { 
      final ConditionTreeNode parent = treeNode.getParent(); 
      parent.removeConditionTreeNode(treeNode); 
     } 
     return; 
    } 

} 

，我想知道什麼是最好的方式修剪，這是。我目前正在獲得ConcurrentModificationExceptions，並且我讀過您可以複製該集合並刪除原始內容 - 或者從迭代器中刪除。有人可以幫助我理解爲了使這種方法起作用而需要做什麼嗎？

Answer 1

問題是，您正在迭代節點的集合，並且在某些情況下將遞歸調用中的實際項目從集合中刪除。你可以從遞歸調用中返回一個布爾標誌來標記實際的項目將被刪除，然後通過Iterator.remove()（你需要將foreach循環改爲迭代器循環來使其成爲可能）將其刪除。

用其唯一的子節點替換實際的項目會更棘手 - 您可以定義一個自定義類以從遞歸方法調用中返回更多信息，但它開始變得尷尬。或者你可以考慮使用例如循環來替換遞歸調用。一個堆棧。

Answer 2

public boolean remove(int target) 
{ 
    if(find(target)) //TreeNode containing target found in Tree 
    { 
     if(target == root.getInfo()) //target is in root TreeNode 
     { 
      if(root.isLeaf()) 
      root = null; 
     else if(root.getRight() == null) 
      root = root.getLeft(); 
     else if(root.getLeft() == null) 
      root = root.getRight(); 
     else 
     { 
      root.getRight().getLeftMostNode().setLeft(root.getLeft()); 
      root = root.getRight(); 
     } 
     } 
     else //TreeNode containing target is further down in Tree 
     { 
      if(cursor.isLeaf()) //TreeNode containing target has no children 
     { 
      if(target <= precursor.getInfo()) 
       precursor.removeLeftMost(); 
      else 
     precursor.removeRightMost(); 
      } 
     else if(cursor.getRight() == null) //TreeNode containing target   
     {     //has no right subtree 
      if(target <= precursor.getInfo()) 
       precursor.setLeft(cursor.getLeft()); 
      else 
     precursor.setRight(cursor.getLeft()); 
     } 
     else if(cursor.getLeft() == null) //TreeNode containing target 
     {     //has no left subtree 
      if(target <= precursor.getInfo()) 
        precursor.setLeft(cursor.getRight()); 
      else 
     precursor.setRight(cursor.getRight()); 
     } 
     else //TreeNode containing target has two subtrees 
     { 
      cursor.getRight().getLeftMostNode().setLeft(cursor.getLeft()); 
      if(target <= precursor.getInfo()) 
        precursor.setLeft(cursor.getRight()); 
      else 
     precursor.setRight(cursor.getRight()); 
      } 
     } 

     cursor = root; 
     return true; 
    } 
    else //TreeNode containing target not found in Tree   
     return false; 
}