In [30]: all_trees
Out[30]: frozenset({frozenset({'D', frozenset({'B', frozenset({'A', 'C'})})}),
           frozenset({'D', frozenset({'C', frozenset({'A', 'B'})})}),
           frozenset({'D', frozenset({'A', frozenset({'B', 'C'})})}),
           frozenset({'D', frozenset({'A', 'B', 'C'})})})

In [27]: L=[list(x) for x in all_trees]

In [27]: L
Out[28]:
[['D', frozenset({'B', frozenset({'A', 'C'})})],
 [frozenset({'C', frozenset({'A', 'B'})}), 'D'],
 ['D', frozenset({'A', frozenset({'B', 'C'})})],
 [frozenset({'A', 'B', 'C'}), 'D']]

In [31]: print_set(all_trees)
Out[31]: '((((A,B),C),D),(((A,C),B),D),(((B,C),A),D),((A,B,C),D))'