package algo;
//package blatt4;
import java.util.LinkedList;
import java.util.List;
import java.util.Arrays;
/**
* BaumLsg repr�sentiert einen Baum. Der Baum ist leer oder enth�lt
* lediglich einen Verweis auf seinen (einzigen) Wurzelknoten.
* Die ganzen anderen Knoten h�ngen als Nachfolgerknoten direkt
* oder indirekt an diesem Wurzelknoten.
* Die Struktur der Knoten ist in der inneren Klasse Knoten festgelegt.
*
* @author Belenus666
*
*/
public class Baum {
static int x = 0;
Knoten wurzel = null;
/**
* erzeugt einen leeren Baum ohne Wurzel
*/
Baum() {
}
/**
* erzeugt einen Baum, der nur die Wurzel enth�lt
* @param label stellt die Nutzlast der Wurzel dar
*/
Baum(Object label){
wurzel = new Knoten(label);
}
/**
* erzeugt einen Baum aus beliebig vielen Unterb�umen
* @param label stellt die Nutzlast der neuen Wurzel dar
* @param b ist das array der zusammenzuf�genden B�ume
*/
Baum(Object label, Baum... b) {
wurzel = new Knoten(label);
/* neue erweiterte for-Schleife seit Java 5.0
* siehe Javabuch unter for-Schleife (erweiterte)
*/
for (Baum bb : b) {
wurzel.list.add(bb.wurzel);
x++;
}
}
/**
* berechnet die H�he des Baumes als die H�he seiner Wurzel.
* Ist der Baum leer ist das Ergebnis 0.
* @return H�he des Baumes
*/
public int hoehe(){
if (wurzel == null) {
return 0;
} else
return wurzel.hoehe();
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
public String toString() {
if (wurzel == null) {
return "<Baum>\n</Baum>\n";
} else {
return "<Baum>\n" + wurzel.toStringRek("") + "</Baum>\n";
}
}
/**
* Repr�sentiert einen Knoten eines Baumes.
*/
private class Knoten {
/**
* wird f�r die formatierte rekursive Darstellung verwendet.
*/
static final String prefix = "--";
/**
* Nutzlast des Knoten
*/
Object label;
/**
* Liste aller Nachfolgerknoten
*/
List<Knoten> list;
/**
* erzeugt einen Knoten mit Nutzlast und leerer Nachfolgerliste
* @param label Nutzlast des Knoten
*/
Knoten(Object label) {
this.setLabel(label);
list = new LinkedList<Knoten>();
}
/**
* erzeugt einen Knoten mit Nutzlast und Nachfolgerliste
* @param label Nutzlast des Knoten
* @param k array der Nachfolgerknoten
*/
Knoten(Object label, Knoten... k) {
this(label);
/* neue erweiterte for-Schleife seit Java 5.0
* siehe Javabuch unter for-Schleife (erweiterte)
*/
for (Knoten kk: k) {
list.add(kk);
x++;
}
}
/**
* setzt die Nutzlast des Knoten
* @param label Nutzlast
*/
void setLabel(Object label) {
this.label = label;
}
/**
* @return Nutzlast des Knoten
*/
Object getLabel() {
return label;
}
/**
* @return Hoehe des Knoten
*/
public int hoehe(){
throw new UnsupportedOperationException();
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
public String toString() {
return getLabel().toString();
}
/**
* erzeugt rekursiv eine Stringrepr�sentation des Knoten
* und aller seiner Nachfolger.
*
* @param s = "" bei direktem Aufruf durch toStringRek()
* @return
*/
private String toStringRek(String s) { //preorder!!
String res = s + getLabel().toString() + "\n";
int v = 0;
for (Knoten k: list) {
res += k.toStringRek(s + prefix);
v++;
}
return res+v;
}
/**
* erzeugt rekursiv eine Stringrepr�sentation des Knoten
* und aller seiner Nachfolger.
* @return Stringrepr�sentation des Knoten
*/
public String toStringRek() {
return toStringRek("");
}
} // class Knoten
/**
* Erzeugung und Ausgabe von Beispielb�umen
*/
public static void main(String[] args) {
Baum b;
b = new Baum("Buch"
,new Baum("K1"
,new Baum("K1.1")
,new Baum("K1.2")
,new Baum("K1.3")
)
,new Baum("K2")
,new Baum("K3"
,new Baum("K3.1"
,new Baum("K3.1.1")
,new Baum("K3.1.2")
),new Baum("K3.2"
)
));
System.out.println(b);
}
// main()
} // class Baum
Das Programm hab ich soweit fertig was ich nicht hin bekomme ist die rekursive Methode höhe die die Höhe des Erzeugten Baumes ausgibt.
Wäre klasse wenn mir jmd von euch helfen könnte.
Grüße
Belenus
mir ist nur etwas ziemlich umständliches eingefallen.
Aber es scheint zu tun.
Hier die Höhe von dem Knoten. Hab es mit einem Array gemacht, da ja geguckt werden muss welcher Knoten die am höchsten ist.
Code:
public int hoehe(){
lengh = new int[list.size()];
int max;
max = 0;
if(list == null){
return 1;}
else {
int i=0;
int count = 0;
for (Knoten s : list) {
i = i + s.hoehe() + 1;
lengh[count] = i;
count++;
i = 0;
}
for(int t=0; t < lengh.length; t++)
{
if (lengh[t]> max){
max = lengh[t];
}
}
return max;
}
}
Und die Wurzel benötigt ein
Code:
public int hoehe(){
public int hoehe(){
if (wurzel == null) {
return 1;
} else
return wurzel.hoehe() + 1;
// +1 für die Wurzel
}
}
Ich bin mir sicher das ging auch irgendwie einfacherer. Ich schau ob ich die Unterlagen noch finden kann, ist schon eine Weile her das wir das in Info hatten (~1 Jahr).
//edit:
Code:
private int maxDepth(final int depth, final Node node) {
if( node != null ) {
return Math.max( // Der tiefere Zweig zählt
maxDepth(depth+1, node.left), // Links absteigen
maxDepth(depth+1, node.right) // Rechts absteigen
);
}
return depth;
}
Quelle: Google. So gehts eleganter Node ist halt ein Knoten.
im Baum:
int getHoehe(){
if(wurzel!=null) return wurzel.getHoehe();
return 0;
}
im Knoten:
int getHoehe(){
return this.getHoehe(1);
}
int getHoehe(int aktuelleHoehe){
int max=aktuelleHoehe;
int i;
for(Knoten k:list){
i=k.getHoehe(aktuelleHoehe+1);
if(i>max)max=i;
}
return max;
}
so sollte es gehen
-man kann natuerlich direkt im Knoten mit 1 aufrufen und die leere Methode weglassen
-i ist eigendlich ueberfluessig, da Java die Ergebnisse eh zwischenspeichert
-ich finde das so halt schoener
list als Name fuer die Liste der Nachfolgerknoten ist unschoen
public,private,protected,default musste dir selber aussuchen
[JAVA] allgemeiner unsortierter Baum Problem
Node ist halt ein Knoten.
Hybrid-Darstellung
