0


我尝试“线性化”二叉树的每一种可能性，以使其更易于阅读。每种可能性都应添加到以下结构中：

// (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-path”的每个可能性。


两个基本示例：

二元端或树示例 (1)

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

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


二进制结束或树示例 (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', ...
}


非常感谢你的帮助。

4

1 回答 1

0

基于@Freggar 链接，这里是“或”分布的简化实现。它可能不是以最有效的方式完成的，但它给出了我正在寻找的全局概念。

/*
    TreePath = {
        HashSet<TreeNode> path,
        bool IsAdded // set to false even if it's true when an instance is cloned
    }

    Every class (Tree...) define the methods:
        public object Clone()
        public bool Equals(T typedObj)
        public override bool Equals(object obj)
        public override int GetHashCode()
*/

enum TreeBranch
{
    Unknown,
    Left,
    Right
}

class TreeDecomposer {
    public List<TreePath> Possibilities = new List<TreePath>();

    public TreeDecomposer(AbstractTree tree)
    {
        DecomposeTree(null, tree, TreeBranch.Unknown, new TreePath());
        RemoveDuplicatePaths();
    }

    public void DecomposeTree(AbstractTree parentNode, AbstractTree node, TreeBranch branch, TreePath path)
    {
        if (!path.IsAdded)
        {
            Possibilities.Add(path);
            path.IsAdded = true;
        }

        // Recursive browse
        if (node is TreeConnector) {
                TreeConnector treeConnector = (TreeConnector)node;
                if (treeConnector.Connection == "&")
                {
                    DecomposeTree(treeConnector, treeConnector.LeftTree, TreeBranch.Left, path);
                    DecomposeTree(treeConnector, treeConnector.RightTree, TreeBranch.Right, path);
                }
                else if (treeConnector.Connection == "|")
                {
                    // In this case, parentNode is a TreeOperator
                    if (parentNode != null)
                    {
                        // Left distribution
                        TreePath clonedPathLeftDistribution = (TreePath)path.Clone();
                        TreeConnector parentTreeConnectorLeftDistribution = (TreeConnector)parentNode.Clone();

                        // Right distribution
                        TreePath clonedPathRightDistribution = (TreePath)path.Clone();
                        TreeConnector parentTreeConnectorRightDistribution = (TreeConnector)parentNode.Clone();

                        if (branch == TreeBranch.Left)
                        {
                            parentTreeConnectorLeftDistribution.LeftTree = treeConnector.LeftTree;
                            parentTreeConnectorRightDistribution.LeftTree = treeConnector.RightTree;
                        }
                        else if (branch == TreeBranch.Right)
                        {
                            parentTreeConnectorLeftDistribution.RightTree = treeConnector.LeftTree;
                            parentTreeConnectorRightDistribution.RightTree = treeConnector.RightTree;
                        }

                        // Remove obsolete path
                        Possibilities.Remove(path);

                        // Browse recursively distributed tree ; the path must be different (by ref) if the parent operator is 'OR'
                        DecomposeTree(
                            parentTreeConnectorLeftDistribution,
                            parentTreeConnectorLeftDistribution.LeftTree,
                            TreeBranch.Left,
                            parentTreeConnectorLeftDistribution.Connection == "|"
                                ? (TreePath)clonedPathLeftDistribution.Clone()
                                : clonedPathLeftDistribution
                        );
                        DecomposeTree(
                            parentTreeConnectorLeftDistribution,
                            parentTreeConnectorLeftDistribution.RightTree,
                            TreeBranch.Right,
                            clonedPathLeftDistribution
                        );

                        DecomposeTree(
                            parentTreeConnectorRightDistribution,
                            parentTreeConnectorRightDistribution.LeftTree,
                            TreeBranch.Left,
                            parentTreeConnectorLeftDistribution.Connection == "|"
                                ? (TreePath)clonedPathRightDistribution.Clone()
                                : clonedPathRightDistribution
                        );
                        DecomposeTree(
                            parentTreeConnectorRightDistribution,
                            parentTreeConnectorRightDistribution.RightTree,
                            TreeBranch.Right,
                            clonedPathRightDistribution
                        );
                    }
                    // The operator is the root of the tree; we simply divide the path
                    else
                    {
                        TreePath clonedLeftPath = (TreePath)path.Clone();
                        TreePath clonedRightPath = (TreePath)path.Clone();

                        // Remove obsolete path
                        Possibilities.Remove(path);

                        DecomposeTree(treeConnector, treeConnector.LeftTree, TreeBranch.Left, clonedLeftPath);
                        DecomposeTree(treeConnector, treeConnector.RightTree, TreeBranch.Right, clonedRightPath);
                    }
                }
                break;
        }

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

    public void RemoveDuplicatePaths()
    {
        Possibilities = Possibilities.Distinct().ToList();
    }
}


笔记：

在这里，我只想保留独特的可能性；这就是我使用 HashSet 而不是 List 的原因：

  • "a & a & b" => "a & b"

RemoveDuplicatePaths 方法用于删除重复的组合：

  • "a & b" 和 "b & a" 都是相同的可能性（关于真值）
于 2019-08-13T09:30:55.313 回答