Binäre Suchbaum + Erstellung des Programmes

[granini]

Hallo,

es soll ein Quellcode erstellt werden, welches die Methoden contains, insert und delete enthält.
Ich habe große Schwierigkeiten Ansätze zu finden und habe auch zunächst die Methode delete weggelassen.

Wer kann mir helfen anhand meines Programmgerüstes meine Fehler ausfindig zu machen und das Programm zum Laufen zu bringen?

Das ist mein bisheriges Ergebnis, wo einiges noch nciht übereinstimmt:

import java.util.*;


class BinaryNode {
	private BinaryNode root, leftSon, rightSon;
	private int value;
	public boolean lessThan (Object v){
		return true;
	}
	public boolean greaterThan (Object v){
		return true;
	}
	
	public BinaryNode (int i){
		
		root = leftSon = rightSon = null;
		value = i;
		
	}
	
	public boolean contains (int v) {
		if (root.equals(v)) return true;
		if (root.lessThan(v)|root.greaterThan(v)) return true;
		return false;
	}
	public void insert (int v ) {
		if (contains(v)){
			BinaryNode tree  = value;
		
		}else {
			if (v > root.value) {
				root.rightSon = insert(v);
			}else{
				if (v < root.value) {
					root.leftSon = inser(v);
				}
			}
		}
		
	}
}

public class Main {
	public static void main(String[] args) {
		BinaryNode myTree = new BinaryNode(1);
		myTree.insert(4);
		myTree.insert(9);
		myTree.insert(2);
		myTree.insert(18);
		myTree.insert(13);

	}

}

Danke

Gruss

 

[moormaster]

Hallo,

es soll ein Quellcode erstellt werden, welches die Methoden contains, insert und delete enthält.
Ich habe große Schwierigkeiten Ansätze zu finden und habe auch zunächst die Methode delete weggelassen.

Wer kann mir helfen anhand meines Programmgerüstes meine Fehler ausfindig zu machen und das Programm zum Laufen zu bringen?

Wahrscheinlich niemand, denn die meisten hier haben keine Lust, Rätsel raten zu spielen, um herauszufinden, wo genau das Problem liegt. Also könntest du es etwas weiter eingrenzen, wo genau dein Problem liegt; sprich was genau Dein Programm anders macht, als du es erwartest?

 

[granini]

Ok,

zunächst die Methode contains.. Dort brauche ich etwas äquivalentes zu equals, lessThan und GreaterThan was mit int v zusamenarbeitet. Oder kann ich die Methode public boolean contains (int v) anders gestalten??

Die Methode insert: Was gebe ich am besten zurück, wenn die contains (v) = true ist?? Meine Idee geht nicht so ganz, da keine int-Variable zu binaryNode konvertiert werden kann.
Und wie muss die Syntax lauten, um ein Node einzufügen?

Soweit erstmal..

Danke

 

[granini]

Wollte nochmal auf mich aufmerksam machen. ;-)

Es gibt doch bestimmt jemanden der mir da helfen kann...

 

[bygones]

ok die contains geht so schonmal nicht ;-)

public boolean contains (int v) { 
      if (root.equals(v)) return true; 
      if (root.lessThan(v)|root.greaterThan(v)) return true; 
      return false; 
   }

v ist ein int - das kannst du nicht einfach per equals mit einem Objekt vergleichen - wäre auch unlogisch.
außerdem musst du doch deinen Baum durchlaufen und die werte überprüfen ? desweiteren ist es unsinnig für jeden knoten die überprüfung an der wurzel zu beginnen, sondern es sollte bei dem aktuellen Knoten begonnen werden

public boolean contains(int v) {
  if(v == value)
     return true;

  if(v < value)
    return leftSon == null ? false : leftSon.contains(v);

  if(v > value) 
    return rightSon == null ? false : rightSon.contains(v);
}

d.h. wenn der übergebene wert gleich dem knoten wert ist -> true.
Ansonsten schauen ob man nach links oder rechts gehen muss & wenn es ein Kind gibt, so überprüft man rekursiv die Kinder