我正在制作一棵树(本质上是一个前缀树,但针对数字而非字符串),该树由数字元组的排序列表构建而成((1,1,2),(1,2,5),(2,1,0)等),每个元组与单个标量值(int或double)相关联。由于树只建立一次,然后进行多次迭代/搜索,我计划使用std::vectors来保存每个节点的子节点。要搜索树,我只需要调用std::lower_bound在每个节点的_children向量上执行二进制搜索,该向量将包含每个节点及其相应键的std::pair。但是,底部节点必须包含一个向量,其中包含每个元组中最后一个条目及其相应值的对,因此必须与BranchNode类型不同。代码如下:
然而,这样做真的很丑陋,因为两个类都必须继承自无用的GenNode类,以便每个BranchNode的子节点可以是其他BranchNodes或LeafNodes...有更好的方法吗?
class GenNode
{
};
template<typename key_type,typename value_type>
class BranchNode : GenNode
{
void insert(std::pair< std::vector<key_type> , value_type>);
private:
std::vector< std::pair<key_type,GenNode*> > _children;
};
template<typename key_type,typename value_type>
class LeafNode : GenNode
{
private:
std::vector< std::pair<key_type,value_type> > _children;
};
然而,这样做真的很丑陋,因为两个类都必须继承自无用的GenNode类,以便每个BranchNode的子节点可以是其他BranchNodes或LeafNodes...有更好的方法吗?
Node
在没有子节点的情况下是叶子节点,一旦添加了子节点,它就成为了分支节点。只需要拥有Node
对象即可。 - Peter Wood