如何构建从泛型树到ab树的继承

Question

我正在尝试实现一个 a-b 树，作为从通用树派生的 class。通用树节点如下：

template<typename T>
struct TreeNode
{
    T value;
    std::vector<TreeNode*> children;
    //Some other trivial stuff
};

a-b节点结构如下：

template<typename T>
struct ABTreeNode : TreeNode<T>
{
    std::vector<T> keys;
    //The idea is to omit the T value field of the base node and use that vector for the keys
};

同样在通用树中 class 存在一个根字段

TreeNode *root;

而 a-b 构造函数是

template<Typename T>
ABTree<T>::ABTree(T value)
{
    GenericTree<T>::root = new ABTreeNode;
    root->keys.push_back(value);
}

现在，这种方式，我需要在很多 a-b 树方法中使用向下转换，例如：

template<typename T>
bool ABTree<T>::search(T value)
{
    ABTreeNode *node = GenericTree<T>::root;
    //....
}//Downcast base to derived

据我所知，向下转换是一种不好的做法，表明设计不好。我使用派生结构中定义的变量但将节点声明为基本结构这一事实似乎很容易出错。如果该节点是作为基本节点创建的而不是派生的，会发生什么情况？例如：

//Somewhere:
TreeNode *node = new TreeNode;//Instead of new ABTreeNode
//..
//Somewhere else
node->keys//Shouldn't that be an error?

我的做法对吗？如果不是，我应该如何更好地构建它？

PS: 请保留原始指针。

Answer 1

通过继承共享代码是一种糟糕的设计。更好的方法是使用 Composition - 请参阅 https://en.wikipedia.org/wiki/Composition_over_inheritance

为了在各种树的不同实现之间共享代码，我会将公共字段提取到结构中。

template <class T, class ChildT>
struct TreeNodeCommons
{
  T nodeValue;
  std::vector<ChildT*> children;
  // more common fields
}

然后我会把它附加到不同类型的节点上。

template<typename T>
struct ABTreeNode
{
  TreeNodeCommons<T, ABTreeNode<T>> commons;
  std::vector<T> keys;  
};

然后您可以编写模板化算法，假设 Node 包含名为 commons 的字段，您也可以编写 Node 特定算法。而且没有dynamic_casts.

如何构建从泛型树到ab树的继承

How to structure the inheritance from generic tree to a-b tree

c++

oop

inheritance

tree

hierarchy