c++ - 具有不同节点类型的二叉树

Question

我正在编写一个用 C++ 编写的有点复杂的数学代码。我正在使用(模板化的)树结构来表示自适应函数。由于某些数学特性，我最终需要从一种类型的节点更改为另一种类型的节点。这需要透明地发生，并且在存储和性能方面的开销最小，因为这些结构用于非常繁重的计算。

详细情况如下:我有一个模板化的抽象基类，定义了一个通用的、双向链接的节点的通用数学和结构属性。除了跟踪其子节点之外，每个节点都需要来自其父节点和顶级 Tree 类的信息。有两个类继承自该类，FunctionNode 和 GenNode。这些类在存储和功能方面非常不同，并且不应该(至少是公共(public)的)彼此的祖先。因此，我想构造一棵这样的树:

     T
     N
    / \
   N    N
       / \
      G   N
     / \
    G   G

其中 T 是一个树，N 是一个普通的 FunctionNode，G 是一个 GenNode。问题是 N - G 转换:N 需要有 G 类型的子代，G 有 N 类型的父代。由于 N 和 G 只是堂兄弟而不是 sibling ，所以我无法将 N* 转换为 G*。 G 知道 N 是一个 BaseNode 就足够了，但是 N 必须以某种方式多态地存储 G，以便在遍历树时自动调用正确的虚函数。任何如何优雅有效地解决这个问题的想法将不胜感激! :) 当然，有人可以破解它，但由于这是一段非常基础的代码，我希望有一个好的解决方案。将来很可能会有很多此代码的派生。

最好的问候，

乔纳斯·朱塞利乌斯

特罗姆瑟大学理论与计算化学中心

Answer 1

可以委派的时候不要使用继承。请查看Strategy 设计模式以获得这方面的指导。

“N - G”转换可以通过 N (N_g) 的子类更好地处理，它是一元运算符(其他 N 是二元的)，并将工作委托(delegate)给关联的 G 对象。 G 子树实际上是一个基于 G 而不是 N 的不相交类族。

   T
   N
  / \
 N    N
     / \
    N_g N
    |
    G
   / \
  G   G

---

“其中一个问题是我事先不知道下一个 N 是 N 还是 N_g。”

“事先？”在什么之前？如果您正在创建 N，然后尝试确定它们是否应该是 N_g，那么您已经遗漏了几件事。

1. 您在此过程中过早地实例化了 N。

2. 您忘记编写一个通过复制 N 来工作的 N_g 构造函数。

3. 您忘记编写一个 replace_N_with_Ng 方法来“克隆”一个 N 来创建一个 N_g，然后用 N_g 替换树中的原始 N。

多态性的要点是你不需要“事先”知道任何东西是什么。您应该等待尽可能长的时间来创建 N 或 N_g，并将生成的 N(或 N 的子类)对象绑定(bind)到树中。

“此外，有时我需要修剪所有 G:s，并生成更多 N:s，然后再生成更多 G:s。”

很好。您遍历树，用 N 个实例替换 N_g 个实例以“修剪”。您遍历树，用 N_g 替换 N 个实例，以生成新的/不同的 G 子树。