Suche Algo um einen Tree auszulesen

DanielusITF

Hallo!

Ich habe einen Tree, bei dem jedes Item als eine Art Ordner fungieren kann. Das heißt, jeder Ordner kann einen oder mehr Unterordner besitzen und jeder Unterordner wiederum weitere Unterordner und so weiter. In jedem Ordner können Items enthalten sein, die dann Informationen enthalten.

Jetzt möchte ich einen Algo entwickeln, mit dem ich alle Items, die keine Children haben, auslesen kann, quasi alle Items mit Informationen. Wenn das Root-Item ausgewählt ist müssen also ALLE Items geladen werden und wenn einer der Unterordner ausgewählt ist müssen alle im Unterordner befindlichen Items geladen werden.

Ich bin bis jetzt so weit, dass immer der zuerst gefundene Ordner/Unterordner betreten wird und die Items des am tiefsten verschachtelten Ordners ausgelesen werden können. Ich brauche allerdings ALLE untergebenen Items.

Kann mir jemand dabei helfen, den richtigen Algo zu finden, der genau das alles kann?

Hier mein Entwurf:

HTREEITEM h = tree.GetSelectedItem();
   int iAmount= tree.GetItemCount();
   CString cszId, cszUnit;
   cszId.Format("%i",iAmount+1);

   if(h)
   {
      int iCount = tree.GetSelectedCount();
      POSITION pos = m_ctTree.GetFirstSelectedItemPosition(); //wegen multiselection
      int iPos = tree.GetNextSelectedItem(pos);

      for (int i=0;i<iCount;i++) //für jedes selektierte Item (multiple selection)
      {
         h = tree.GetItemFromIndex(iPos);

         int iItemAmount = tree.GetChildrenCount(); //anzahl der children

         if(tree.ItemHasChildren(h)) //wenn children vorhanden
         {            
            HTREEITEM htiChild = tree.GetNextItem(h, TVGN_CHILD);            
            for (int i=0; i<iItemAmount; i++)
            {
               while (tree.ItemHasChildren(htiChild)) //durch bis zum untergebensten ordner
               {
                  iItemAmount = tree.GetChildrenCount();
                  htiChild = tree.GetNextItem(htiChild, TVGN_CHILD);
               }

               auslesendesitems(); //das tatsächliche auslesen des items
            }
         }
         else //wenn keine children vorhanden
         {

            int iDropImage;
            tree.GetItemImage(h,iDropImage,iDropImage);

            if (iDropImage!=0) //iDrobImage = 0 bedeutet, dass es ein Ordner ist
            {
               auslesendesitems();
            }
            else AfxMessageBox(_T("Ordner ist leer!"),MB_OK|MB_ICONSTOP);
         }

         iPos = m_ctTree.GetNextSelectedItem(pos);
      }
   }
}

Wie gesagt, damit funktioniert es nicht. Ausserdem habe ich den Code etwas gekürzt und vereinfacht, also kann es sein, dass es manche Methoden in Wirklichkeit nicht gibt.

Ich würde mich sehr freuen, wenn mir jemand "in Worten" erklären kann, wie der Ablauf (der Algo) lauten müsste. Programmieren kann ich das Ganze dann selbst.

Vielen Dank schon mal für Eure Mühe. Ich komme leider absolut nicht weiter (sonst müsste ich auch nicht fragen).

Viele Grüße
Daniel

CStoll

Ich würde da etwas aus Rekursion und Schleife zusammenbauen ( Pseudocode):

void getItems(Ordner root, vector<Item>& items)
{
  for(i=0;i<root.ItemCount();++i)
    if(isOrdner(root.Item(i)))
      getItems(root.Item(i),items);
    else
      items.push_back(root.Item(i));
}

finix

DanielusITF schrieb:

Kann mir jemand dabei helfen, den richtigen Algo zu finden, der genau das alles kann?

Google: "breadth first"

DanielusITF

Vielen Dank für Eure Antwort.

@CStoll
An Rekursion habe ich auch gedacht, aber wo ist in Deinem (Pseudo-)Code denn eine? So in etwa habe ich es ja auch. Aber ich weiß nicht wie ich selbige Prozedur auch für alle Siblings, also die Geschwister laufen lassen kann. Ich glaube ich denke im Moment einfach zu kompliziert.

@finix
das sieht in der Theorie ganz gut aus, aber ich habe ehrlich gesagt keine Ahnung, wie ich hier Items in eine Queue stellen kann, bzw. wie eine Queue implementiert werden müsste.

Viele Grüße
Daniel

PS: Ich programmiere erst seit einem Monat C++, zeigt etwas erbarmen

CStoll

DanielusITF schrieb:

@CStoll
An Rekursion habe ich auch gedacht, aber wo ist in Deinem (Pseudo-)Code denn eine?

Schau mal genau hin - getItems() ruft sich rekursiv selber auf.

Aber ich weiß nicht wie ich selbige Prozedur auch für alle Siblings, also die Geschwister laufen lassen kann. Ich glaube ich denke im Moment einfach zu kompliziert.

Ja, du mußt eine Ebene höher denken - der Vater (Wurzelknoten) ruft die Prozedur für alle seine Kinder auf und die gehen immer tiefer in die Verzeichnisstruktur. Daß die Prozedur auch für deine Geschwister aufgerufen wird, kümmert dich jetzt nicht - da macht wiederum dein Vater.

DanielusITF

habs geschafft. Vielen Dank!

gruß
Daniel