Блог

У меня есть следующая функция, которая обрезает древовидную структуру данных :

 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, и я прочитал, что вы можете скопировать коллекцию и удалить оригинал — или удалить из итератора. Может кто-нибудь помочь мне понять, что мне нужно сделать, чтобы этот метод заработал?

Проблема в том, что вы перебираете коллекцию узлов и в некоторых случаях удаляете фактический элемент из коллекции внутри рекурсивного вызова. Вместо этого вы могли бы вернуть логический флаг из рекурсивного вызова, чтобы указать, что фактический элемент должен быть удален, затем удалить его с помощью Iterator.remove() (вам нужно изменить цикл foreach на цикл итератора, чтобы сделать это возможным).

Заменить фактический элемент его единственным подузлом сложнее — вы могли бы определить пользовательский класс для возврата дополнительной информации из вызова рекурсивного метода, но это начинает становиться неудобным. Или вы можете рассмотреть возможность замены рекурсивного вызова циклом, используя, например, стек.

 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;
}