i-kleinstes Element in Suchbäumen finden

Y

Yannik0103

Mitglied
Hi, ich bin leider ziemlicher Anfänger im Programmieren und habe Probleme mit einer Aufgabe. Ich soll 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. 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?
 
K

kneitzel

Gast
Also ein Knoten soll bei Dir folgend Dinge "wissen":
- einen Wert
- einen linken und einen rechten Knoten, wobei der eine Teilbaum nur kleinere und der andere Teilbaum nur größere Werte hat.
- Wie viele Kinder der Knoten besitzt.

Nun mal dir einfach einmal einen solchen Baum auf und überleg, wie du zu einem vorgegebenen Element (z.B. 3. kleinster Wert) kommen kannst.

Du kannst Dir dabei überlegen:
Du schaust Dir einen Knoten an und kennst dann die Anzahl der Kinder des Knotens. Und da Du die Child-Knoten kennst, kennst Du auch die Anzahl deren Kinder.

Du kannst das einmal durchspielen und zwar mit mehreren Bäumen:
a) einem Ausbalanzierten Baum.
b) einem Baum der nur nach rechts geht.
c) einem Baum, der nur nach links geht.

(b + c erstellst Du, indem Du aufsteigende / absteigende Zahlenfolgen einfügst)


=> Schau dir einfach einmal selbst an, welches z.B. der 3. kleinste Wert ist und dann schau, ob Du irgendwelche Regeln erkennen kannst für die Entscheidungen:
a) Ja, dieser Node enthält den dritt-Kleinste Wert.
b) wieso musste ich bei den Nodes von diesem Node bis zur Wurzel jeweils den entsprechenden Child-Node wählen?
 
Y

Yannik0103

Mitglied
Java: 
public class {// 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 mein bisheriger Ansatz, das meiste war mit ein paar anderen Methoden zur Implementierung von Suchbäumen schon vorgegeben, ich habe size und select implementiert, allerdings wird mir bei select angezeigt, dass die Methode keinen Suchbaum zurückgibt, aber ich gebe doch den Baum mit der Wurzel, die ich gerade betrachte zurück oder nicht?
 
Zuletzt bearbeitet von einem Moderator:
mrBrown

mrBrown

Super-Moderator
Mitarbeiter
Hier gibst du "T" zurück, was auch immer "T" ist:
if (left.wurzel.size + 2 == i) return T;


Außerdem gibst du nur innerhalb eines ifs etwas zurück, du musst aber auch im Fall, dass keins der if's wahr ist, was zurückgeben.
 
Y

Yannik0103

Mitglied
Java: 
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;
}
}



}

Das ist der komplette Code, T ist der Suchbaum der eingelesen wurde auf den ich select anwende, bei den darauf folgenden Aufrufen von select würde dann doch der linke bzw rechte Teilbaum auf den ich select anwende zurückgegeben werden oder?
Ok, es fehlen noch die Fälle in denen kein linker bzw rechter Teilbaum existiert oder?[/I][/code]
 
Zuletzt bearbeitet von einem Moderator:
mrBrown

mrBrown

Super-Moderator
Mitarbeiter
Bitte Code-Tags benutzen ([code=java]//code...[/code]) und den Code wenn möglich sinnvoll einrücken
 
mrBrown

mrBrown

Super-Moderator
Mitarbeiter
Du solltest in dem gesamten Code keine statischen Variablen benutzen, die brauchst du dort nicht und die machen es nur komplizierter.

Der Grund für den Fehler steht weiter oben schon
 
Y

Yannik0103

Mitglied
Der Code ist schon von der Aufgabenstellung vorgegeben und wir dürfen nur select implementieren, size für jeden Knoten definieren und in insert size verändern, wie könnte ich dieses Problem umgehen, wenn ich nichts anderes verändern darf?
 
Y

Yannik0103

Mitglied
Wenn mein Ansatz richtig ist müsste select bei Gleichheit den Suchbaum auf den select momentan angewandt wird. Aber wie kann ich diesen zurückgeben? Der erste Aufruf von select erfolgt doch mit T.select(i) und diese Variable ist doch statisch
Ich hab die Fälle < = und > also fehlen doch nur noch die Fälle, dass kein linker Teilbaum vorhanden ist und mein Teilbaum den ich gerade betrachte der richtige ist oder dass i größer als die Anzahl der Elemente im Baum ist oder? Das sind die einzigen 5 Fälle, die mir einfallen
 
mrBrown

mrBrown

Super-Moderator
Mitarbeiter
Yannik0103 hat gesagt.:
Wenn mein Ansatz richtig ist müsste select bei Gleichheit den Suchbaum auf den select momentan angewandt wird. Aber wie kann ich diesen zurückgeben? Der erste Aufruf von select erfolgt doch mit T.select(i) und diese Variable ist doch statisch
Zum Vergrößern anklicken....
Kennst du this?

Yannik0103 hat gesagt.:
Ich hab die Fälle < = und > also fehlen doch nur noch die Fälle, dass kein linker Teilbaum vorhanden ist und mein Teilbaum den ich gerade betrachte der richtige ist oder dass i größer als die Anzahl der Elemente im Baum ist oder? Das sind die einzigen 5 Fälle, die mir einfallen
Zum Vergrößern anklicken....
Ja, aber in jedem Fall wirst du einen Zweig ohne Bedingung brauchen, damit der Compiler sicherstellen kann, dass immer etwas zurückgegeben wird.
 
Y

Yannik0103

Mitglied
Also anstatt return T return this?
Ok ich muss also die Fälle <, =, >, i>Anzahl der Elemente in T, es existiert kein linker Teilbaum und mein Element ist das richtige, es existiert kein linker Teilbaum und mein Element ist im rechten Teilbaum und einen Fall ohne Bedingung implementieren?
 
Y

Yannik0103

Mitglied
(
Java: 
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 this;
           else {
               if (left.wurzel.size + 2 < i) return this.right.select(i - this.left.wurzel.size - 2);
               if (left.wurzel.size + 2 > i) return this.left.select(i);
               if (this.left.wurzel == null && i == 1) return this;
               if (this.left.wurzel == null && i > 1) return this.right.select(i - 1);
                
           }
        return new Suchbaum();
       }
)
Das wäre meine Idee
 

Aktuelle Jobs

Neue Themen


Oben