Pseudocode für "Suche grösstmögliche Zahl in einem Binären Baum"

  • Gegeben sei ein binärer Suchbaum, dessen Knoten nacht nicht bekannten angeordnet sind (also die Regel kleinere sind linke Kinder, grössere sind "rightsons" wird ignoriert) - Gesucht wird ein Pseudocode der den grössten Schlüssel retourniert. Dabei soll die Laufzeit "ideal" sein und bei 2 gleich grossen grössten SChlüsseln soll das möglichst linke gewählt werden.
    Viel Spaß ! *seufz* :( --> Prüfungsordnerbeispiel ...

    Der beste Beweis, dass ausserirdische Intelligenz existiert, ist der dass bis jetzt noch keiner Kontakt zu uns aufgenommen hat

  • naja, da wird nix anderes überbleiben, als einen Algorithmus, der


    max_el = root


    1) schauen, ob p.key > max_el.key ist, wenn ja, p in max_el kopieren
    3) sich jetzt für p.leftson und dann für p.rightson rekursiv aufrufen, sofern die jeweils != NULL sind.


    Der hat dann Theta(n) Laufzeit und ich denke, wenn es gar keine Anordnungsregeln gibt, ist das optimal!


    In Pseudocode



    max_el = NULL;


    suche_max_in_ungeordnetem_Baum(p)
    {
    if (max_el == NULL) max_el = p;
    if (p.key > max_el.key) max_el = p;
    if (p.leftson != NULL) suche_max_in_ungeordnetem_Baum(p.leftson);
    if (p.rightson != NULL) suche_max_in_ungeordnetem_Baum(p.rightson);
    }


    Aufruf mit suche_max_in_ungeordnetem_Baum(root), nachher ist in max_el das Maximum (denke ich mal)

  • ich weiß nicht was ein ungeordneter binärer baum bringen soll aber wenn die es so wollen ;)


    ich glaub der algo von gck passt, hab aber auch einen entworfen:

  • eigentlich ist dieses bsp schon grundsätzlich in der angabe falsch!
    weil wenn es ein binärer suchbaum ist, dann muß auch das gesetz gelten, daß kleinere und größere schlüsseln getrennt werden, da sonst eine suche eigentlich nicht möglich ist... stellt euch mal vor der baum würde nicht aus zahlen bestehen sondern obstknödeln... wer sagt dem system ob ein zweitschenknödel ein größerer schlüssel ist als ein marillenknödel! drum geht das eigentlich nicht... ;) also muß es irgendwelche vorraussetzungen und gesetze für diesen speziellen baum geben!
    da wir solche bsp aber nie hatten ignorier ich das getrost... =)

    "Von allen Dingen die mir verloren gegangen, hab ich am meisten an meinem Verstand gehangen"

  • aber du kannst die zwetschkenknödel & marillenknödel der größe nach ordnen.
    Sie sind in einem Baum und du willst das größte für dich :D
    wie musst du die äste abklettern damit du sicher das größte hast.
    mmmmmh hab hunger

  • is schon klar doomedone... nur sind in der angabe eben keine sortiergesetze drin und damit kann ich das eben nichtmehr rausfinden! wenn gesagt wird, es sei ein binärer suchbaum ohne dem gesetz wo das größere zu suchen sei (nach welchen kriterien)... dann lässt es sich nicht lösen, oder denk ich da grundsätzlich falsch?


    und shit... ich hab auch hunger, sollte mir solche assoziationen sparen in zukunft! :D

    "Von allen Dingen die mir verloren gegangen, hab ich am meisten an meinem Verstand gehangen"