0

ツリーデータ構造を剪定する次の関数があります。

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 を取得しています。コレクションをコピーしてオリジナルを削除するか、イテレータから削除できることを読みました。この方法が機能するために何をする必要があるかを誰かが理解するのを手伝ってくれますか?

4

2 に答える 2

1

問題は、ノードのコレクションを繰り返し処理していて、場合によっては再帰呼び出し内のコレクションから実際のアイテムを削除していることです。代わりに、再帰呼び出しからブール値フラグを返して、実際のアイテムを削除することを署名し、それを介して削除することもIterator.remove()できます (これを可能にするには、foreach ループを反復子ループに変更する必要があります)。

実際の項目をその唯一のサブノードに置き換えるのは、よりトリッキーです。カスタム クラスを定義して、再帰的なメソッド呼び出しからより多くの情報を返すこともできますが、扱いにくくなります。または、スタックなどを使用して、再帰呼び出しをループに置き換えることを検討することもできます。

于 2011-05-20T21:25:06.860 に答える
0 
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;
}
于 2013-04-10T13:49:32.993 に答える