| Zeige Beiträge 1 bis 6 von 6 Treffern |
|
 Thema: Suchbaum |
|
|
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.Arrays;
public class Suchbaeume {
static class Suchbaum {
private Knoten wurzel;
private Suchbaum left;
private Suchbaum right;
private class Knoten{
public int key;
public int size;
public Knoten(int x){
key = x;
size = 0;
}
}
public Suchbaum select(int i){
if (left.wurzel.size + 2 == i) return T;
else {
if (left.wurzel.size + 2 < i) return right.select(i - left.wurzel.size - 2);
if (left.wurzel.size + 2 > i) return left.select(i);
}
}
public void insert(int x){
if (wurzel==null) {
wurzel = new Knoten(x);
left = new Suchbaum();
right = new Suchbaum();
}
else {
if (wurzel.key > x){
left.insert(x);
wurzel.size++;
}
if (wurzel.key < x){
right.insert(x);
wurzel.size++;
}
}
}
public Suchbaum(){
wurzel = null;
left = null;
right = null;
}
public String toString()
return toStringRec(0);
}
private String toStringRec(int i){
char[] spaces = new char[i];
Arrays.fill(spaces,'\t');
String platz = new String(spaces);
if (wurzel==null) return platz+"[]";
else return right.toStringRec(i+1)+"\n"+platz+"["+Integer.toString(wurzel.key)+"]"+"\n"
+left.toStringRec(i+1);
}
}
static Suchbaum T;
static int i;
public static void main(String[] args) {
String vorname1, nachname1, matrikelnr1, vorname2, nachname2, matrikelnr2, vorname3, nachname3, matrikelnr3;
vorname1 = "";
nachname1 = "";
matrikelnr1 = "";
vorname2 = "";
nachname2 = "";
matrikelnr2 = "";
vorname3 = "";
nachname3 = "";
matrikelnr3 = "";
file_name = args[0];
T = new Suchbaum();
i = 0;
inputEinlesen();
System.out.println("Baum nach Eingabe aller Zahlen:");
System.out.println(T.toString());
System.out.println("Der Baum, dessen Wurzel das "+i+"-te Element ist:");
System.out.println(T.select(i).toString());
System.out.println(vorname1+" "+nachname1+";"+matrikelnr1+";"+vorname2+" "+nachname2+";"+matrikelnr2+";"+vorname3+" "+nachname3+";"+matrikelnr3);
}
static String file_name;
static void inputEinlesen(){
Scanner input;
String zeile;
// Initialisierung:
input = null;
zeile = "";
// Datei input.txt einlesen:
try
{
input = new Scanner(new File(file_name));
}
catch(FileNotFoundException e)
{
System.out.println("Input-Datei nicht gefunden.");
return;
}
if(input.hasNextLine())
zeile = input.nextLine();
String[] zahlenliste = zeile.split(" ");
for (String str : zahlenliste)
{
try
{
T.insert(Integer.parseInt(str));
}
catch (NumberFormatException e)
{
System.out.println("Erste Zeile enthaelt nicht nur Zahlen.");
return;
}
}
if(input.hasNextLine())
zeile = input.nextLine();
try
{
i = Integer.parseInt(zeile);
}
catch (NumberFormatException e)
{
System.out.println("Zweite Zeile enthaelt nicht nur eine Zahl.");
return;
}
}
}
So sieht das ganze Programm mit der Implementierung und dem Einlesen der Suchbäume aus. Ich muss leider heute Abend schon abgeben.
|
|
| Thema: Suchbaum |
|
|
public class Suchbaeume {// Hier muessen Sie den Klassennamen anpassen.
/*
*
Beginn der Definition der Unterklasse "Suchbaum"
*
*/
static class Suchbaum {
/*
In dieser Klasse sollten Sie an drei Stellen Aenderungen vornehmen:
2) Die Methode "select" fuellen.
3) Dafuer die Definition der Klasse "Knoten" anpassen.
4) Und die Methode "insert" anpassen.
*/
private Knoten wurzel;
private Suchbaum left;
private Suchbaum right;
private class Knoten{
public int key;
public int size;
public Knoten(int x){
key = x;
size = 0;
}
}
public Suchbaum select(int i){
//Diese Prozedur sollen Sie fuellen. Dafuer sollte zudem die Definition von Knoten um den parameter "size" erweitert werden und die Methode "insert" angepasst werden.
if (left.wurzel.size + 2 == i) return T;
else {
if (left.wurzel.size + 2 < i) return right.select(i - left.wurzel.size - 2);
if (left.wurzel.size + 2 > i) return left.select(i);
}
}
public void insert(int x){
//x in Baum einfuegen
if (wurzel==null) {
wurzel = new Knoten(x);
left = new Suchbaum();
right = new Suchbaum();
}
else {
if (wurzel.key > x) {
left.insert(x);
wurzel.size++;
}
if (wurzel.key < x) {
right.insert(x);
wurzel.size++;
}
}
}
}
Das ist bis jetzt mein komplettes Programm
|
|
| Thema: Suchbaum |
|
|
public Suchbaum select(int i){
//Diese Prozedur sollen Sie fuellen. Dafuer sollte zudem die Definition von Knoten um den parameter "size" erweitert werden und die Methode "insert" angepasst werden.
if (left.wurzel.size + 2 == i) return T;
else {
if (left.wurzel.size + 2 < i) return right.select(i - left.wurzel.size - 2);
if (left.wurzel.size + 2 > i) return left.select(i);
}
}
Das ist meine bisherige Lösung von select, allerdings wird mir angezeigt, dass die Methode keinen Suchbaum ausgibt, obwohl ich doch eigentlich den jeweiligen Suchbaum mit der Wurzel, die ich gerade betrachte zurückgebe oder nicht?
|
|
| Thema: Suchbaum |
|
|
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
|
private Knoten wurzel;
private Suchbaum left;
private Suchbaum right;
private class Knoten{
public int key;
public int size;
public Knoten(int x){
key = x;
size = 0;
}
}
public void insert(int x){
//x in Baum einfuegen
if (wurzel==null) {
wurzel = new Knoten(x);
left = new Suchbaum();
right = new Suchbaum();
}
else {
if (wurzel.key > x) wurzel.size++; left.insert(x);
if (wurzel.key < x) wurzel.size++; right.insert(x);
}
} |
|
So sieht mein Code bis jetzt aus
|
|
| Thema: Suchbaum |
|
|
Erweitern Sie die gegebene Implentierung von Suchbaumen um die zusätzliche Operation select:
Diese erhält eine Zahl i und gibt den Teilbaum zuruck, dessen Wurzel das i-kleinste Element im Suchbaum ist (oder einen leeren Suchbaum, falls i zu groß oder zu klein ist). Dafur enthält jeder Knoten x die zusätzliche Information x.size, die Anzahl der Knoten im Baum mit Wurzel x.
Also bis jetzt habe ich für jeden Knoten x.size=0 gesetzt und in der insert Methode size von der Wurzel mit der x verglichen wird um 1 erhöht.
Danke das hilft mir schon mal sehr. Ich müsste also in jedem Aufruf von select schauen, ob mein Element das richtige ist und wenn es falsch ist, select auf den linken bzw rechten Teilbaum anwenden und den Parameter i anpassen?
|
|
| Thema: Suchbaum |
|
|
Meine Frage:
Hi, ich bin leider ziemlicher Anfänger im Programmieren und habe Probleme mit einer Aufgabe. Ich soll in Java eine Methode implementieren, die den Teilbaum eines Suchbaums zurückgibt, dessen Wurzel das i-kleinste Element im Suchbaum ist. Die Aufgabenstellung verlangt, dass wir die Aufgabe mit der Information, wie viele Kinder jeder Knoten x besitzt, lösen.
Meine Ideen:
Ich habe also für jeden Knoten x einen Integer x.size implementiert, der der Anzahl der Kinder von x entspricht. Nun weiß ich allerdings nicht, wie ich mit dieser Information einen Algorithmus entwerfen und diesen dann implementieren soll. Mein Plan ist es an der Wurzel vom Suchbaum T anzufangen und zu überprüfen, ob die Wurzel kleiner oder größer als das i-kleinste Element ist und dann mit dem linken bzw rechten Teilbaum weiterzumachen, aber ich finde keine Möglichkeit wie man für einen allgemeinen Knoten x bestimmen kann, der wie vielt kleinste er ist. Hat jemand eine Idee?
|
|
|
| Zeige Beiträge 1 bis 6 von 6 Treffern |
|
|
|
