使用 Kasper Peeters 的 Tree.hh 库避免在节点中添加重复的子节点

Question

我正在尝试获取此处实现的树容器库：http://tree.phi-sci.com/index.html。一直在找树容器，这里推荐的好像是这个或者图库。

在这个特定的示例中，我试图创建一个 N 叉树，并向其添加一些节点。问题是我不想复制这些项目。所以在添加东西之前，我先检查它是否存在。

预期的树应该是这棵：

A
---- A.1
B
---- B.1
---- B.2
C
---- C.1
D
---- D.1
---- D.2
E
---- E.1
---- E.2

数据按字符串对以任意顺序到达。例如，如果我得到 "D"、"D.1"，如果节点 "D" 不存在，我需要创建节点，如果节点 "D.1" 不存在，则在 "D" 中添加节点 "D.1"它不存在，我不关心A、B、C以前是否存在。

到目前为止，这是我的代码

#include "tree.hh"

#include <iostream>
#include <string>
#include <array>

int main(int argc, char *argv[])
{


    //Init the database
    std::string zones[10] = {"A",
                             "A",
                             "B",
                             "C",
                             "B",
                             "D",
                             "D",
                             "E",
                             "E",
                             "E"};

    std::string subZones[10] = {"A.1",
                                "A.1",
                                "B.1",
                                "C.1",
                                "B.2",
                                "D.1",
                                "D.2",
                                "E.1",
                                "E.1",
                                "E.2"};

    //Prepare the strings for the categories
    std::string tempZone = "";
    std::string tempSubZone = "";

    //Prepare the tree
    tree<std::string> bodyTree;
    tree<std::string>::iterator zoneIt, subZoneIt, topIt;
    topIt = bodyTree.begin();

    //Loop the entire database
    for(int i=0; i<10; i++){

        //Grab the data
        tempZone = zones[i];
        tempSubZone = subZones[i];

        //Check if we have that zone already
        zoneIt=find(bodyTree.begin(), bodyTree.end(), tempZone);

        //If we don't have the zone, add it to the tree
        if(zoneIt==bodyTree.end()){

            bodyTree.insert(topIt, tempZone);

            std::cout << "Added new Zone: "<< tempZone << "\n";

        }

        //Now we have the zone for sure, we do the same with the subZone

        //Check if we have that subzone already
        subZoneIt=find(bodyTree.begin(zoneIt), bodyTree.end(zoneIt), tempSubZone);

        //If the subZone doesn't exist, add it to the zone
        if(subZoneIt==bodyTree.end(zoneIt)){

            bodyTree.insert(zoneIt, tempSubZone);

            std::cout << "Added new subZone "<< tempSubZone << " --> to --> " << tempZone << "\n";

        }

    }

    return 0;
}

这是输出：

Added new Zone: A
Added new subZone A.1 --> to --> A
Added new subZone A.1 --> to --> A
Added new Zone: B
Added new subZone B.1 --> to --> B
Added new Zone: C
Added new subZone C.1 --> to --> C
Added new subZone B.2 --> to --> B
Added new Zone: D
Added new subZone D.1 --> to --> D
Added new subZone D.2 --> to --> D
Added new Zone: E
Added new subZone E.1 --> to --> E
Added new subZone E.1 --> to --> E
Added new subZone E.2 --> to --> E

所以如你所见，一级节点没问题，只添加了一次。多次添加二级节点，试图找出它们以前是否存在于该特定节点中。

我的猜测是兄弟姐妹使用迭代器的代码是错误的，所以它应该是这两行之一：

//Check if we have that subzone already
subZoneIt=find(bodyTree.begin(zoneIt), bodyTree.end(zoneIt), tempSubZone);

//If the subZone doesn't exist, add it to the zone
if(subZoneIt==bodyTree.end(zoneIt)){

我想知道是否有人可以告诉我我做错了什么。

Answer 1

有两个问题：

第一次插入区域 zoneIt 将等于 bodyTree.end()。因此，您需要插入另一个对 find(bodyTree.begin(), bodyTree.end(), tempZone); 的调用，使其指向新插入的元素。
insert 将新元素添加为当前区域的兄弟元素。但是您想使用 append_child 来将其添加为当前区域的子区域。

将 these 更改添加到您的代码后，我得到以下输出：

Added new Zone: A
Added new subZone A.1 --> to --> A
Added new Zone: B
Added new subZone B.1 --> to --> B
Added new Zone: C
Added new subZone C.1 --> to --> C
Added new subZone B.2 --> to --> B
Added new Zone: D
Added new subZone D.1 --> to --> D
Added new subZone D.2 --> to --> D
Added new Zone: E
Added new subZone E.1 --> to --> E
Added new subZone E.2 --> to --> E

使用 Kasper Peeters 的 Tree.hh 库避免在节点中添加重复的子节点

Avoid adding a duplicate child in a node, using the Tree.hh library from Kasper Peeters

c++

tree