二叉树与不同的节点类型

Question

我正在研究一种用C++编写的有点复杂的数学代码.我正在使用(模板化)树结构进行自适应函数表示.由于某些数学属性,我最终会遇到需要从一种节点更改为另一种节点的情况.这需要在存储和性能方面透明地并且以最小的开销发生,因为这些结构用于非常繁重的计算.

具体情况如下:我有一个模板化的抽象基类,它定义了一般的双链节点的一般数学和结构属性.每个节点除了跟踪它的子节点之外,还需要来自它的父节点和顶级Tree类的信息.两个类继承自此类,FunctionNode和GenNode.这些类在存储和功能方面非常不同,并且不应该(至少是公开的)彼此的祖先.因此,我想构建一个这样的树:

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

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

最好的祝福,

Jonas Juselius

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

Answer 1

委托时不要使用继承.查看策略设计模式以获得相关指导.

通过具有N(N_g)的子类可以更好地处理"N-G"转换,N(N_g)是一元运算符(其他N是二进制的)并且将工作委托给关联的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_g构造函数,它通过复制N来工作.

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

多态性的要点是你不需要事先知道什么是什么.您应该尽可能长时间地创建N或N_g,并将生成的N(或N的子类)对象绑定到树中.

"此外,有时候我需要修剪所有的G:s,并产生更多的N:s,然后才能产生更多的G:s."

精细.你走在树上,用N个实例替换N_g实例为"prune".您走过树用N_g替换N个实例以生成新的/不同的G子树.