Array in einen Baum umwandeln



  • Ich versteh die Anordnung der Zahlen im Array nicht. Wenn Du dort auch keine Klammerung bei der infix-Ausgabe einbaust, kannst Du das Array nicht wieder eindeutig in einen Baum konvertieren. Mit Präfix- oder Postfix-Sortierung wird das Aufbaen des Baumes aber ganz einfach (kannst relativ leicht eine rekursive Funktion schreiben).

    Beide der folgenden Bäume haben die gleiche Infix-Ausgabe (ohne Klammerung)

    AND      OR
      / \      /\
     OR  1    0  AND
     /\          / \
    0  1        1   1
    
    infix:  0 OR 1 AND 1  (beide)
    präfix: AND OR 0 1 1  (erster Baum)
    präfix: OR 0 AND 1 1  (zweiter Baum)
    

    Gruß,
    SP



  • AHA,
    danke für den Hinweis. Also sollte ich schon mal den Baum anders als Array speichern. Dann ändere ich das gleich mal.



  • Also ich hab meinen Baum anders gespeichert:

    Knotenummer, Funktionalität ( Blatt oder logische Verknüpfung ), Liste alle Kinder-Knotennummern

    Und das für alle Knoten im Baum. Wobei ich den Kram aber in einer Datei speichere.



  • so, also habe das jetzt so wie beschrieben in prefix als array gespeichert. aber wie komme ich denn nun zurück???



  • Siggi198181 schrieb:

    so, also habe das jetzt so wie beschrieben in prefix als array gespeichert. aber wie komme ich denn nun zurück???

    Geht das nicht fast genauso?
    Wie sieht denn Dein Pseudoalgorithmus zum Abspeichern aus?



  • also mein code sieht so aus:

    //Methode um einen Baum PREFIX als Array zu speichern
    //NOT = -3
    //AND = -2
    //OR = -1
    int fillArrayFromTree(int intArray[], node* startNode, int index){
    
    	int rc = index;
    
    	if(startNode->isLeaf()){
    		if(startNode->getNotOP()){
    			intArray[rc] = -3;
    			rc++;
    		}
    		intArray[rc] = startNode->getIndex();
    		rc++;
    	}else if(startNode->getOP() == 0){
    		intArray[rc] = -1;
    		rc++;
    	}else if(startNode->getOP() == 1){
    		intArray[rc] = -2;
    		rc++;
    	}
    
    	if (startNode->getLeft() != NULL) {
    		rc = fillArrayFromTree(intArray, startNode->getLeft(), rc);
    	}
    
    	if (startNode->getRight() != NULL) {
    		return fillArrayFromTree(intArray, startNode->getRight(), rc);
    	} else {
    	return rc;
    	}
    }
    


  • das problem ist ja nun die richtigen beziehungen zu finden



  • Ich hätte der Einfachheit und Sicherheit wegen wahrscheinlich einen std::vector<int> per Referenz genommen und die Zahlen per push_back angehängt. Denn so läufst Du ja Gefahr, über das Ende des Arrays hinaus zuschreiben.

    Das Aufbauen des Baums geht jetzt aber fast genauso. Pseudo-Code:

    node* aufbauen(int const*& start, int const* const ende)
    {
      if (start==end) return 0;
      int elem = *start;
      ++start;
      if (0<=elem && elem<=1) return Zeiger von neuem Blattknoten;
      if (elem==-3) {
        assert(start != end);
        elem = *start;
        ++start;
        return Zeiger auf neuen Not-Knoten mit "elem" als Wert;
      }
      node* kind1 = aufbauen(start,ende);
      node* kind2 = aufbauen(start,ende);
      return Zeiger auf neuen Bin-Op-Knoten zurückgeben,
             der kind1 und kind2 als Kinder hat;
    }
    


  • aber hier wird doch dann links und rechts der gleiche knoten angehängt oder verstehe ich das falsch?



  • Neee, dafür wird start per Referenz übergeben. Innerhalb der Funktion wird start ja verändert.



  • OK,

    erstmal sorry für die dummen Fragen und schon mal vielen Dank für die Antworten, aber leider ich versteh es noch immer nicht ganz.

    Habe da leider doch noch ein paar Fragen, aber prinzipiell funktioniert es auch schon fast. Bei mir funktioniert das mit dem Zeiger verändern noch nicht ganz.

    Was bedeuten denn die beiden Übergabeparameter im Funktionsaufruf? Sind das Zeiger auf die Arrayfelder??
    Bzw. wie greifst du denn hier überhaupt auf ein einzelnes arrayfeld zu?
    und was beudeutet genau: return Zeiger auf neuen Not-Knoten mit "elem" als Wert;
    Bedeutet das array[elem] ?



  • Siggi198181 schrieb:

    Was bedeuten denn die beiden Übergabeparameter im Funktionsaufruf? Sind das Zeiger auf die Arrayfelder??

    Ja, das war so gedacht. start zeigt auf das erste Element im Array und ende zeigt hinter das letzte Element.

    start           ende
      |               |
      v               v             AND
    +---+---+---+---+               / \
    |-2 |-3 | 1 | 0 |      --->   N1   1
    +---+---+---+---+
    

    Das Übergeben einer Sequenz über zwei "Iteratoren" ist ein bekanntes Muster in C++.

    Ich empfehle Dir das Thema Arrays und Zeiger zu wiederholen. Beispielsweise sind

    void foo(int t[]);
    void foo(int *t);
    

    äquivalent. t ist jeweils ein Zeiger.

    Siggi198181 schrieb:

    Bzw. wie greifst du denn hier überhaupt auf ein einzelnes arrayfeld zu?

    Mit dem Dereferenzierungsoperator (der Stern): *start .

    Siggi198181 schrieb:

    und was beudeutet genau: return Zeiger auf neuen Not-Knoten mit "elem" als Wert;
    Bedeutet das array[elem] ?

    elem speichert den Wert des Arrayfeldes. Du wolltest ja "NOT" auch zu einem Blattknoten mit irgendeinem Wahrheitswert machen. Der Wahrheitswert wurde aus dem Array ausgelesen und steht jetzt in elem drin. Mit dem obigen Beispiel: elem wird bei einem Funktionsaufruf in Zeile 4 mit -3 initialisiert. Das signalisiert ein "Not-Blatt". Der Wahrheitswert steht im Array dahinter und wird in Zeile 9 ausgelesen. Nach jedem Lesezugriff wird der Zeiger so verändert, dass er auf das nächste zu lesende Element zeigt.

    Gruß,
    SP



  • Eine letzte Frage: Wie komme ich denn an den Zeiger vom ende?

    etwa so?

    int *endZeiger = &Zahlen[sizeOfArray];
    


  • Siggi198181 schrieb:

    Eine letzte Frage: Wie komme ich denn an den Zeiger vom ende?

    Kommt drauf an, wo Du die Daten speicherst.

    Siggi198181 schrieb:

    etwa so?

    int *endZeiger = &Zahlen[sizeOfArray];
    

    Nein, nicht ganz. Zahlen[sizeOfArray] würde ja auch das Element hinter dem letzten zugreifen, was nicht erlaubt ist.

    int *endZeiger = &Zahlen[0] + anzahl_der_gueltigen_elemente;
    

    Falls Zahlen ein Array oder ein nicht leerer std::vector<int> ist.

    Hier ist eine Alternative mit std::vector:

    void baum_zu_array(knoten const* wurzel, std::vector<int> & wohin)
    {
      if (!wurzel) return;
      ...
      wohin.push_back(wert);
      ...
      if (bin-op-knoten) {
        knoten* kind1 = ...;
        knoten* kind2 = ...;
        if (!kind1 || !kind2) throw std::runtime_error("darf nicht sein!");
        baum_zu_array(kind1,wohin);
        baum_zu_array(kind2,wohin);
      }
      ...
    }
    
    knoten* array_zu_baum(std::vector<int> const& woher, int & position)
    {
      if (woher.size() <= position) return 0;
      int elem = woher[position]; ++position;
      if (elem==0 || elem==1) return Zeiger auf neuen Blattknoten;
      if (elem==-3) {
        elem = woher[position]; ++position;
        assert(elem==0 || elem==1);
        return Zeiger auf neuen Not-Blattknoten;
      }
      knoten* kind1 = array_zu_baum(woher,position);
      knoten* kind2 = array_zu_baum(woher,position);
      if (!kind1 || !kind2) throw std::runtime_error("zu wenig daten");
      return Zeiger auf neuen BinOp-Knoten, der kind1/kind2 als Kinder hat.
    }
    
    knoten* array_zu_baum(std::vector<int> const& woher)
    {
      int pos = 0;
      return array_zu_baum(woher,pos);
    }
    
    /// erzeugt eine Kopie des Baumes
    knoten* umstaendliches_klonen(knoten* wurzel)
    {
      std::vector<int> dings;
      baum_zu_array(wurzel,dings);
      return array_zu_baum(dings);
    }
    

    Gruß,
    SP



  • so habe das jetzt mal wirklich genauso gemacht wie du es beschrieben hast. und die methode wird vom kompiler korrekt übersetzt und es erscheinen keine fehlermeldungen. Also scheint es so als ob alles korrekt sei. Allerdings frage ich mich wie ich das jetzt aufrufe.
    denn mich verwirrt

    int const*& start
    

    ich dachte eigentlich dass es so ist:

    int* begin = meinArray;
    int* end = &meinArray[0]+(sizeOfArray-1);
    node* root = aufbauen(begin, end);
    

    dies geht aber wiederum nicht 😕



  • Was ist meinArray und was ist sizeOfArray?

    Bei

    int const*& start
    

    handelt es sich um eine Referenz auf einen Zeiger auf int const .

    Gruß,
    SP



  • in meinArray ist quasi der Baum gespeichert. Also ist

    int* begin = meinArray;
    

    doch der Zeiger auf das erste Element in meinem Array.
    Und SizeOfMyArray ist quasi die Anzahl meiner Felder im Array. Also ist das doch quasi der Zeiger auf das Ende des Array.
    Andererseits könnte ich doch das auch so machen, dass ich sage das Ende des arrays ist das letzte Element des Arrays. Und am Ende des Arrays ist ja eigentlich immer ein boolscher knoten gespeichert. damit müsste ich nicht über das ende des arrays hinauslaufen.
    Also könnte ich das folgendermaßen machen:

    if(start == end) return new node(elem);
    

    Und dadurch dass ich im konstruktor die nachfolger auf NULL setze, dürfte da doch nichts passieren.

    Die eigentliche Frage ist ja aber wie denn der Aufruf der Methode dann aber wäre. Auf jeden Fall mal nicht so wie ich es oben beschrieben habe



  • Siggi198181 schrieb:

    in meinArray ist quasi der Baum gespeichert.

    Das war mir klar. Ich wollte aber den genauen Typ wissen und woher der Wert für sizeOfArray kommt.



  • Ich wollte aber den genauen Typ wissen

    das ist ein integer array.

    woher der Wert für sizeOfArray kommt.

    Und den Wert von sizeOfArray weiß ich ja vom umwandeln vorher. Ich kann mir ja ausrechnen wieviele felder ich benötige bevor ich den baum in das array umwandel und diese Größe speichere ich 🙂



  • Sebastian Pizer schrieb:

    Beide der folgenden Bäume haben die gleiche Infix-Ausgabe (ohne Klammerung)

    AND      OR
      / \      /\
     OR  1    0  AND
     /\          / \
    0  1        1   1
    
    infix:  0 OR 1 AND 1  (beide)
    präfix: AND OR 0 1 1  (erster Baum)
    präfix: OR 0 AND 1 1  (zweiter Baum)
    

    Gruß,
    SP

    Stimmt schon. Hat sogar einen Grund: Der Binäre Ausdruck ist äquivalent.


Anmelden zum Antworten