Pseudocode für "Suche grösstmögliche Zahl in einem Binären Baum"
Results 1 to 7 of 7
  1. #1
    Jimmy's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    539
    Thanks
    0
    Thanked 0 Times in 0 Posts

    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

  2. #2

    Title
    Elite
    Join Date
    Feb 2002
    Posts
    482
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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)

  3. #3
    DoomedOne
    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:
    PHP Code:
    int maxElement(root)
    {
      if (
    root == null)
       return 
    Int.NegInfinity//das ist sicher kleiner als alles andere :)

      
    return max(root.key
                        
    maxElement(root.left), 
                        
    maxElement(root.right)
                        );


  4. #4

    Title
    Elite
    Join Date
    Jan 2002
    Location
    vienna/austria
    Posts
    471
    Thanks
    0
    Thanked 1 Time in 1 Post
    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"

  5. #5

    Title
    Elite
    Join Date
    Jan 2002
    Location
    vienna/austria
    Posts
    471
    Thanks
    0
    Thanked 1 Time in 1 Post
    das sollte natürlich zwetschkenknödel heißen...
    "Von allen Dingen die mir verloren gegangen, hab ich am meisten an meinem Verstand gehangen"

  6. #6
    DoomedOne
    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
    wie musst du die äste abklettern damit du sicher das größte hast.
    mmmmmh hab hunger

  7. #7

    Title
    Elite
    Join Date
    Jan 2002
    Location
    vienna/austria
    Posts
    471
    Thanks
    0
    Thanked 1 Time in 1 Post
    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!
    "Von allen Dingen die mir verloren gegangen, hab ich am meisten an meinem Verstand gehangen"

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •