Elementare Graphenalgorithmen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Geben Sie eine Adjazenzlisten-Darstellung für einen vollständigen binären Baum mit sieben Knoten an. Geben Sie eine äquivalente Adjazenzmatrix-Darstellung an. Nehmen Sie an, dass die Knoten wie in einem binären Heap von 1 bis 7 nummeriert sind. |
Hallo, habe leider keinen Ansatz bei dieser Aufgabe und würde mich deswegen über Tipps freuen.
Hauptsächlich habe ich schwierigkeiten diese Aufgabenstellung zuverstehen. Wie ist das gemeint "Nehmen Sie an, dass die Knoten wie in einem binären Heap von 1 bis 7 nummeriert sind" also sollte man hier ein MaxHeap aus Zahlen 1,2,3,4,5,6,7 bauen und dann mit dieser Reihenfolge eine Adjazenzlisten-Darstellung und Adjazenzmatrix-Darstellung angeben?
gruß
|
|
| |
|
Hallo!
Folgende Nummerierung wäre in dem Binärbaum denkbar (Min-Heap):
1
/ \
2 3
/ \ / \
4 5 6 7
Adjazentliste (Verbindungen zu Nachbarknoten) für ungerichtete Kanten:
1: {2,3}
2: {1,4,5}
3: {1,6,7}
4: {2}
5: {2}
6: {3}
7: {3}
Adjazenzmatrix für ungerichtete Kanten:
| 1 2 3 4 5 6 7
--------------------
1 | 0 1 1 0 0 0 0
2 | 1 0 0 1 1 0 0
3 | 1 0 0 0 0 1 1
4 | 0 1 0 0 0 0 0
5 | 0 1 0 0 0 0 0
6 | 0 0 1 0 0 0 0
7 | 0 0 1 0 0 0 0
Bei weiteren Aufgaben kann vielleicht dieses kleine Programm helfen. Ich habe es während des Mathe-Semesters geschrieben um Aufgaben überprüfen zu können.
http://web318.server168.star-server.info/node/141
MfG
Wolfgang
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:24 Sa 17.07.2010 | | Autor: | capablanca |
Danke für die Ausführliche Erklärung!
Gruß
|
|
|
|
