java - 在二叉树中分布 AND over OR(合取范式)

Question

我正在尝试转换二叉树，例如

OR (Implementation of Operator - a specialisation of TreeNode... see below)
|-A (Implementation of TreeNode... see below)
|-OR
  |-B
  |-AND (Implementation of Operator - a specialisation of TreeNode... see below)
    |-C
    |-OR
      |-D
      |-E

转化为等效的合取范式 (CND) 表示。我相信，因为我只使用逻辑 OR + AND 运算符，所以我必须执行的唯一步骤是 AND 在 OR 上的分布。这将在 CNF 中生成以下树(出于我的目的仍然是二进制):

AND
|-OR
| |-A
| |-OR
|   |-B
|   |-OR
|     |-E
|     |-D
|-OR
  |-A
  |-OR
    |-B
    |-OR
      |-E
      |-C

我在创建算法来执行此操作时遇到问题...到目前为止，我有以下框架，它将自下而上地重新编写树(注意递归调用以重建):

public TreeNode reconstruct(TreeNode treeNode) {
  if(treeNode instanceof Operator) {
    TreeNode left = reconstruct(((Operator)treeNode).getLeft());
    TreeNode right = reconstruct(((Operator)treeNode).getRight());

    return distribute(treeNode, left, right);
  }
  else
    return node;
}

使用类:

 -----------
|  TreeNode | // Interface
 -----------
      ^
      |
 -----------
| Operator  | // Interface
 -----------
| getLeft() |
| getRight()|
| setLeft() |
| setRight()|
 -----------

任何人都可以建议一个可以转换为 CNF 的 distribute 实现吗？

//编辑 1(nif 回答后)

private Node distribute(TreeNode node, TreeNode left, TreeNode right) {
  if (node instanceof Or) {
    if (left instanceof And) {
      // distribute right over left AND
      return 
        new And(
          new Or(((Operator)left).getLeft(), right),
          new Or(((Operator)left).getRight(), right)
        );
    } 
    else if (right instanceof And) {
      // distribute left over right AND
      return 
        new And(
          new Or(((Operator)right).getLeft(), left),
          new Or(((Operator)right).getRight(), left)
        );
    }
  }
  if(node instanceof Operator) {
    ((Operator)node).setLeft(left);
    ((Operator)node).setRight(right);
  }
  // default
  return node;
}

Answer 1

如果 AND 和 OR 是您正在使用的唯一运算符，那么将您的树转换为 CNF 应该不难。您所要做的就是找到 OR(AND(X,Y), Z) 或 OR(Z, AND(X,Y)) 形式的结构并使用分布规律。

private static TreeNode distribute(TreeNode n, TreeNode left, TreeNode right) {
  if (n instanceof Or) {
    if (left instanceof And) {
      // distribute right over left AND
      return new And(new Or(left.getLeft(), right), 
                     new Or(left.getRight(), right));
    } else if (right instanceof And) {
      // distribute left over right AND
      return new And(new Or(right.getLeft(), left), 
                     new Or(right.getRight(), left));
    }
  }

  // no change
  return treeNode;
}

此算法必须应用于树的所有节点，直到树不再更改为止。将算法应用于节点的顺序无关紧要。直观地，算法的重复应用将拉起所有 AND 节点超过 OR 节点，直到树在 CNF 中。

TreeNode root = ....;
while (true) {
  TreeNode transformedRoot = reconstruct(root);
  if (root.equals(transformedRoot)) {
    break;
  }
  root = transformedRoot;
}
// root is now in CNF

注意:请注意，CNF 转换可能会使您的树呈指数增长。显示的实现非常原始，没有使用任何增强功能来减少计算时间。