如何建立一个与或树？ [英] How to build an and-or tree?

问题描述

我需要一个树状结构，支持与和或ING。例如，对于像 AB正则表达式| C（D | E）我想打开的成树

所以，首先我们有两个或分支...它可以往下走 AB 或 C（D | E） 。如果你低着头 AB 枝，你会得到两个节点， A 的和的 b （或 A 然后按 b ，等等）。然后，如果你走在 C（D | E）枝，你会得到 C 的和 （D | E），那么（D | E）被分为 D 的或的电子。

制作一个树状结构很容易，你就必须像

 类节点{
字符串元素; 
节点[]儿童; 
} 
  

但后来你是怎么知道孩子应该是AND关系或或运算？我猜树的每个级别应该安定和或门

之间交替

这是否有意义？任何人都可以提出一个结构呢？

---

有几个人建议存储经营者的节点，这是很好，但是是不是有办法利用这一事实，即每个级别总是交替或与，或，并...？

优势编辑：不明白为什么人们一直假定这是一个二叉树。的这不是的。我希望微小的代码片段会提示你。 。刚刚的的例子发生的有只有2个分支

---

目前倾向于这样的：

 抽象类节点{} 
 
类的DataNode：节点
 {
字符串数据; 
} 
 
抽象类OpNode：节点
 {
节点[]儿童; 
} 
 
类OrNode：OpNode {} 
类AndNode：OpNode {} 
  

解决方案

想想一个树状结构，每一个节点代表一个布尔表达式，可以被评估为真或假的 - 你的情况正则表达式（匹配或不匹配）。
树结构本身代表AND和OR：
每个路由，从根开始节点，并使用具有没有进一步的孩子，是表达的结合，代表和节点结束。
树

  A 
 / 
 B 
 / 
 ç
  

将是A和b和C。

每当一个节点已经超过1子节点，有一个OR（脱节），分支分成几个途径：

 一个
 / \ 
 BD 
 / 
 C 
  

表示A AND（（b和C）或D）

所以，你甚至都不需要存储的运营商的任何地方。

在你的榜样，你有表达 AB | C（D | E）所以没有共同的根表达来评价;我建议在这种情况下，根简直是真正和树看起来像：

 真
 / \ 
 AC 
 / / \ 
 BDE 
  

有关C＃中的自定义树类看这里树数据结构C＃或搜索或使自己的之一。

I need a tree structure that supports "and" and "or"ing. For example, given a regular expression like ab|c(d|e) I want to turn that into a tree.

So, at first we have two "or" branches... it can either go down ab, or c(d|e). If you head down the ab branch, you get two nodes, a and b (or a followed by b, whatever). Then if you go down the c(d|e) branch, you get c and (d|e), then (d|e) is split into d or e.

Making a tree structure is easy, you just have something like

class Node {
    string element;
    Node[] children;
}

But then how do you know if the children should be "anded" or "ored"? I guess each level of the tree should alternate between "anding" and "oring"

Does that make sense? Can anyone suggest a structure for this?

---

A few people have suggested storing the "operator" on the node, which is fine, but isn't there a way to take advantage of the fact that each level always alternates or,and,or,and,...?

Edit: Not quite sure why people keep assuming this is a binary tree. It's not. I was hoping the tiny code snippet would tip you off. The example just happens to have only 2 branches.

---

Currently leaning towards this:

abstract class Node { }

class DataNode : Node
{
    string data;
}

abstract class OpNode : Node
{
    Node[] children;
}

class OrNode : OpNode { }
class AndNode : OpNode { }

解决方案

Think of a tree structure where every node represents a boolean expression that can be evaluated to be either true or false - in your case a regular expression (match or non-match). The tree structure itself represents AND and OR: Each route, starting at the root node and ending with a node that has no further children, is a conjunction of expressions, representing AND. The tree

    A
   /
  B
 /
C

would represent A AND B AND C.

Whenever a node has more than 1 child node, there is an OR (disjunction), branching into several routes:

    A
   / \
  B   D
 /
C

represents A AND ((B AND C) OR D)

So you do not even need to store the operators anywhere.

In your example you have the expression ab|c(d|e) so there is no common root expression to evaluate; I suggest the root in this case is simply true and the tree would look like:

   true
   / \
  A   C
 /   / \
B   D   E

For a custom tree class in c# look here Tree data structure in C# or search on or make one of your own.

这篇关于如何建立一个与或树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！