✔ Quad-Bäume

[fraMewOoD]

Guten morgen,

Wir sollen in einer Hausaufgabe einen Quadbaum mit 2^n*2^n Elementen erstellen, das ganze in einem 2-dimensionalen Array (mit Zahlen).
Der Wurzelknoten des Baumes repräsentiert das gesamte Array, ein Knoten "k" eines Quad-Baumes hat entweder keine oder genau vier Kinder-Knoten, die das obere linke Viertel, das obere rechte Viertel, das untere linke Viertel sowie das untere rechte Viertel des durch "k" beschriebenen Array repräsentiert. Die eigentlichen Werte v sollen in den Blättern des Baumes stehen. Ist einem Blatt die Große s' und der Wert v' zugeordnet, so repräsentiert es ein 2-dimensionales Array der Größe s'.s' in dem jeder Zelle der Wert v' steht.
Sobald der User ein "n" (> 0) spezifiziert, wird der gesamte baum kosntruiert, in einem durchmarsch und man soll nichts mehr hinzufügen oder entfernen können.
n fungiert ja als potenz von 2, also => 2^n * 2^n, wobei jeder der beiden werte spalte bzw. zeilenanzahl repräsentiert und die anzahl der felder wird durch das produkt der beiden errechnet (klar, eben ein 2-dimensionales Array)

Das sieht für n = 2 in etwa so aus:

Wurzel-Knoten :  

| 2 | 2 |
| 2 | 2 |

wobei die '2' einfach nur der Baum-wert ist, also v
und s beschreibt die Baumgröße, in diesem Falle die zeilen & spaltenanzahl, also 2 spalten und zwei zeilen
In einem QuadBaum gebilde sähe es so aus:

     ___________________| s = 2| ____________________ 
   /                         |                                 |                               \
| s = 1 |              | s = 1 |                       | s = 1 |                      | s = 1 |
|v = 2 |               |v = 2 |                       |v = 2 |                       |v = 2 |

So, wir hatten leider in der Vorlesung keine Bäume, weder Binär noch quad noch irgendwas, also habe
ich mal den Deitel (Java how to programm) gewälzt und mir dort die binär-baume angeschaut - mit mäßigem Erfolg.

Also was mir bisher klar ist:

Wir brauchen eine Klasse "Tree", welche den root erzeugt, der root gehört der Klasse "Knoten" an und muss eine Referenz auf seine folgenden Unter-Knoten erhalten, in diesem Falle wären das vier referenzen, also links, linksmitte, rechtsMitte und rechts. wenn ein knoten objekt kreiert wird, wird natürlich auch der knoten konstruktor aufgerufen, mittels dem wir dann unsere links, rechts mitte usw. referenzen setzen

So, die Knoten selber haben eventuell auch wieder Knoten, das hängt von der anzahl der ebenen ab, beispiel: gäbe der User "1" ein, müssten wir nach dem root eine unterebene mit 4 knoten erstellen, da jeder knoten ja ein array feld repräsentiert und das wären bei n = 1 ja insgesamt nur 4 Array felder.

Gibt man hingegen n = 2 ein, dann hätte man bereits 16 Atrray felder, also 2 ebenen.
Die vier knoten der ersten ebene hätte wiederum jeweils vier unterknoten also so:

n = 1

__________________
| Knoten A | Knoten B |
|________ |________|
| Knoten C | Knoten D |
|________ |________|

n = 2 => man unterteilt A, B, C und D jeweils in 4 weitere unterknoten

__________________
|Knoten A1| KnotenA2|
|________ |________|
|Knoten A3|Knoten A4|
|________ |________|
|Knoten C1|Knoten C2|
|________ |________|
|Knoten C3|Knoten C4|
|________ |________|

So, also B und D hab ich mir mal gespart, die müsste man rechts da noch ranpappen, analog zu A und C

wie gesagt, heirmein bisheriger Code:

//Franzisca Woythal
//25.11.2006
//Aufgabe  27
//Matrikelnummer: 3054743

public class Tree
{
	public Knoten current;				//Das aktuelle Knotenobjekt
	private int ebenen;
	private Knoten root;				//Der root-Knoten
	
	//Knotenklasse
	private class Knoten				//		______________[root]_________    	      
	{							   //	         /		  |				|        \
		public Knoten links;			//            |links|  |linksMitte|  |rechtsMitte|  |rechts|
		public Knoten linksMitte;	     //              /||\	    /||\		   /||\		    /||\
		public Knoten rechtsMitte;	    //             [...]          [...]		         [...]	         [...]
		public Knoten rechts;
		public int wert;
		private int arraySize;
		//Konstruktor des Knotens		
		Knoten()
		{
//			root.links = null;
//			root.linksMitte = null;
//			root.rechtsMitte = null;
//			root.rechtsMitte = null;
//			arraySize = ;
			System.out.println("Knoten Konstruktor [] : ");		
		}
	}//End der Knotenklasse
	//Konstruktor übernimmt ein zwei-dimensionales Array
	Tree(int [][]arr)
	{
		Knoten root = new Knoten() ;	//erstellt den ersten Knoten
		//Errechnet Anzahl der Ebenen
		double ebeneCalc = arr.length;
		System.out.println("Tree Konstruktor [arr.length] : " + arr.length);
		ebeneCalc = Math.sqrt(ebeneCalc);
		int ebene = (int)ebeneCalc;
		System.out.println("Tree Konstruktor [Ebenen] : " + ebene);		

	}

}

Ich hoffe es gilt irgendwie als entschuldigung für meine unzulänglichen Fähigkeiten in Java, das ich es erst seit knapp nem Monat mache :-(

 

[fraMewOoD]

Also... ich seh schon, allzu viel Ideen habt iihr wohl auch nicht XD ...

 

[zeja]

Was daran liegen könnte dass du keine Frage gestellt hast.

 

[fraMewOoD]

Was daran liegen könnte dass du keine Frage gestellt hast.

Wow... du hast Recht - muss ich glatt vergessen haben .
Also, offiziellerweise meine Frage :

1.

Ist ein Quadbaum vom Grundaufbau her gleich zu einem Binaerbaum?
Also => root, left child, right child, middleleft child und middleright child?

2.

Der Baum muss ja in einem Satz konstruiert werden - man kann anschließend nichts mehr an dem Baum verändern/zufügen/löschen sondern nur suchen, also muss ich gleich vom Konstruktor aus eine iterative Funktion aufrufen, die die Ebenen des Baumes erstellt?

3.

Und sollte ich die Baumklasse mit Knoten-Objekten versehen oder sollte ich die Knoten klasse besser ganz weglassen und jeden Teilbaum (also jedes Kind ist ja wieder ein baum) als eigenen baum repräsentieren, also als neues tree-objekt?

Das wär erstmal ... Danke im Voraus für etwaige vorschläge

 

[Zarathutra]

Hallo,

Ich hab auch dieselbe Aufgabe,
ich denke das die Knoten sind selber auch Quadbaum (class Tree).
Das heißt du brauchst nicht eine separate Klasse dafür implementieren, sondern es müss genau wie das Code für einen Binärbaum sein, aber diesmal mit vier Refrenzen, anstat 2.

 

[fraMewOoD]

@zarathutra:

Hat sich erledigt , hatte es mit ein paar anderen zusammen gemacht, ja ungefähr wie du gesagt hast - war eigentlich gar net so schwer XD.

Gruss framewood