Array in einen Baum umwandeln



  • 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.



  • Siggi198181 schrieb:

    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 🙂

    Warum nimmste nicht einfach einen std::vector<int> ?!

    spätzünder schrieb:

    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)
    

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

    Das ist doppelt Quatsch. Erstens ist

    (a OR b) AND c  <==>  a OR (b AND c)
    

    falsch (setze a=1,b=0,c=0) und zweitens wäre es auch kein Grund dafür, dass die Infix Ausgabe ohne Klammerung nicht eindeutig dekodierbar ist.

    Gruß,
    SP



  • Also ich habe jetzt das ganze mit dem Vektor gemacht so wie du es geschrieben hast und es funktioniert. Und da mir das ganze ja prinzipiell auch egal ist ob array oder Vektor passt das so.
    Auf jeden Fall vielen vielen Dank für die Geduld und die Hilfe 😃

    Gruß Siggi


Anmelden zum Antworten