 Suchbaum |
yannik0103
Grünschnabel
Dabei seit: 04.06.2019
Beiträge: 6
 |
|
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?
|
|
04.06.2019 17:07 |
|
|
as_string 
Haudegen
Dabei seit: 06.11.2013
Beiträge: 639
Herkunft: Heidelberg
|
|
Ich bin mir nicht sicher, ob ich die Aufgabenstellung komplett richtig verstehe. Könntest Du nochmal den kompletten Aufgabentext im Wortlaut rein stellen? Ist das dann ein binärer Suchbaum?
Also ich stelle es mir so vor: Jeder Knoten im Baum merkt sich die Anzahl aller seiner Kinder (und Kindes-Kinder, etc) im Baum. Das könnte man ja relativ einfach realisieren, indem man beim Einfügen im Suchbaum einfach bei jedem Knoten, den man auf dem Weg von Wurzel bis Blatt "trifft", einen Zähler hoch zählt.
Wenn ich jetzt die Aufgabe lösen sollte, würde ich mir die Wurzel erst anschauen. Angenommen, ich soll den 50ten Knoten finden und im Baum sind 100 Elemente. Dann hätten die Kindknoten meines Wurzelknotens vielleicht einmal 43 Kinder und der andere dann 56 Kinder (ein Wert hält die Wurzel selbst ja schon). Also weiß ich, dass der 50te sicher in dem rechten Teilkbaum drin sein muss, der 56 Kinder hat.
Dann kann ich auf der nächsten Ebene weiter suchen, suche jetzt aber den 50-43-1 = 6ten Knoten, weil der 50te im gesamten Baum ja dann der sechste im rechten Teilbaum sein muss, wenn im linken Teilbaum schon 43 drin sind und noch einer mit der Wurzel weg ist. In dem rechten Teilbaum hat das eine Kind vielleicht 20 und das andere dann 35 Kinder. Weil 6 <= 20 gehts im linken weiter usw.
Gruß
Marco
|
|
|
04.06.2019 17:34 |
|
|
yannik0103
Grünschnabel
Dabei seit: 04.06.2019
Beiträge: 6
|
|
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?
|
|
|
04.06.2019 18:20 |
|
|
yannik0103
Grünschnabel
Dabei seit: 04.06.2019
Beiträge: 6
|
|
| 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
|
|
|
04.06.2019 18:22 |
|
|
as_string
Haudegen
Dabei seit: 06.11.2013
Beiträge: 639
Herkunft: Heidelberg
|
|
Hallo!
Vom Prinzip her sieht das ja schon gar nicht so schlecht aus, allerdings:
Mir fällt auf den ersten Blick ein Problem in den letzen beiden if-Zeilen auf: Du hast da ja jeweils zwei Anweisungen, nämlich das Erhöhen der size und das Einfügen in den jeweiligen Teilbaum. Wenn Du bei einem if einen Anweisungsblock mit mehreren Anweisungen (hier 2) hast, dann musst Du eine geschweifte Klammer um die beiden Anweisungen machen. Da hilft es auch nicht, wenn beide Anweisungen auf einer Zeile stehen, das spielt so wie so keine große Rolle, was auf einer Zeile steht oder nicht.
Probier doch mal, ob Du mit den Hinweisen, die ich in meinem ersten Post geschrieben hatte, schon irgendwie weiter kommst.
Gruß
Marco
|
|
|
05.06.2019 10:58 |
|
|
yannik0103
Grünschnabel
Dabei seit: 04.06.2019
Beiträge: 6
|
|
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?
|
|
|
05.06.2019 11:11 |
|
|
yannik0103
Grünschnabel
Dabei seit: 04.06.2019
Beiträge: 6
|
|
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.
|
|
|
06.06.2019 09:36 |
|
|
|
