Vermeiden Sie ein Duplikat Kind in einem Knoten hinzufügen, die Tree.hh Bibliothek von Kasper Peeters mit

Question

Ich versuche, einen der den Baum Container-Bibliothek zu erhalten, die hier umgesetzt wird: http://tree.phi-sci.com/index.html. Ich habe nach einem Baumbehälter gesucht und die Empfehlung hier scheint diese eine oder die Diagrammbibliothek zu sein.

In diesem speziellen Beispiel, ich versuche, einen N-ary Baum zu machen und einige Knoten, um es hinzuzufügen. Das Problem ist, dass ich die Elemente nicht duplizieren möchte. Bevor ich etwas hinzufüge, prüfe ich zuerst, ob es existiert.

Die beabsichtigte Baum sollte dieses sein:

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

Die Daten gelangen in einer beliebigen Reihenfolge durch Paare von Saiten. Zum Beispiel, wenn ich „D“, „D.1“ bekommen, muss ich den Knoten „D“ erstellen, wenn es nicht vorhanden ist, fügen Sie den Knoten „D.1“ innen „D“, wenn es nicht existiert, und es ist mir egal, ob A, B oder C vorher existieren oder nicht.

Dies ist mein Code so weit

#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; 
} 

Und dies ist die Ausgabe:

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 

So wie Sie sehen können, die erste Ebene Knoten sind in Ordnung, und nur einmal zugegeben. Die Knoten der zweiten Ebene werden mehrmals hinzugefügt, um zu verachten, ob sie vorher in diesem bestimmten Knoten existieren.

Meine Vermutung ist, dass der Code, den Iterator für die Geschwister verwendet falsch ist, so dass es einer dieser beiden Linien sein sollte:

//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)){ 

Ich frage mich, ob jemand kann mir sagen, was mache ich falsch.

Answer 1

Es gibt zwei Probleme:

1. das erste Mal, wenn Sie eine Zone einfügen zoneIt wird bodyTree.end() gleich sein. Sie müssen also einen weiteren Aufruf an find(bodyTree.begin(), bodyTree.end(), tempZone); einfügen, damit es auf das neu eingefügte Element zeigt.

2. insert fügt das neue Element als Geschwister der aktuellen Zone hinzu. Aber Sie möchten stattdessen append_child verwenden, um es als Kind der aktuellen Zone hinzuzufügen.

Mit these Änderungen hinzugefügt, um Ihren Code, den ich folgende Ausgabe:

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