Level-Durchmusterung Binärer Baum
Results 1 to 23 of 23
  1. #1
    Clauko

    Exclamation Level-Durchmusterung Binärer Baum

    Hallo zusammen-
    Hat schon jemand versucht einen Pseudocode für die Level-Durchmusterung eines binären Baumes zu schreiben? diese Aufgabe wurde auf einem Zusatzübungsblatt für WINFler gestellt und ist auch schon mal zur VO-Prüfung gekommen.

    Angabe: Geben Sie einen Pseudocode einer Funktion Level-Order an, die folgendes Problem löst: Die Knoten eines binären Baumes sollen ebenenweise ausgegeben werden, d.h. zuerst die Wurzel, dann deren unmittelbare Nachfolgeknoten, dann jene, die jeweils zwei schritte von der Wurzel entfernt sind, und so weiter. Achten Sie darauf, dass Ihr Algorithmus auch dann funktionieren soll, wenn nicht alle Ebenen des Baumes vollständig gefüllt sind.

  2. #2
    eXe's Avatar
    Title
    Principal
    Join Date
    Feb 2002
    Posts
    99
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: Level-Durchmusterung Binärer Baum

    Original geschrieben von Clauko
    diese Aufgabe wurde auf einem Zusatzübungsblatt für WINFler gestellt und ist auch schon mal zur VO-Prüfung gekommen.
    was is das? von welchem semester? hu?

    hier gibts pascal algorithmen dafür

    http://www-user.tu-chemnitz.de/~mali...aum/order.html

  3. #3

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    534
    Thanks
    3
    Thanked 124 Times in 78 Posts
    das ist ja das erste Beispiel vom fünften Übungsblatt

  4. #4
    eXe's Avatar
    Title
    Principal
    Join Date
    Feb 2002
    Posts
    99
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ach das meint er mit zusätzlichem übungsblatt für winfler

  5. #5
    Clauko

    Level durchmusterung

    Unter dem oben angegebenen Link gibts nur was zu den Pre-, Post-... Durchmusterungen. Heisst das für eine Level durchmusterung muss ich die nur kombinieren? steh momentan auf der leitung...also noch niermand gelöst?

  6. #6

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    534
    Thanks
    3
    Thanked 124 Times in 78 Posts
    ich hab jetzt eine Methode geschrieben und getestet.
    ich glaub, sie funktioniert sogar, aber vielleicht gibt's auch bessere Möglichkeiten.

    Code:
     static void levelOrder(Knoten root)
     {
      boolean weiter=true;
      int ebene=0;
      while(weiter)
      {
       weiter=false;
       for (int n=0; n<=Math.pow(2,ebene)-1; n++)
       {
        int g=n; int z=1; Knoten p=root;
        while (z<=ebene && p!=null)
        {
         int j=g-(int)Math.pow(2,ebene-z);
         if (j>=0)
         {
          g=j;
          p=p.rightson;
         }
         else
         {
          p=p.leftson;
         }
         z++;
        }
        if (p!=null)
        {
         weiter=true;
         System.out.println(p.key);
        }
       }
       ebene++;
      }
     }

  7. #7

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    534
    Thanks
    3
    Thanked 124 Times in 78 Posts
    mir ist noch eine Möglichkeit eingefallen:
    Code:
    	static void levelOrder (Knoten root)
    	{
    		int ebene=0;
    		boolean weiter=true;
    		while (weiter)
    		{
    			weiter=gibEbeneAus(root,ebene);
    			ebene++;
    		}
    	}
    
    	static boolean gibEbeneAus(Knoten p, int ebene)
    	{
    		if (p!=null)
    		{
    			if (ebene==0)
    			{
    				System.out.println(p.key);
    				return true;
    			}
    			else
    			{
    				return gibEbeneAus(p.leftson,ebene-1) | gibEbeneAus(p.rightson,ebene-1);
    			}
    		}
    		else return false;
    	}

  8. #8

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    Wenn man den abstrakten Datentyp Queue (Warteschlange) einsetzt, ergibt sich eine sehr elegante Loesung: algodat1_ueblatt5.html

    /edit 25.05.02:
    Den obigen Link gibt es nicht mehr. Hier gibt es die (fast) komplete Loesung zum Uebungsblatt 5: algodat1_ue_loesung5.pdf
    Last edited by yrucrem; 12-04-2003 at 03:49.

  9. #9
    #!/usr/bin/perl's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Posts
    291
    Thanks
    0
    Thanked 1 Time in 1 Post
    Code:
    public void printLevelOrder ( Queue q ) {
        while ( ! q.isEmpty() ) {
            Node n = ( Node ) q.leave();
            if ( n.getLeftChild() != null )
    	q.enter( n.getLeftChild() );
            if  ( n.getRightChild() != null )
    	q.enter( n.getRightChild() );
            System.out.println("key: " + n.getKey() );
         }
    }
    in die main() kommt dann halt noch:

    Code:
    public static void main( String ARGS[] ) {
        BinaryTree b = new BinaryTree( ARGS );
        Node root = b.getRoot();
        Queue q = new Queue();
        q.enter( root );
        b.printLevelOrder( q );
    }
    die Klassen Queue, BinaryTree und Node musst halt noch reinklopfen, sollte aber kein Problem sein.

    Oliver
    this is Unix land. In silent nights, you can hear Windows machines reboot...

  10. #10

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts
    hab mir jetzt nicht alle geposteten algorithmen durchgelesen... aber an sich müsste doch eine ganz normale breitensuche (gestartet mit der wurzel vom baum) alles erledigen, oder?

    mfg, Chris
    hi, i'm a signature virus. copy me into your signature to help me spread.

  11. #11

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    780
    Thanks
    25
    Thanked 18 Times in 8 Posts
    na dann zeig mir mal eine "ganz normale breitensuche"...

  12. #12

    Title
    Elite
    Join Date
    Feb 2002
    Posts
    482
    Thanks
    0
    Thanked 0 Times in 0 Posts
    na ganz einfach: die root in einen Queue hauen, dann in eine Schleife gehen, in der du
    1) sofern vorhanden, das linke, dann das rechte Kind auf den Queue haust (jeweils nur, wenn != NULL)
    2) den aktuellen Knoten ausgibst oder sonstwas damit machst
    3) Schleife solange, bis der Queue leer ist.

    Fertig.

    Sofern man nicht einfach so einen Queue verwenden darf, tät ich folgenden Pseudocode dafür angeben:
    struct queue_el {
    p el; // das gequeuete Element
    queue_el *next, *last;
    }

    queuel *queue, *queue_end; // zu Beginn des Progs NULL

    queue_push(p *arg)
    {
    //neues queue_el x erzeugen, etwa mittels malloc()
    x.el = p;
    if (queue == NULL) { queue = x; queue_end = x; x.next = x.last = NULL; }
    else {
    x.next = queue;
    x.last = NULL;
    queue = x;
    x.next.last = x;
    }
    }

    queue_pop()
    {
    if (queue == NULL) return NULL;
    else {
    x = queue_end;
    queue_end = x.last;
    if (x.last == NULL) queue = NULL;
    return(x);
    }
    }

    Also push tut ein Element vorne in den Queue rein, pop holt das letzte hinten wieder raus.

    Dazu jetzt noch der Code für Breitensuche im Baum, der eben jene Queue verwendet:

    levelorder(root)
    {
    p = root;
    queue_push(root);
    while ( (p = queue_pop()) != NULL) {
    if ( p.leftson ) queue_push(p.leftson);
    if( p.rightson) queue_push(p.rightson);
    print p.key;
    }
    }

    Ich denke, dass müsste so passen, außer vielleicht der Code für den Queue, den hab ich jetzt nur improvisiert...

  13. #13

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    780
    Thanks
    25
    Thanked 18 Times in 8 Posts
    naja aber mittels queue is es ja oben auch gelöst worden... meines wissens nach is die "ganz normale" breitensuche halt mit ner queue...

  14. #14

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts
    mit "ganz normaler breitensuche" meine ich eine breitensuche, die ganz allgemein für beliebiege graphen gilt.. (da müssma für den test nix extra lernen )

    und den pseudocode dafür hat der georg im rep. am freitag auf die tafel geschrieben (http://rs6k.feig.at/informatik-forum...&threadid=1625 )

    mfg, Chris
    hi, i'm a signature virus. copy me into your signature to help me spread.

  15. #15
    enemy2k's Avatar
    Title
    Elite
    Join Date
    Dec 2001
    Location
    Wien
    Posts
    464
    Thanks
    3
    Thanked 2 Times in 2 Posts
    also ich kenne mich in algodat überhaupt ned aus und deswegen meine frage:

    sind diese pseudocodes gleich.... also kann ich den hier aus dem forum nehmen, versuchen zu verstehen und beim test einfach hinschreiben....... oder muss ich dort meinen eigenen entwickeln????

  16. #16

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts
    der georg hat im rep. gesagt, es wird ein pseudocode zu schreiben sein, der 'nicht so ganz trivial' ist...

    also nehm ich mal an, dass wir schon etwas neues schreiben werden dürfen

    mfg, chris
    hi, i'm a signature virus. copy me into your signature to help me spread.

  17. #17

    Title
    Elite
    Join Date
    Feb 2002
    Posts
    482
    Thanks
    0
    Thanked 0 Times in 0 Posts
    was meinst du mit gleich? Es reicht doch völlig aus, wenn du IRGENDEINEN code hinschreibst, der das gegebene Problem löst, egal, ob der in der VO oder sonstwo vorgekommen ist, oder ob du ihn selbst entwickelt hast!

  18. #18
    enola's Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    139
    Thanks
    0
    Thanked 0 Times in 0 Posts

    level order

    hallo!
    also so wie ich das am fr. beim georg verstanden habe ist level order im baum gleich breitensuche im graphen, also sollte man seine algorithmus dafür verwenden können. stimmt das jetzt oder nicht?
    danke
    never underestimate the power of denial

  19. #19
    eXe's Avatar
    Title
    Principal
    Join Date
    Feb 2002
    Posts
    99
    Thanks
    0
    Thanked 0 Times in 0 Posts
    naja fast bei nem graphen kanns ja kreise geben also muß man aufpassen dass man nicht in eine endlosschleife kommt beim durchmustern - glaub ich

  20. #20

    Title
    Elite
    Join Date
    Feb 2002
    Posts
    482
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ja, aber deshalb werden bereits gesuchte Knoten ja auch markiert, sonst würdest du in jedem Fall in eine Endlosschleife kommen.

  21. #21

    Title
    Elite
    Join Date
    Jan 2002
    Location
    vienna/austria
    Posts
    471
    Thanks
    0
    Thanked 1 Time in 1 Post
    in ne endlosschleife kannst du ja gar nicht geraten weil der algorithmus ja knoten markiert! und nicht mehr zu markierten zurückkehrt
    "Von allen Dingen die mir verloren gegangen, hab ich am meisten an meinem Verstand gehangen"

  22. #22
    eXe's Avatar
    Title
    Principal
    Join Date
    Feb 2002
    Posts
    99
    Thanks
    0
    Thanked 0 Times in 0 Posts
    war auch grundsätzlich gemeint

  23. #23

    Title
    Elite
    Join Date
    Jan 2002
    Location
    vienna/austria
    Posts
    471
    Thanks
    0
    Thanked 1 Time in 1 Post
    achso, dann sorry für meine belehrenden worte *smiles*
    ignore last post
    "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
  •