c# - C#でバイナリand-orグラフを線形化する方法は?

Question

より読みやすくするために、バイナリおよびツリーのすべての可能性を「線形化」しようとします。次の構造にすべての可能性を追加する必要があります。

// (x1 AND x2) OR (x2 AND x3)
List<List<Node>> possibilities = new List<List<Node>>() {
    { x1, x2 },
    { x2, x3 }
};

ツリー構造からリストベースの可能性を生成するのにいくつかの困難に直面しています。多くの場合正しい答えを返さない単純化されたバージョンまたは私のアルゴリズムは次のとおりです。

class TreeDecomposer {
    public List<TreePath> Possibilities = new List<TreePath>();
    // TreePath = { List<TreeNode> path, bool IsAdded }

    public TreeDecomposer(AbstractTree tree) {
        DecomposeTree(tree, new TreePath());
    }

    public void DecomposeTree(AbstractTree tree, TreePath path)
    {
        // Add the path to the list of possibilities
        if (!path.IsAdded)
        {
            Possibilities.Add(path);
            path.IsAdded = true;
        }

        // Recursive browse
        if (tree is TreeConnector) {
            TreeConnector treeConnector = (TreeConnector)tree;
            if (treeConnector.Connection == "&")
            {
                DecomposeTree(treeConnector.LeftTree, path);
                DecomposeTree(treeConnector.RightTree, path);
            }
            else if (treeConnector.Connection == "|")
            {
                TreePath clonedPath = (TreePath)path.Clone(); // deep clone

                DecomposeTree(treeConnector.LeftTree, path);
                DecomposeTree(treeConnector.RightTree, clonedPath); // somehow 'or' operator multiplies possibilities by two?
            }
        }

        // Leaf
        else if (tree is TreeValue) {
            TreeValue treeValue = (TreeValue)tree;
            path.Add(treeValue);
        }
    }
}

ツリー構造で動作する正しいアルゴリズムを見つけて、ツリーを参照し、「AND パス」のすべての可能性を構築するには、助けが必要です。

2 つの基本的な例:

バイナリ end-or ツリーの例 (1)

式: (a | b) & (c | d)
可能性:

{
    {a, c}, // or {c, a}, the order doesn't matter
    {a, d},
    {b, c},
    {b, d}
}

バイナリ end-or ツリーの例 (2)

式: a & ((b | c) & d)
可能性:

{
    {a, b, d}, // or {d, b, a}, the order doesn't matter
    {a, c, d}
}

ツリー構造:

実装またはツリー構造は次のとおりです。

abstract class AbstractTree {}

class TreeConnector: AbstractTree
{
    public string Connection; // '&' or '|'
    public AbstractTree LeftTree;
    public AbstractTree RightTree;
}

class TreeValue : AbstractTree
{
    public string Data; // 'a', or 'b', ...
}

どうもありがとうございました。