Array in einen Baum umwandeln



  • Hallo Leute, ich hoffe jemand kann mir helfen.

    Also ich habe folgendes Problem: Ich arbeite mit Binärbäumen, die eine boolsche Formel enthalten. D.h: ein Knoten hat entweder zwei oder keine nachfolger - in den blättern stehen die boolschen werte und in den inneren knoten stehen die Operatoren. Das funktioniert auch alles soweit. Jetzt muss ich aber solch einen Baum als Array speichern(das funktioniert auch wunderbar. Habe den Baum inorder durchlaufen und mir damit ein Array erstellt) und an einer anderen Stelle muss ich den umgekehrten Weg gehen, also aus diesem Array einen Baum erstellen, der wiederum die boolsche Formel enthält. Und hier liegt mein Problem. Komme nämlich einfach nicht dahinter wie das gehen soll.
    Könnte mir das vielleicht jemand als pseudocode hinschreiben wie das ungefähr aussehen könnte??

    Danke



  • Mach doch mal ein kleines Beispiel. Wie sieht das aus, was Du in das Array geschrieben hast?



  • Baum:

    AND
           /   \
         OR    AND
        / \    /  \
       0   1  1    N1
    

    Also ich habe mir das so gedacht: ich speichere einen integerarray mit folgenden Werten: NOT = -3
    AND = -2
    OR = -1
    sonst false = 0 und true = 1

    damit würde sich hier folgendes Array ergeben:

    ARRAY:

    {-3, 1, -2, 1, -2, 1, -1, 0}



  • Müsste dein Not nicht auch wieder ein Knoten mit zwei Blättern sein anstatt im Blatt zu stehen?

    Also:

    AND
       /   \
      OR   AND
     / \  /  \
    0  1  1  NOT
             / \
            0   1
    

    Oder Ähnlich?

    Und anscheinend hast du das Array von hinten aufgebaut. Inordner beginnt man doch eigentlich Links.



  • ups, ja habe ich auch gemacht. habe nur den baum verkehrt rum aufgezeichnet. Und der NOT Operator wird in einem Knoten mitgespeichert. Ein knoten im baum ist entweder ein operatorknoten oder ein blatt, das sowohl den boolschen wert als auch den NOT operator enthält.



  • Das mit dem Not im Blatt find ich irgendwie Merkwürdig zumal du das in deinem Array als eigenes Element speicherst. Ich würde also entweder das NOT 1 nach 0 auflösen oder das Not in einen Operatorknoten packen sonst ist das ganze irgendwie inkonsistent und dann ist das mit dem Array parsen auch leichter.



  • Tolpan schrieb:

    Das mit dem Not im Blatt find ich irgendwie Merkwürdig zumal du das in deinem Array als eigenes Element speicherst. Ich würde also entweder das NOT 1 nach 0 auflösen oder das Not in einen Operatorknoten packen sonst ist das ganze irgendwie inkonsistent und dann ist das mit dem Array parsen auch leichter.

    Das mag komisch aussehen, ist aber wirklich so gewollt.



  • Außerdem sollte "NOT" eigentlich nur einen Subknoten haben, oder eben direkt im Knoten definiert sein, oder eben nicht.
    In meinem binären Baum hab ich NOT als logischen Knoten definiert, aber man kann sich das natürlich auch sparen.



  • 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


Log in to reply