LevelOrder Traversierung von Bäumen

[Jaipur]

Hi,

wie kann ich in einem Binären Baul eine LevelOrder Traversierung vornehmen?

Es gibt einen Pointer auf das erste Element,

jedes Element hat zwei Pointer, einen für LINKS und einen für RECHTS.

# define DATA struct data

# define ROOT struct root


DATA

{

	DATA *l;	/* left eye */

	DATA *r;	/* right eye */

	int x;

};


ROOT

{

	DATA *first;

};


ROOT *erstelle()

{

	ROOT *root;


	root = (ROOT *)malloc( sizeof(ROOT) );

	root->first = NULL;


	return root;

}


void anmelden(ROOT *t, int x)

{

	DATA *neu,*d;


	neu = (DATA *)malloc( sizeof(DATA) );


	if( t->first == NULL )

	{

		t->first = neu;

		neu->l = NULL;

		neu->r = NULL;

		neu->x = x;

		return;

	}


	for( d=t->first; d; )

	{

		if( x == d->x )

			return;


		if( x <= d->x )

		{

			if( d->l == NULL )

			{

				d->l = neu;

				neu->x = x;

				break;

			}

			else

				d = d->l;

		}

		else

		{

			if( d->r == NULL )

			{

				d->r = neu;

				neu->x = x;

				break;

			}

			else

				d = d->r;

		}

	}

	neu->l = NULL;

	neu->r = NULL;

}


void main()

{

	ROOT *t;	

	t = erstelle();


	anmelden(t, 10);

	anmelden(t, 5);

	anmelden(t, 16);


/* hier würde ich gerne level für level anzeigen wollen */

/* z.b in dieser form: show(t); */

}

Ich habe zwar eine kleine Vermutung das, das ganze Rekursiv aufgebaut werden muss ... aber wie?

[hoagi]

Laut Robert Sedgewick( Algorithmen in C )

kann die Leveltraversie mit ein Warteschlage realisiert werden und zwar im Buchbeispiel iterativ und nicht rekursiv

DATA

{

DATA *l; /* left eye */

DATA *r; /* right eye */

int x;

};

show( DATA * d )

{

put(d);

while( !queueempty() )

{

d = get();

ausgabe(d);

if( d -> l )

put( d -> l );

if( d -> r )

put( d -> r );

}

}

Keine Hexerei also

Hoagi

P.S.

Mal ne blöde Frage : Wie kriegt man die Leerzeichen am Anfang einer Zeile?

[Crush]

Ach, das mit dem Show() hab ich überlesen - das wäre natürlich einfach gewesen wie man sieht.

Stattdessen habe ich das Einfügen mal rekursiv umgeschrieben.

#define abbruch break==true;return;

Insert(Data*d, int x)

{

static bool break=false; // Abbruchkriterium

static int x=x;

// müßte nicht unbedingt sein, aber bei Klassen-Kapselung muß das auf jeden fall innerhalb der Funktion stehen, deshalb mach ich das einfach mal so - neu müßte dann auch noch als Referenz übergeben werden

if (break==true) return;

if (x==d->x) abbruch;

{

if (x<=d->x)

{

if( !(d->l))

{

d->l = neu;

neu->x = x;

abbruch;

}

else Insert(d->l, x);

}

else

{

if(!(d->r))

{

d->r = neu;

neu->x = x;

abbruch;

}

else Insert(d->r,x);

}

Aufruf ganz einfach:

// erst mal neu erstellen und initialisieren, dann

Insert(t->first,x);

Ich hoffe mal, daß kein zu drastischer Fehler drin ist - vielleicht läufts sogar schon - wer weiß - ich habe mich an Deine Schleife gehalten und nur umgeschrieben.

Sorry, da bin ich wohl etwas übers Ziel rausgeschossen, weil ich das mit dem Show() wohl übergangen habe.

Man sieht aber hiermit sicher schon wie man den Show() rekursiv machen sollte.

[Crush]

@Hoagi

JEDER ALGORHYTHMUS kann iterativ oder rekursiv dargestellt werden (auch wenn die Transformation manchmal etwas schwierig ist). Auch sowas wie der Bubble-Sort, Fibonacci-Zahlen, Türme von Hanoi oder die Lösung des 8-Damen-Problems: Einfach alles! (mir ist jedenfalls keine Ausnahme bekannt). Meist ist halt die rekursive Alternative optisch leichter verständlich und kürzer, weshalb man sich gerne dafür entscheidet. Es ist allgemein meist einfacher sich in den rekursiven Funktionen reinzuversetzen als in Iterative - diese können nämlich in manchen Fällen echt unnötig kompliziert wirken und unverständlich aussehen. Die Laufzeiteffizienz ist bei der Iteration natürlich etwas besser, weil keine Unterprogrammaufrufe erfolgen (aber je nach Algorhythmus verschwindend gering), keine unnötigen Hilfsvariablen in jedem Aufruf erzeugt werden (falls verwendet) und keine Übergabeparameter weitergereicht werden müssen (also unnötige Stack-Operationen und Registerabsicherungen nicht notwendig sind).

Das mit dem Queueempty() erscheint mir etwas komisch, weil man mit d doch alles was notwenig ist fragen kann. Es sei denn man hat die Blätter einfach nur hintereinander in eine Queue gelegt oder aber x als Prio für eine Priority-Queue verwendet. Die Laufzeiteffektivität beim Einfügen in Prio-Queues aber wesentlich schlechter liegen als bei Binärbäumen.

Es gibt ja grundsätzlich mal 3 Arten einen Baum zu traversieren: Inorder, Präorder, Postorder. Dabei wird entweder von oben nach unten & links nach rechts durchwandert, von unten links nach oben und rechts nach rechts ab oder von unten links nach oben. Da sehen die Traverse-Funktionen natürlich dann je nachdem etwas anders aus.

Weil in dem Beispielvom hoagi die Ausgabe put() genannt wird nenne ich die einfach auch mal so:

Hier ist halt eine höhere Absturzsicherheit gewährleistet (und so steht´s in vielen Büchern):

Leveltrav(DATA * d)

{

if (d) // hier werden die 0-Zeiger von rechts raussortiert

{

Leveltrav(d->l); // das linke Blatt muß ja immer belegt sein

put(d);

Leveltrav(d->r);

}

}

oder aber ohne diese Einsprünge in rechte 0-Zeiger. Ein leeres Blatt würde jedoch zum Absturz führen - aber das sollte ja nicht sein, solange man nicht mit anderartigen binären Suchbäumen arbeitet, bei denen das erlaubt ist.

Leveltrav(DATA * d)

{

put (d);

Leveltrav(d->l);

if (d->r) Leveltrav(d->r);

}

Das sieht zwar sehr gleich aus, aber es wird bei Leerzeigern nicht unnötig in Leveltrav gesprungen und das sinnlose Checken der linken Blätter wird unterlassen. Wie man sieht ist der Code hier kleiner als bei Hoagi und somit kann er u.U. trotz der oben genannten Zusatzoperationen bei Rekursion sogar schneller sein!

[hoagi]

Hi Crush,

wahrscheinlich kann alles irgendwie rekursiv dargestellt werden.

Die Frage ist narürlich ob wir ein originär rekursives Problem haben, oder nicht.

Die andere Frage ist ob deine rekursive Lösung wirklich das gleiche Ergebniss hat wie das Iterative.

Die Antwort auf die ersten Frage kann meiner Meinung dadurch entschieden werden, ob für das Programm eine Stackstruktur notwendig ist.

Dadurch das sich das Problem durch eine Warteschlange lösen lässt denke ich mal das das Problem kein rekursives ist

( ich möchte jetzt mal nicht behaupten das es sich rekursiv umstellen lässt )

Für die zweite Frage habe ich das Program mal ein wenig umgeschrieben.

EInfach als WIN32 Konsolenprogram kompilieren und starten und du wirst sehen das das Ergebnis ein wirklich anderes ist.

Die put() -Funktion ist übrigens in deiner Lösung nicht erforderlich.

// Traverse.cpp : Definiert den Einsprungpunkt für die Konsolenanwendung.

//

#include "stdafx.h"

#include <stdlib.h>

# define DATA struct data

# define ROOT struct root

DATA

{

DATA *l; /* left eye */

DATA *r; /* right eye */

int x;

};

DATA *first;

void erstelle()

{

first = (DATA*)malloc( sizeof(DATA) );

first -> l = NULL;

first -> r = NULL;

first -> x = 0;

}

DATA *qu[1000];

long head,tail;

void put( DATA * r )

{

qu[tail++] = r;

}

DATA * get()

{

return (qu[head++]);

}

int quempty()

{

return head ==tail;

}

void ausgabe( DATA * d )

{

printf( "d->x = %d\n",d->x );

}

void show( DATA * d )

{

head = tail = 0;

if ( d )

put(d);

while( !quempty() )

{

d = get();

ausgabe(d);

if( d -> l )

put( d -> l );

if( d -> r )

put( d -> r );

}

}

void anmelden(DATA *t, int x)

{

DATA *neu,*d;

neu = (DATA *)malloc( sizeof(DATA) );

if(first == NULL )

{

first = neu;

neu->l = NULL;

neu->r = NULL;

neu->x = x;

return;

}

for( d=first; d; )

{

if( x == d->x )

return;

if( d->l == NULL )

{

d->l = neu;

neu->x = x;

break;

}

else

{

if( d->r == NULL )

{

d->r = neu;

neu->x = x;

break;

}

else

d = d->l;

}

}

neu->l = NULL;

neu->r = NULL;

}

Leveltrav(DATA * d)

{

ausgabe(d);

if( d->l )

Leveltrav(d->l);

if (d->r)

Leveltrav(d->r);

}

void main()

{

DATA *t;

erstelle();

t = first;

anmelden(t, 1);

anmelden(t, 2);

anmelden(t, 3);

anmelden(t, 4);

anmelden(t, 5);

anmelden(t, 6);

anmelden(t, 7);

anmelden(t, 8);

anmelden(t, 9);

anmelden(t, 10);

anmelden(t, 11);

anmelden(t, 12);

anmelden(t, 13);

anmelden(t, 14);

anmelden(t, 15);

anmelden(t, 16);

anmelden(t, 17);

anmelden(t, 18);

anmelden(t, 19);

anmelden(t, 20);

show( (DATA*)t );

Leveltrav(t) ;

/* hier würde ich gerne level für level anzeigen wollen */

/* z.b in dieser form: show(t); */

}

Hoagie

PS: WIe krieg ich denn nu die Leerzeichen an den Anfang der Zeile.

[hoagi]

           


              Achsogehtdas 

:) :)

[Crush]

Ich denke, daß der iterative Ansatz ohne Stack nur auskommt, wenn man sich an der Stackstruktur selbst orientiert. Die Art des Containers spielt normalerweise eine relativ untergeordnete Rolle, sofern die Elemente durch Zeiger verknüpft und man einfach den Container durchwandert. Doch die Art des Containers kann die Suche erheblich beschleunigen (mit Hashes z.B.).

Ich verstehe jetzt die Frage nicht ganz, aber wenn Du vorhast die Levels der Blätter direkt zu durchwandern, dann mußt Du mit Reference-Couting arbeiten und die "Tiefe" bei der Ausgabe berücksichtigen (zu hoch->abbruch, zu klein-> weiter wandern in den linken und rechten Ast).

Wie die Frage mit den Leerzeichen gemeint ist hab ich nicht so ganz gecheckt, aber nach dem "Achsogehtdas" vermute ich wirst Du das schon selber rausgefunden haben.

[hoagi]

Hi Crush

hier geht es um das konkrete Problem der Level-Order-Traversierung:

Dabei geht es darum alle Knoten des Baumes in einer bestimmten Reihenfolge zu besuchen.

Immer alle Knoten einer Stufe zu besuchen.

Dann auf die nächste Ebene, hier alle Knoten besuchen

usw...

(Ich wollte hier ein ein kleines Diagram einbinden, aber irgendwie bin da nicht künstlerich genug zu )

Ich denke, daß der iterative Ansatz ohne Stack nur auskommt, wenn man sich an der Stackstruktur selbst orientiert.

Stimmt nur , wenn ich den Satz richtig verstehe, wenn ein Stack benötigt wird.

Im meinem Beispiel nutze ich aber keinen Stack, sondern eine Warteschlange.

Würde mein Programbeispiel einfach durch einen Stackersetzen.

Also statt queueempty() , put() und get() die entsprechenden

stackempty() , push() und pop() - Implementierungen nutzen

( und damit zu einer wirklich rekursiven Darstellung kommen )

hätten wir keine Level-Order -Traversie mehr , sondern eine Preorder - Traversie.

Also erste linke zweige vorwärst bis zum Ende , dan rechte Zweige rückwärts bis zum Ende´( oder so ähnlich ).

Ich denke Rekursion ist ne schöne Sache, aber es gibt Behandlungen von Datenstrukturen, die nicht rekursiv sind.

PS:

Mit Leerzeichen vorder Zeile meine ich übrigens das Einrücken des Codes im Text.

Hoagi

[Crush]

Vielleicht ist hier ja noch ein Hinweis drin versteckt. Jetzt kapiere ich das mit dem Levelorder auch - also die Ebenen einzeln sollen abgeerntet werden. Das ist tatsächlich etwas schwieriger. Vielleicht wäre die Lösung eine doppelt verkettete Liste, welche nicht nur die Baumstruktur enthält, sondern auch noch eine Level-Liste die unabhängig vom lr-Baum verknüpft ist ... sowas hab ich auch noch nicht gemacht oder gebraucht.

http://www.csc.uvic.ca/~csc115/slides/7-Trees.ppt

http://netdb.chungbuk.ac.kr/~jrshin/algorithm/

[hoagi]

Ich will ja nicht penetrant wirken aber die Lösung ist die von mir vorgeschlagende.

Ist übrigens nicht auf meinen Mist gewachsen,

sondern stammt aus dem schon erwähnten Buch

"Algorithmen in C" von Robert Sedgewick

[Jaipur]

Hi,

danke Euch!

Habe mich jetzt drangesetzt, musste zwar dafür eine Queue erstellen, aber es funzt

Wenn interesse besteht kann ich es ja posten

[Crush]

Interesse besteht!

[Jaipur]

Hi!

main.cpp

# include "baum.h"

# include "queue.h"


void main()

{

	ROOT *t;


	t = erstelle();


	anmelden( t,10);

	anmelden( t,5);

	anmelden( t,16);

	anmelden( t,2);

	anmelden( t,8);

	anmelden( t,12);

	anmelden( t,18);

	anmelden( t,1);

	anmelden( t,4);

	anmelden( t,6);

	anmelden( t,9);

	anmelden( t,11);

	anmelden( t,14);

	anmelden( t,17);

	anmelden( t,19);

	anmelden( t,3);

	anmelden( t,7);

	anmelden( t,13);

	anmelden( t,15);


	printf("   preorder: ");

	ausgabe( t,PREORDER);

	printf("    inorder: ");

	ausgabe( t,INORDER);

	printf("  psotorder: ");

	ausgabe( t,POSTORDER);

	printf(" levelorder: ");

	ausgabe( t,LEVELORDER);

}

baum.h

# ifndef BAUM_H

# define BAUM_H


# include <stdio.h>

# include <stdlib.h>

# include <time.h>


# define DATA struct data

# define ROOT struct root


# define PREORDER	0

# define INORDER	1

# define POSTORDER	2

# define LEVELORDER	3


DATA

{

	DATA *l;

	DATA *r;

	int x;

};


ROOT

{

	DATA *first;

};


extern ROOT *erstelle();

extern void anmelden( ROOT *t, int x);

extern void suchen(ROOT *t, int x);

extern void ausgabe( ROOT *t, int typ);


# endif

baum.cpp

# include "baum.h"

# include "queue.h"


ROOT *erstelle()

{

	ROOT *root;


	root = (ROOT *)malloc( sizeof(ROOT));

	root->first = NULL;


	return root;

}


void anmelden( ROOT *t, int x)

{

	DATA *neu,*d;


	neu = (DATA *)malloc( sizeof(DATA));


	if( !t->first)

	{

		t->first = neu;

		neu->l = NULL;

		neu->r = NULL;

		neu->x = x;

		return;

	}


	for( d=t->first; d; )

	{

		if( x == d->x)

			return;


		if( x <= d->x)

		{

			if( !d->l)

			{

				d->l = neu;

				neu->x = x;

				break;

			}

			else

				d = d->l;

		}

		else

		{

			if( !d->r)

			{

				d->r = neu;

				neu->x = x;

				break;

			}

			else

				d = d->r;

		}

	}

	neu->l = NULL;

	neu->r = NULL;

}


void suchen( ROOT *t, int x)

{

	DATA *d;


	for( d=t->first; d; )

	{

		if( x < d->x)

			d = d->l;

		else if( x > d->x)

			d = d->r;

		else if( x == d->x)

		{

			printf("zahl: %d\n",d->x);

			break;

		}

	}

}


void preorder( DATA *d)

{

	if( d)

	{

		printf("%3d",d->x);

		preorder( d->l);

		preorder( d->r);

	}

}


void inorder( DATA *d)

{

	if( d)

	{

		inorder( d->l);

		printf("%3d",d->x);

		inorder( d->r);

	}

}


void postorder( DATA *d)

{

	if( d)

	{

		postorder( d->l);

		postorder( d->r);

		printf("%3d",d->x);

	}

}


void levelorder( DATA *d)

{


	QUEUE *Q;

	Q = Qconstruct();


	Qput(Q,d);


	while( !Qempty(Q))

	{

		d = Qget(Q);

		printf("%3d",d->x);


		if( d->l)

			Qput( Q,d->l);

		if( d->r)

			Qput( Q,d->r);

	}


	Qdestruct( Q);

}


void ausgabe( ROOT *t, int typ)

{	

	switch( typ)

	{

		case INORDER:

			inorder( t->first);

			break;

		case PREORDER:

			preorder( t->first);

			break;

		case POSTORDER:

			postorder( t->first);

			break;

		case LEVELORDER:

			levelorder( t->first);

	}

	printf("\n");

}

queue.h

# ifndef QUEUE_H

# define QUEUE_H


# include <stdio.h>

# include <stdlib.h>

# include "baum.h"


# define QUEUE struct queue

# define ENTRY struct entry


ENTRY

{

	ENTRY *nxt;

	DATA *d;

};


QUEUE

{

	ENTRY *first;

	ENTRY *last;

};


extern QUEUE *Qconstruct();

extern void Qdestruct( QUEUE *Q);

extern void Qput( QUEUE *Q, DATA *d);

extern DATA *Qget( QUEUE *Q);

extern int Qempty( QUEUE *Q);

extern void Qausgabe( QUEUE *Q);


# endif

queue.cpp

# include "queue.h"

# include "baum.h"


QUEUE *Qconstruct()

{

	QUEUE *Q;


	Q = (QUEUE *)malloc( sizeof( QUEUE) );


	if( !Q)

		return NULL;

	Q->first = NULL;


	return Q;

}


void Qdestruct( QUEUE *Q)

{

	ENTRY *E;


	while( E = Q->first)

	{

		Q->first = E->nxt;

		free(E);

	}

	free(Q);

}


void Qput( QUEUE *Q, DATA *d)

{

	ENTRY *E;


	E = (ENTRY *)malloc( sizeof(ENTRY));


	E->nxt = NULL;

	E->d = d;


	if( Q->first)

		Q->last->nxt = E;

	else

		Q->first = E;


	Q->last = E;

}


DATA *Qget( QUEUE *Q)

{

	ENTRY *E;

	DATA *d;


	d=(DATA *)malloc( sizeof(DATA));


	E = Q->first;


	d = E->d;

	Q->first = E->nxt;

	free( E);


	return d;

}


int Qempty(QUEUE *Q)

{

	if( Q->first)

		return 0;

	else

		return 1;

}


void Qausgabe(QUEUE *Q)

{

	ENTRY *E;


	for( E=Q->first; E; E=E->nxt)

		printf("%3d",E->d->x);

}

Das einzige was ich noch machen könnte aber ausgelassen habe ist es, eine rekursionsfreie Preorder Traversierung des Baumes.

traversierung( NODE *n)

{

	push(n);


	while( !stackempty())

	{

		n = pop();


		if( n->right)

			push( n->right);

		if( n->left)

			push(n->left);

	}

}

Kann man hier durch vertauschen der if Bedingungen eine rekursionsfreie Postorder Traversierung des Baumes hinbekommen?

(Habe selbst noch nicht darüber nachgedacht, würde es aber dennoch gerne wissen

Und über kritik würde ich mich auch sehr gerne freuen!

Lob ist aber auch OK *g*.

[Crush]

Erst mal das Lob: Hast Du prima gemacht - das lernt man aber nicht in der Schule - in welchem Lehrjahr bist Du? Fertig? Schon prima!

Keine Kritik eher eine Frage: Warum arbeitest Du nur mit C (malloc(), free())?

Zum Thema Postorder Traverse: Du mußt das unterste Leaf links und dann von der nächsten Abzweigung rechts rückwärts (also nach oben zur Wurzel) durchwandern. Das läßt sich wohl nur mit einer doppelt verketteten Liste (prev) erreichen. Jedenfalls kann ich mir nur schwer vorstellen, wie man das anders hinbekommen könnte. Oder Du arbeitest mit einem Stack und beim Durchwandern ins unterste Blatt mußt Du alle noch nicht abgeernteten Blätter kurzfristig auf den Stack pushen und beim Nach-oben-wandern wieder runterpoppen (hehe hört sich lustig an).

Mit dem Austauschen der Ifs wirst Du das wohl nicht hinbekommen.

Ansonsten hätte ich keinen weiteren Vorschlag.

Gute Arbeit!

[Jaipur]

Hi,

- das lernt man aber nicht in der Schule - in welchem Lehrjahr bist Du? Fertig? Schon prima!

Lass das bloß nicht meinen Prof hören!!! ...

Fachbereich: Elektrotechnik

Studiuengang: Informations- & Kommunikatinstechnik

Semster: 1

[Mr. X]

Hi,

ich weiß das passt nicht wirklich hier rein (weil es ja ne andere Programmiersprache ist - es geht aber um dasselbe Thema)

also ihr habt ja den ganzen Spaß jetzt in C gemacht, aber hat jemand ne Idee wie man Levelorder eines binären Baums in Delphi macht? Ich möchte also eine Ausgabe bei der ein bestehender binärer Baum levelweise ausgegeben wird. Wäre nett, wenn jemand solch einen Quelltext posten könnte.

Danke schon mal im Voraus.

[Guybrush Threepwood]

Genauso wie in C, nur mit der Delphi Syntax. Der Algorithmus bleibt der gleiche

[Mr. X]

Ja das is mir schon klar, aber ich hab keinen Plan vom C Syntax, und weiß somit nicht wie ich das ganze "übertragen" soll. Wenn ihr selber kein Delphi könnt, wäre ne theoritische Anleitung nicht schlecht, danke.

[Crush]

Ist nicht in den Texten zwischen den Codezeilen einigermaßen verständlich und detailliert beschrieben, was man so tut - im Sinne eine theoretischen Anleitung?

[Astasor]

:old ich spiel mal totengräber.

hat die levelordertraversierung genau wie alle anderen "baumdurchläufe" auch eine laufzeit von O(n)?

Aus dem Code erschliest sich mir das nicht wirklich.

Oder hängt das gar davon ab, wie man es implementiert?

mfg Astasor.

[Klotzkopp]

Oder hängt das gar davon ab, wie man es implementiert?

Natürlich, schlechter geht immer. Besser als O(n) geht nicht. Aber die Umsetzung mit der Queue ist schon in Ordnung.

Die Queue-Operationen laufen in konstanter Zeit, und jeder Knoten wird einmal in die Queue gesteckt, einmal wieder rausgeholt und einmal ausgegeben.