Frage zur einfügen in einem Binärbaum

Status
Nicht offen für weitere Antworten.

gustav-mega

Bekanntes Mitglied
Hallo,

ich habe das folgende Code:

Code:
class MMenge<T extends Comparable> 
{
  Node root = null;

  class Node<T extends Comparable>
  {
    T value;
    int indx = 1;
    Node left, right;

    public Node(T v)
    {
      value = v;
    }
  }

  void insert(T[] val)
  {
    boolean hilfe = true;
    for (int i = 0; i < val.length; i++)
    {
      if (root == null) 
      {
        root = new Node<T> (val[i]);
        return;
      }

      Node parent = null, child = root;

      while (child != null) 
      {
        parent = child;

        if (child.value.compareTo(val[i]) == 0) 
        {
          parent.indx += 1;
          hilfe = false;
          return;
        }

        if (child.value.compareTo(val[i]) < 0)
          child = child.left;
        else
          child = child.right;
      }

      if (parent.value.compareTo(val[i]) == 0 && hilfe) 
      {
        child.indx += 1;
        return;
      }

      if (parent.value.compareTo(val[i]) < 0 && hilfe)
        parent.left = new Node<T>(val[i]);

      else
        parent.right = new Node<T>(val[i]);
    }
  }
  
  int anzahl(MMenge<T> baum, T wert)
  {
    int ergebniss = -1;
    Node parent = root;
    while(parent != null)
    {
      if(parent.value.compareTo(wert) == 0)
      {
        ergebniss = parent.indx;
        return ergebniss;
      }
      if(parent.value.compareTo(wert) < 0)
        parent = parent.left;
      else
        parent = parent.right;
    }
    return ergebniss;
  }
  
  public static void main(String[] args)
  {
    MMenge<String> test = new MMenge<String>();
    String[] hallo = {"a","a","a","v","d","f","r"};
    test.insert(hallo);
    MMenge<String> test2 = new MMenge<String>();
    test2 = test;
    System.out.println(test.anzahl(test2, "a"));
  }
}
kann jemend vielleicht sagen, warum 1 als Ergebnis geliefert wird?

Gruß,
G.M.
 

bambi

Bekanntes Mitglied
initialisieren = wert zuweisen

sowas wie root = "irgendeinWert" // wobei "irgendeinWert" != null
 

bambi

Bekanntes Mitglied
also ich denke mal, dass root in deiner methode null ist und dass dann natuerlich auch parent = null ist, da du deine insert-methode ja gar nicht aufrufst, oder lieg' ich da jetzt falsch?

check einfach mal root, bevor du die zuweisung machst. wenns nicht null ist, dann sag' bescheid - ich schau dann noch mal genauer rein, okay?

und immer schoen :lol: okay?!?
 

gustav-mega

Bekanntes Mitglied
ich habe gerade mit dem Befehl getestet:
Code:
System.out.println(test.root != null);

und bekomme true, daher root kann nicht null sein!
 
B

Beni

Gast
Nur mal eine Frage: wie hast du das kompiliert? Eclipse streicht da viel rot an...

Das ist doch ein ideales Stück Code um einen Debugger auszuprobieren.
Nur so als Tipp: das Problem wird durch Zeile 25 verursacht :wink:
 

gustav-mega

Bekanntes Mitglied
Du must JDK 1.5 installiert haben, und ich habe es über Konsole kompiliert. Ich habe den Code jetzt soweit geändert:
Code:
class MMenge<T extends Comparable>
{
  Node root = null;

  class Node<T extends Comparable>
  {
    T value;
    int indx = 1;
    Node left, right;

    public Node(T v)
    {
      value = v;
    }
  }

  void insert(T[] val)
  {
    T element;
    for (int i = 0; i < val.length; i++)
    {
      element = val[i];
      
      Node parent = null, child = root;

      while (child != null)
      {
        parent = child;

        if (element.compareTo(child.value) == 0)
          child.indx += 1;

        if (element.compareTo(child.value) < 0)
          child = child.left;
        else
          child = child.right;
      }
      
      if (parent == null)
        root = new Node<T> (element);
      else
      {
        if (element.compareTo(parent.value) == 0)
          parent.indx += 1;
        
        if (element.compareTo(parent.value) < 0)
          parent.left = new Node<T>(element);

        else
          parent.right = new Node<T>(element);
      }
    }
  }

  int anzahl(MMenge<T> baum, T wert)
  {
    int ergebniss = -1;
    Node parent = root;
    while(parent != null)
    {
      if(parent.value.compareTo(wert) == 0)
      {
        ergebniss = parent.indx;
        //return ergebniss;
      }
      if(parent.value.compareTo(wert) < 0)
        parent = parent.left;
      else
        parent = parent.right;
    }
    return ergebniss;
  }

  public static void main(String[] args)
  {
    MMenge<String> test = new MMenge<String>();
    String[] hallo = {"a","a","a","a","v","d","f","r","a"};
    test.insert(hallo);
    MMenge<String> test2 = new MMenge<String>();
    test2 = test;
    System.out.println(test.root.right.right.value);
    System.out.println(test.anzahl(test, "f"));
  }
}
 
B

Beni

Gast
gustav-mega hat gesagt.:
Du must JDK 1.5 installiert haben...
Das ist ja schon fast eine Beleidigung, natürlich hab ich Java 1.5 auf meinem Rechner, schon seit den ersten Betas :!: :wink:

Zeile 24 und Zeile 58: mach aus den "Node" "Node<T>", sonst geht die Typsicherheit flöten (darum reklamierte auch mein liebes Eclipselein, du müsstest eigentlich ein paar Warnungen haben?).

Bin mir jetzt nicht ganz sicher, aber suchst du sowas? (Achtung: ich hab da zweimal "f" eingegeben, deshalb die Ausgabe 2)
Code:
class MMenge<T extends Comparable> {
	Node root = null;

	class Node<T extends Comparable> {
		T value;

		int indx = 1;

		Node left, right;

		public Node(T v){
			value = v;
		}
	}

	void insert( T[] val ) {
		for( T t : val )
			insert( t );
	}

	void insert( T element ) {
		Node<T> parent = null, child = root;

		if( root == null ){
			root = new Node<T>( element );
			return;
		}
		
		while( true ){
			parent = child;

			if( element.compareTo( child.value ) == 0 ){
				child.indx += 1;
				return;
			}

			if( element.compareTo( child.value ) < 0 ){
				child = parent.left;
				if( child == null ){
					parent.left = new Node<T>( element );
					return;
				}
			}
			else{
				child = parent.right;
				if( child == null ){
					parent.right = new Node<T>( element );
					return;
				}
			}
		}

	}

	int anzahl( T wert ) {
		Node<T> parent = root;
		while( parent != null ){
			if( parent.value.compareTo( wert ) == 0 ){
				return parent.indx;
			}
			if( parent.value.compareTo( wert ) > 0 )
				parent = parent.left;
			else
				parent = parent.right;
		}
		return 0;
	}

	public static <T extends Comparable> void print( int tab, Node<T> node ) {
		printTabs( tab );
		if( node == null )
			System.out.println( "-" );
		else{
			System.out.println( node.indx + " / " + node.value );
			print( tab + 1, node.left );
			print( tab + 1, node.right );
		}

	}

	public static void printTabs( int tabs ) {
		for( int i = 0; i < tabs; i++ )
			System.out.print( " " );
	}

	public static void main( String[] args ) {
		MMenge<String> test = new MMenge<String>();
		String[] hallo = { "a", "a", "a", "a", "v", "d", "f", "r", "f", "a" };
		test.insert( hallo );
		MMenge<String> test2 = new MMenge<String>();
		test2 = test;
		print( 0, test.root );
//		System.out.println( test.root.right.right.value );
		System.out.println( test.anzahl( "f" ) );
	}
}
 
B

Beni

Gast
Du hattest keine richtigen Abbruchbedingungen in deiner Schleife (in "insert"). Wenn du ein Element gefunden hattest, wurde zwar der Knoten markiert, aber dann ging es munter weiter (was immer zu einem neuen Knoten führt).

Ich hab jetzt einfach deine "insert"-Methode in zwei verschiedene Methoden aufgeteilt, und springe mit "return" aus der zweiten Methode raus, sobald ein Werte gefunden wird.

Das zweite ist diese "anzahl" Methode: das Argument "MMenge<T> baum" ist unnötig, du suchst ja nicht "baum" ab, sondern das Objekt, von dem du "anzahl" aufgerufen hast.
 

gustav-mega

Bekanntes Mitglied
erstmal Vielen, Vielen, Vielen Dank :D , und übrigens mit JDK 1.5 war nicht böse gemeint :wink: . Jetzt noch eine Frage: wenn ich eine while-Schleife in einer for-Schleife habe wie kann ich aus der while-Schleife rausspringen ohne, daß ich aus der for-Schleife rausgesprungen werde?
 
B

Beni

Gast
Das geht mit "break":

Code:
for(...){
  while(...){
    break; // beendet das while
  }
}

Du kannst auch ein Label verwenden (dann wirds übersichtlicher).

Code:
for(...){
  loop: while(...){
    break loop;  // beendet die mit "loop" markierte Schleife
  }
}
 

Illuvatar

Top Contributor
So könntest du übrigens natürlich auch aus der äußeren Schleife springen:
Code:
loop: for(...){ 
  while(...){ 
    break loop;  // beendet die mit "loop" markierte Schleife 
  } 
}
 

bambi

Bekanntes Mitglied
kleine zwischenfrage:
ich hab' mal gelernt, dass labels "nicht so toller" programmierstil waeren - hat sich das jetzt mit java 1.5 geaendert? also bei c++ - ich weiss, das hier ist java - war's nicht so gut...
 

gustav-mega

Bekanntes Mitglied
nur daß ich es auch richtig verstehe, mit return springe ich ganz aus aus alle Schleifen und der Methode raus, mit break aus der aktuelle Schleife und mit continue setzt sich die Schleife beim nächsten Schritt einfach fort, richtig?
 
B

Beni

Gast
Da hast du schon recht bambi. Theoretisch sollte man auch nur ein "return" pro Methode haben, und break (ah, es gibt auch noch continue :D ) gar nicht benutzen, sondern alles mit if's lösen.
Das führt dann zu Code, der nicht "wild in der Gegend rumspringt".
Naja, und das gibt dann x ineinandergeschachtelte Klammern, ich finde die Lösung auch nicht gerade "so dolle".

Was wirklich schlecht ist, ist das goto. Da kann man wirklich Verwirrung stiften.

edit:
@gustav-mega
Jop, richtig verstanden
 

Illuvatar

Top Contributor
mit if/else und nem boolean ob er abbrechen soll z.B. gehts immer auch. Aber da wirds um einiges unübersichtlicher als nen kleines feines break irgendwo, find ich.

Edit: Is halt bissle wie goto, auch das kann man hin und wieder sinnvoll und mit gutem Programmierstil eingesetzt werden. Da das aber 0,1% der Leute so machen wurde es gleich weggelassen ;)
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
P Frage zu SortedMap: Warum kann ich Item zweimal einfügen? Java Basics - Anfänger-Themen 3
F Kurze Frage: JLabel in BorderLayout einfügen Java Basics - Anfänger-Themen 2
Zrebna Frage zu Test-Driven Development (TDD) Java Basics - Anfänger-Themen 3
I Frage Thymeleaf -> Fehler ignorieren und mit "" ersetzen? Java Basics - Anfänger-Themen 15
I Frage Thymeleaf -> Prefix / Suffix ändern? Java Basics - Anfänger-Themen 11
D Rekursions Probleme / frage Java Basics - Anfänger-Themen 4
T Frage zu Parse Java Basics - Anfänger-Themen 2
H Frage an die Profis Java Basics - Anfänger-Themen 4
J Eine konzeptionelle Frage zu OOP Java Basics - Anfänger-Themen 3
P Frage zu Rekursion und Backtracking Java Basics - Anfänger-Themen 2
H Frage zur Ausgabe Java Basics - Anfänger-Themen 4
H Frage zu arithmetischen Operationen Java Basics - Anfänger-Themen 20
F Kurze Frage zu replace() Java Basics - Anfänger-Themen 19
JavaSchmecktLecker Polymorphie Frage zur Methodenüberschreibung Java Basics - Anfänger-Themen 21
J Frage zu einem "Taschenrechner" code Java Basics - Anfänger-Themen 9
B Erste Schritte Frage zu Instanzierung und Referenzen Java Basics - Anfänger-Themen 8
DoubleM Runtime.getRuntime().exec Frage Java Basics - Anfänger-Themen 2
J Eine theoretische Frage zur Praxis - JPanel oder Canvas Java Basics - Anfänger-Themen 5
O Frage: Formaler Typbezeichner? Java Basics - Anfänger-Themen 3
I BlueJ Queue Frage für Klausur Java Basics - Anfänger-Themen 2
N Verständnis Frage zu Variablen Java Basics - Anfänger-Themen 3
N Spezielle frage zum Comparator Java Basics - Anfänger-Themen 6
L Frage zum Array Java Basics - Anfänger-Themen 1
A Frage zum UML Design Java Basics - Anfänger-Themen 1
I Hilfe bei Klausur Frage Java Basics - Anfänger-Themen 8
izoards Drucken Frage zu FAQ Beitrag Java Basics - Anfänger-Themen 2
J Frage zu meinem Code (OOP) Java Basics - Anfänger-Themen 4
sserio Split() -> Regex Frage. Java Basics - Anfänger-Themen 7
A OCA Study Guide: 2. Frage aus Kapitel 3 Java Basics - Anfänger-Themen 9
sserio Date Library Frage Java Basics - Anfänger-Themen 9
Max246Sch Frage zu Währungsrechner Code Java Basics - Anfänger-Themen 2
sserio Frage zu HashMaps Java Basics - Anfänger-Themen 20
sserio Frage zu Threading - Multithreading Java Basics - Anfänger-Themen 2
sserio Frage zu Lambda Ausdrücken Java Basics - Anfänger-Themen 7
sserio Frage zu BigInteger Java Basics - Anfänger-Themen 1
D Frage bzgl. Enum-Handhabung Java Basics - Anfänger-Themen 16
xxx12 Frage Java Basics - Anfänger-Themen 2
I Generelle Frage zu Mikroservices (Spring Boot?), Docker... Java Basics - Anfänger-Themen 7
R Frage zu Methoden (Rückgabewert u. ohne.) Java Basics - Anfänger-Themen 2
A Frage zur programmierung Java Basics - Anfänger-Themen 12
M Frage zur Methode split der Klasse String Java Basics - Anfänger-Themen 32
R Input/Output Frage zu Java IO Java Basics - Anfänger-Themen 6
M Frage zu printWriter Java Basics - Anfänger-Themen 5
C Frage zu OLSMultipleLinearRegression Java Basics - Anfänger-Themen 31
KogoroMori21 Frage zum Euklidischen Algorithmus Java Basics - Anfänger-Themen 11
S Verständnis-Frage zu einer HÜ? Java Basics - Anfänger-Themen 1
F Frage betreff Programm mit dem man C++-Code in JAVA-Code übersetzen lassen kann Java Basics - Anfänger-Themen 2
L Frage zur Ticket Maschine Java Basics - Anfänger-Themen 1
J Frage zu OOP-Klassendiagramm Java Basics - Anfänger-Themen 8
OSchriever Frage zu Compiler Java Basics - Anfänger-Themen 8
H Frage zu Throw Exception Java Basics - Anfänger-Themen 2
TimoN11 Frage zu Java-Vererbung (Cast) Java Basics - Anfänger-Themen 5
Bademeister007 Hallo Leute ich hab eine Frage zur ArrayList Java Basics - Anfänger-Themen 8
F Frage betreff Programmierbücher zu Lagerverwaltung als Konsolenprogramm Java Basics - Anfänger-Themen 3
dieter000 Kurze Frage kann mir ejmand kurz diesen Code erklären, bzw wie man die zeilen erklärt und so Java Basics - Anfänger-Themen 1
I String.split regex Frage Java Basics - Anfänger-Themen 2
N Best Practice Frage zum MVC-Pattern Java Basics - Anfänger-Themen 2
dieter000 Frage zu einem Beispiel... Java Basics - Anfänger-Themen 5
J Frage zum Loggen Java Basics - Anfänger-Themen 18
J Methoden Frage: Array-Werte in anderer Methode ändern Java Basics - Anfänger-Themen 4
Zrebna Frage zum "Referenzen-konzept" in Java Java Basics - Anfänger-Themen 8
JD_1998 Array-Position aus einer Methode in einer anderen ausgeben (Kurze Frage) Java Basics - Anfänger-Themen 2
marcooooo Frage zu bestimmten Beispiel Java Basics - Anfänger-Themen 31
NeoLexx equals()-Methode Verständnis Frage anhand Code Beispiel Java Basics - Anfänger-Themen 22
N Input/Output Eine Frage über system.out.println. Java Basics - Anfänger-Themen 10
B Erste Schritte Learning Coding (!) Frage an erfahrene Programmierer. Java Basics - Anfänger-Themen 23
M konzeptuelle Frage: In welcher Klasse definiert man am Besten Methoden, die die Kommunikation mit dem User regeln? Java Basics - Anfänger-Themen 8
B Frage zum Code verständnis im Resultat Java Basics - Anfänger-Themen 10
C Exception-Frage Java Basics - Anfänger-Themen 3
J Eine Frage zur Schreibweise == ? : Java Basics - Anfänger-Themen 3
S Frage des Designs Java Basics - Anfänger-Themen 1
JavaTalksToMe Extends/Implements Frage Java Basics - Anfänger-Themen 3
pkm Frage zu Servletfunktion Java Basics - Anfänger-Themen 0
B Frage zur Währungsumrechnung Java Basics - Anfänger-Themen 3
S Allgemeine Frage über Generics und Vererbungen Java Basics - Anfänger-Themen 5
Kirby.exe Frage zur Verwendung von Interfaces Java Basics - Anfänger-Themen 6
D Frage zu Strings einer Exception Java Basics - Anfänger-Themen 4
L Wie frage ich ab, ob in einem Array, Werte doppelt vorkommen? Java Basics - Anfänger-Themen 4
D Frage zur IDE IntelliJ IDEA Java Basics - Anfänger-Themen 6
H Frage zum 2d Array Java Basics - Anfänger-Themen 1
N Frage zum Newton-Fraktal Java Basics - Anfänger-Themen 1
H Frage zu interfaces Java Basics - Anfänger-Themen 1
J Frage dazu Variablen klassenübergreifend zu verändern Java Basics - Anfänger-Themen 22
I Frage zu SkipList Java Basics - Anfänger-Themen 4
G Frage zu JScrollPane Java Basics - Anfänger-Themen 12
Kirby.exe Allgemeine Frage Java Basics - Anfänger-Themen 3
W Frage zu anonymen Klassen Java Basics - Anfänger-Themen 4
J Kleine Frage zu OOP Java Basics - Anfänger-Themen 371
S Frage Klasse und Objekte Java Basics - Anfänger-Themen 2
F Frage zu Iteratoren Java Basics - Anfänger-Themen 2
C Erste Schritte Frage zur ArrayList Java Basics - Anfänger-Themen 15
J Frage zur Vererbung Java Basics - Anfänger-Themen 1
H Frage zur ermittlung eines doppelte Paars aus Sotieralgorithmus Java Basics - Anfänger-Themen 4
H Frage zum Array Java Basics - Anfänger-Themen 17
G Schach -Frage 2- Maussteuerung Java Basics - Anfänger-Themen 7
G Schach in Java - Allgemeine Frage zur Architektur Java Basics - Anfänger-Themen 7
B Fachliche Frage bei Rechnungen Java Basics - Anfänger-Themen 16
B Frage zu: String... strings -> Ungleiche Anzahl an Parameter? Java Basics - Anfänger-Themen 4
B Frage zu Datenbank Design - Rechnungen, Angebote... und deren Positionen Java Basics - Anfänger-Themen 4
H Frage zu Parameter einer Methode Java Basics - Anfänger-Themen 2

Ähnliche Java Themen

Neue Themen


Oben