Binäre Bäume - schulnote.de 
Akzeptieren

Unsere Webseite nutzt Cookies. Wenn Sie auf dieser Webseite bleiben, nehmen wir an, dass Sie damit einverstanden sind. Sie können unsere Cookies löschen. Wie das geht, erfahren Sie in unserer Datenschutzerklärung. Mehr erfahren



Impressum | Datenschutzerklärung Startseite




 Apache HTTP Server Test Page powered by CentOS

Apache 2 Test Page
powered by CentOS

This page is used to test the proper operation of the Apache HTTP server after it has been installed. If you can read this page it means that the Apache HTTP server installed at this site is working properly.


If you are a member of the general public:

The fact that you are seeing this page indicates that the website you just visited is either experiencing problems or is undergoing routine maintenance.

If you would like to let the administrators of this website know that you've seen this page instead of the page you expected, you should send them e-mail. In general, mail sent to the name "webmaster" and directed to the website's domain should reach the appropriate person.

For example, if you experienced problems while visiting www.example.com, you should send e-mail to "webmaster@example.com".

If you are the website administrator:

You may now add content to the directory /var/www/html/. Note that until you do so, people visiting your website will see this page and not your content. To prevent this page from ever being used, follow the instructions in the file /etc/httpd/conf.d/welcome.conf.

You are free to use the images below on Apache and CentOS Linux powered HTTP servers. Thanks for using Apache and CentOS!

[ Powered by Apache ] [ Powered by CentOS Linux ]

About CentOS:

The Community ENTerprise Operating System (CentOS) Linux is a community-supported enterprise distribution derived from sources freely provided to the public by Red Hat. As such, CentOS Linux aims to be functionally compatible with Red Hat Enterprise Linux. The CentOS Project is the organization that builds CentOS. We mainly change packages to remove upstream vendor branding and artwork.

For information on CentOS please visit the CentOS website.

Note:

CentOS is an Operating System and it is used to power this website; however, the webserver is owned by the domain owner and not the CentOS Project. If you have issues with the content of this site, contact the owner of the domain, not the CentOS Project.

Unless this server is on the centos.org domain, the CentOS Project doesn't have anything to do with the content on this webserver or any e-mails that directed you to this site.

For example, if this website is www.example.com, you would find the owner of the example.com domain at the following WHOIS server:

http://www.internic.net/whois.html





Titel:

Binäre Bäume


  Note: 2   Klasse: 11









Arbeit: Binäre Bäume

1. Allgemeines

Binäre Bäume werden grundsätzlich verwendet, um Zahlen der Größe nach, oder Wörter dem Alphabet nach zu sortieren. Dem einfacheren Verständnis zu Liebe werde ich mich hier besonders auf die Zahlen beziehen, doch mit Buchstaben besteht in der Funktionsweise kein Unterschied.

Zur Definition einiger Begriffe:

Knoten bzw. Knotenpunkte sind die Stellen, wo die Zahlen eingetragen werden.

Wurzel wird der aller oberste Knoten genannt.

Verzweigungen sind die Verweise eines Knoten auf seinen linken oder rechten Nachfolgers.

Als Tiefe wird bei den Binären Bäumen die Anzahl der Knotenpunkte bis zum tiefsten Element genannt.

Nimmt man n als Tiefe an, so kann ein binärer Baum maximal 2n -1 Knoten haben.









2. Funktionsweise



2.1 Eintragen



Das Prinzip basiert darauf, daß eine Zahl immer auf zwei weitere verweist, eine größere rechts und eine kleinere links. Die erste Zahl, die eingelesen wurde, dient als Wurzel. Von ihr gehen dann die weiteren Verzweigungen aus. Bei der nächsten Zahl vergleicht man diese mit der Wurzel.





Ist die neue Zahl kleiner als die Wurzel, folgt man dem linken Zweig, ist sie größer, dem Rechten. Steht dort wieder eine Zahl, wird wieder verglichen, bis man an einem freien Platz angekommen ist. Hat man einen freien Platz erreicht, kann die Zahl eingetragen werden.





2.2 Ausgeben



Möchte man nun die Zahlen ausgeben, fängt man wieder bei der Wurzel an. Sollen die Zahlen aufwärts sortiert ausgegeben werden, geht man den linken Verzweigungen nach, solange dies möglich ist. Ist man am äußersten linken Punkt angekommen, ist dies nun die niedrigste Zahl. Danach geht man eine Verzweigung zurück und nimmt diese Zahl, dann wird deren rechter Zweig abgearbeitet, wobei dort wieder zuerst nach links gegangen werden muß. Nachdem auch der rechte Zweig abgeschlossen wurde, geht man eine weitere Verzweigung zurück und macht das selbe noch einmal.

Sollen die Zahlen abwärts sortiert ausgegeben werden, muß man nur die Instruktionen im oberen Absatz befolgen, wobei man aber links und rechts vertauscht. Das heißt man geht zuerst zum äußersten rechten Knoten, usw.

Sucht man eine bestimmte Zahl braucht man nur an jedem Knotenpunkt vergleichen, ob diese Zahl größer oder kleiner ist, und geht dem entsprechend der linken (Zahl ist kleiner als Knoten) oder der rechten (Zahl ist größer als Knoten) Verzweigung nach, bis die Zahl gefunden wurde, oder die Verzweigung auf NICHTS (bzw. NULL) verweist.





3. Programmierung



Binäre Bäume werden mit Hilfe von Pointern programmiert. Jeder Knotenpunkt beinhaltet die eigene Adresse, die darin gespeicherte Zahl, einen Zeiger für den linken Zweig und einen weiteren für den rechten Zweig. Da das Umgehen mit Pointern in C noch am einfachsten ist und diese Programmiersprache noch halbwegs aktuell ist, sind die unten angeführten Beispiele in dieser Sprache geschrieben.





3.1 Einfügen



Die Prozedur für das Einfügen ist der, in Kapitel 3.3 über das Löschen beschriebenen teilweise ähnlich. In beiden Prozeduren lasse ich eine Hilfsvariable nachlaufen.





void eingeben (struct knoten *akt, int x);

{

struct knoten *hilfe;

if (akt != NULL)

{

if (akt => zahl != x)

{

if (akt => zahl > x)









{

hilf = akt;

eingeben (akt => links, x);

}

else

if (akt => zahl < x)

{

hilf = akt;

eingeben (akt => rechts, x);

}

}

}

else

{

akt = malloc (struct knoten);

akt => rechts = NULL;

akt => links = NULL;

akt => zahl = x;

if (hilf => zahl < x)

hilf => rechts = akt;

else

hilf => links = akt;

}

}





3.2 Ausgeben



Man kann sich die Zahlen natürlich auf mehrere Arten ausgeben lassen. Doch ich möchte nur zwei, die wahrscheinlich am häufigsten verwendet werden, zeigen.

Möchte man die Zahlen geordnet ausgeben, kann man folgende Prozedur benutzen, wobei akt bei Aufruf der Prozedur auf die Wurzel zeigen sollte:





void ausgabe (struct knoten *akt);

{

if (akt != NULL)

{

ausgabe (akt => links);

printf ("%d \n", akt => zahl);

ausgabe (akt => rechts);

}

}



Hat man sich, wie in Kapitel 3.4 beschrieben, die Tiefe eines binären Baumes bereits ausgerechnet, kann man die folgende Funktion verwenden, um den Baum in strukturierter Form darzustellen:









void ausgabe (struct knoten *akt, int tiefe);

{

int i;

if (akt != NULL)

{

ausgabe (akt => rechts, ++ tiefe);

for (i = 1; i < tiefe; i++) printf (" ");

printf ("%d \n", akt => zahl);

ausgabe (akt => links, tiefe);

}

}



Die ausgegebenen Daten sehen nach Aufruf der zweiten Prozedur aus, wie ein gekippter binärer Baum (d.h. wie um 90° gedreht).





3.3 Löschen



Löschen ist der schwierigste Bereich bei den binären Bäumen. Aus diesem Grund muß eine Hilfsvariable verwendet werden, welche dem anderen Pointer immer um einen Knoten hinten nach ist.





void löschen (struct knoten *akt, int x);

{

struct knoten *hilfe;

if (akt != NULL)

{

if (akt => zahl != x)

{

if (akt => zahl > x)

{

hilf = akt;

löschen (akt => links, x);

}

else

if (akt => zahl < x)

{

hilf = akt;

löschen (akt => rechts, x);

}

}

else

{

if (hilf => rechts == akt)













{

if (akt => rechts != NULL)

{

hilf => rechts = akt => rechts;

hilf = hilf => rechts;

for (hilf = hilf; hilf => links != NULL; hilf = hilf => links);

hilf => links = akt => links;

}

else hilf => rechts = akt => links;

free (akt);

}

else if (hilf =>links == akt)

{

if ( akt=>links != NULL)

{

hilf => links = akt => links;

hilf = hilf => links;

for (hilf = hilf; hilf => rechts != NULL; hilf = hilf => rechts);

hilf => rechts = akt => rechts;

}

else hilf => links = akt => rechts;

free (akt);

}

else free (akt);

}

}

}





3.4 Tiefe berechnen



Die folgende Funktion liefert als Retourwert die Tiefe eines binären Baumes. An die Funktion muß beim Aufruf bloß die Wurzel als Parameter übergeben werden.





int tiefe (ptr *akt);

{

int tl, tr;

if (akt = = NULL) return (0)

else

{

tl=tiefe (akt => links);

tr=tiefe (akt => rechts);

if (tl > tr ) return (tl + 1)

else return (tr + 1);

}

}

4. Sonstige Verwendungsmöglichkeiten für binäre Bäume



Ein binärer Baum kann auch dazu verwendet werden, um dyadische Operatoren darzustellen.

Dies könnte im folgenden so aussehen:



(a + b / c) * (d - e * f)


Es gibt 3 Bearbeitungsarten:


1. PRÄFIX: root before node

z.B.: * + a / b c - d * e f



2. INFIX: subtree root subtree

z.B.: a + b / c * d - e * f



3.POSTFIX: subtrees before root

z.B.: a b c / + d e f * - *









Quelle:




ähnliche Referate 



Hier könnt Ihr die DRUCKANSICHT für das Referat öffnen




Tipp:







(c) schulnote.de 2004-2018

MEDIADATEN --- Besucher seit dem 01.09.2006
gesamt: 6726442 - heute: 1102 - gestern: 1082 - online: 7 - Rekord online: 340 - Rekord Tag: 2801


ID: 5698      Aufrufe seit dem 02.08.2011: 2599