C# 中基于符号数量从符号列表创建树

Question

我试图弄清楚如何从具有不同数量的符号列表创建一棵树。例如，假设我有以下具有指定数量的符号：

符号	Arity
A	2
B	1
C	2
D	0
E	0

我有以下字符串表示形式：

AABCD 已履行

我正在尝试构建以下树：

      A
     / \
    A   B
   / \  |
  C   D D
 / \
E   E

在这种情况下，不需要使用最后三个符号（DED），因为树已经满了。

我已经通过具有特定数量的符号进行了定义，并且每个符号都包含一个可以保存其他符号列表的属性；所有符号均实现

ISymbol<T>

。我还可以生成

AABCDDE...

字符串。

但是我对如何建造这棵树有点迷失了。我试图建造的这种树有名字吗？我无法找到有关不同数量的节点的任何具体信息，也无法以这种特定的方式构建它（即，逐层构建它，直到当前层的所有符号在进入下一层之前都填充了它们的子代）。

如有任何帮助，我们将不胜感激。短暂性脑缺血发作。

Answer 1

因为你的树是一层一层构建的，所以我建议使用节点队列。我认为该算法看起来像这样（未经测试）：

1. 为字符串中的第一个符号创建

   root

   节点。
2. 如果

   root

   的数量为零，则停止（树已完成）。
3. 创建一个

   queue

   节点，最初包含

   root

   。
4. 对于字符串中剩余的每个

   symbol

   ：
   1. 为

      node

      创建

      symbol

      。
   2. 如果

      node

      的元数非零，则将

      node

      排入

      queue

      的后面。
   3. 查看

      current

      前面的

      queue

      节点。
   4. 添加

      node

      作为

      current

      的子级。
   5. 如果

      current

      具有完整的数量：
      1. 从

         current

         的前面出队

         queue

         。
      2. 如果

         queue

         为空，则停止（树已完成）。