H
habkeinen
Gast
Java:
package aufgabenblatt3_aufgabe_35;
/**
* Knoten eines binären Baums mit einem int-Wert als "Nutzinformation"
*/
public class TreeNode {
public TreeNode left;
public int info;
public TreeNode right;
/** erzeugt Knoten mit angegebenem Wert und linkem sowie rechtem
* Teilbaum
*/
public TreeNode(int v, TreeNode l, TreeNode r) {
info = v;
left = l;
right = r;
}
/** erzeugt Blatt mit angegebenem Wert */
public TreeNode(int v) {
info = v;
left = null;
right = null;
}
public boolean istBlatt() {
return left == null && right == null;
}
}
Java:
package aufgabenblatt3_aufgabe_35;
import java.util.*;
/**
* Implementierung eines binären Suchbaums
* (Methoden siehe Aufgabenblatt sind noch zu ergänzen)
*/
public class SearchTree {
private TreeNode root;
/** Konstruktor erzeugt leeren Baum */
public SearchTree() {
root = null;
}
/** Berechnet die Höhe eines Baums */
public int height() {
return height(root);
}
private static int height(TreeNode r) {
if (r == null)
return 0;
else
return 1 + Math.max(height(r.left), height(r.right));
}
/**
* fügt neuen Knoten mit Wert v (falls v noch nicht vorhanden) in den Baum
* ein
*/
public boolean insert(int v) {
if (root == null) {
root = new TreeNode(v);
return true; // erfolgreich eingefügt
} else {
return insertRek(root, v);
}
}
private boolean insertRek(TreeNode r, int v) {
if (v < r.info) {
if (r.left == null) {
r.left = new TreeNode(v);
return true;
} else {
return insertRek(r.left, v);
}
} else if (v > r.info) {
if (r.right == null) {
r.right = new TreeNode(v);
return true;
} else {
return insertRek(r.right, v);
}
} else
// (v == r.info)
return false; // Wert war bereits vorhanden
}
/**
* sucht im Baum nach dem Knoten mit dem Wert v
*
* @return Referenz auf Knoten, falls Suche erfolgreich und null-Referenz
* sonst
*/
public TreeNode searchNode(int v) {
TreeNode current = root;
while (current != null) {
if (v < current.info)
current = current.left; // im linken Teilbaum weitersuchen
else if (v > current.info)
current = current.right; // im rechten Teilbaum weitersuchen
else // if (v == current.value)
return current; // Knoten mit Wert gefunden
}
return null; // Wert nicht gefunden
}
/** Gibt den Baum "liegend" aus */
public void print() {
if (root != null) {
print(root.left, " ", true);
System.out.println("+---" + root.info);
print(root.right, " ", false);
}
}
public void print(TreeNode r, String prefix, boolean links) {
if (r != null) {
if (links)
print(r.left, prefix + " ", links);
else
print(r.left, prefix + "| ", !links);
System.out.println(prefix + "+---" + r.info);
if (links)
print(r.right, prefix + "| ", !links);
else
print(r.right, prefix + " ", links);
}
}
//====================================================================//
// hier sind die Methoden zu ergänzen
//====================================================================//
/** Bestimmt die Anzahl der Werte, die im Baum gespeichert sind.
* (= Anzahl der Knoten im Baum) */
public int size() {
a=root.info;
TreeNode b =root.left;
int c=1;
if(root.left!=null){
c+=size();
}
if(root.right != null){
c+=size();
}
return c;
}
/*int links=0;
int rechts=0;
int size=1;
TreeNode a = root.left;
TreeNode b =root.right;
while(links<a.info){
links++;
}
while(rechts<b.info){
rechts++;
}
size=links+rechts;
return size;
*/
/*
if(root == null){
return 0;
}else{
int anzahl =1;
while(anzahl<a.info){
anzahl++;
//return anzahl;
}
return anzahl;
*/
/*
int i;
for(anzahl=1;anzahl<a.info;anzahl++){
if(a.right==null){
anzahl=anzahl+0;
}else{
anzahl++;;
}
if(a.left==null){
anzahl=anzahl+0;
}else{
anzahl++;
}
return anzahl;
}
// return 0;
*/
//}
//}
/** Bestimmt die Summe aller Werte, die im Baum gespeichert sind. */
public int sum() {
return 0;
}
public ArrayList<Integer> toList() {
return null;
}
public void toList(TreeNode t, ArrayList<Integer> result) {
}
/**
* Bestimmt den Knoten mit dem kleinsten Wert. Liefert 'null', falls Baum
* gar keine Knoten enthält.
*/
public TreeNode minNode() {
return root;
}
/**
* Fügt iterativ (!) einen neuen Knoten mit Wert v (falls v noch nicht
* enthalten ist) in den Baum ein. Liefert false, falls Wert schon im Baum
* enthalten war und sonst true.
*/
public boolean insertIter(int v) {
return false;
}
/** prüft, ob der andere Baum die gleiche Menge von Elementen enthält */
public boolean equals(SearchTree other) {
return false;
}
}bei public int size{...}
da sollen wir die anzhal knoten zählen im baum
mir geht es hier auch net um die lösung das ihr das für mich macht,
aber ich komm da partout nicht weiter und morgen ist abgabe.
kann mir da jemand helfen=
