Rekursion & Generischer Datentyp

[xyfreeman]

Tag zusammen,

ich habe Probleme bei einer Methode die ich gern rekursiv arbeiten lassen würde.

Ziel: Suche in einem binären Baum.
Problem: Der Rückgabewert.

 public Node find (T x){
  Node<T> f = root;
  
  if (isEmpty())
      return null;
    else if (x.compareTo(f.getValue()) < 0){			
      f = root.getLeft();
      return getLeft().find(x);                              // Problem
    }     
    else if (x.compareTo(f.getValue()) > 0){			
      f = root.getRight();
      return getRight(find(x));                             // Problem
    }
    else {
      f = root.getValue();
      return f;
    }
  }

"The Method getLeft() bzw. getRight() is undefined for the Type List<T>". Diese Aussage raubt mir meine Nerven
Ich will erreichen, dass die Folgenode der linken bzw. rechten Seite übergeben wird und dort weiterhin nach dem Wert x gesucht wird. Aber... da man immer nur einen Wert übergeben kann, scheint dies nicht zu funktionieren. Gibt es keine Möglichkeit?

Noch zur übrigen Struktur:

Ich habe eine Klasse Node, in der ich die Knoten definiere und die Methoden setze sowie eine Klasse List, in der der Baum konstruiert und zur Bearbeitung mit Methoden versehen wird.

public class Node <T extends Comparable<T>>{

  private T value;
  private Node<T> left;
  private Node<T> right;
  
  public Node(T value, Node<T> left, Node<T> right){
  this.value = value;
  this.left = left;
  this.right = right;  
  }

... //get & set Methoden

public class List <T extends Comparable<T>> implements Tree<T>{

  Node<T> root;
  Node<T> left;
  Node<T> right;
 
  public List(){
  
    root = new Node<T>(null, null, null);
    left = new Node<T>(null, null, null);
    right = new Node<T>(null, null, null);
    
    root.setLeft(left);
    root.setRight(right);        
  }

... // andere Methoden

 

[SlaterB]

edit: ne, du willst wohl für getLeft() von root == f weiter nach x suchen,
aber die Operation ist in der Liste definiert und arbeitet nunmal nur mit root,
dann musst du einen zweiten Parameter in der der Operation einfügen oder die Operation in den Node verschieben

 

[xyfreeman]

Mhm... mag an der Hitze in diesem Raum liegen, aber ich bin mir nicht sicher, was du mit "in den Node verschieben" meist, sry.

 

[SlaterB]

class A {

public void x() {
}

}


class B {


}

-------------->

class A {


}


class B {

public void x() {
}

}

== x von A nach B verschoben

 

[xyfreeman]

Ah, okay, einleuchtend. Leider darf ich das nicht.

Allerdings, hoffe ich dass es mit dieser Methode klappt:

public Node find (T x , Node<T> f){
  
  if (isEmpty())
      return null;
    else if (x.compareTo(f.getValue()) < 0){			// Def: < 0 = aufg. x kleiner übergebenem x
      f = root.getLeft();
      return find(x, f);
    }     
    else if (x.compareTo(f.getValue()) > 0){			// Def: > 0 = aufg. x größer übergebenem x
      f = root.getRight();
      return find(x, f);
    }
    else {
      return f;
    }
  }

*edit* Letzten return Wert von null auf f gesetzt & f = root rausgenommen *hust*

 

[SlaterB]

wenn du zu Beginn der Operation immer
f = root;
setzt, dann bringt es dir ja nix, einen anderen Node als root zu übergeben

> f = root.getLeft();
wird die Rekursion auch nicht besonders weit bringen

 

[xyfreeman]

Okay, f = root verbuchen wir als Flüchtigkeitsfehler *g .

Aber f = root.getLeft()? Wenn x < value soll doch im linken Ast weitergesucht werden. Dafür setze ich f auf diesen. Und wenn x nicht < value, wird das nicht vorgenommen.

Oder scheitert es dann daran, dass "root.getLeft()" keine Node zurückgibt? Wobei.. eigentlich müsste sie das tun.

 

[SlaterB]

du bist in einer Rekursion,
vielleicht arbeitet du aktuell mit einem f, welches getLeft() von root in einem vorherigen Aufruf war,
im nächsten Schritt möchtest du nun root.getLeft().getLeft() durchsuchen, nicht nochmal root.getLeft()

also machst du einfach
f = f.getLeft();
denn auf f beziehst du dich ja und durch die Rekursion erreichst du ja gerade, dass f nicht unbedingt root ist

---------------

> if (isEmpty())

musst du wohl auch noch auf das aktuelle f umbauen

 

[xyfreeman]

Danke! Ich komme noch leicht durcheinander wie man merkt


Hier meine empty Methode

public boolean isEmpty(){ 					// überprüft, ob der Baum leer ist
  
    return (root.getValue() == null) ; 
  
  }

Ich denke, dass kann so bleiben. Bezieht sich ja im Grunde genommen nur auf das aller erste Element, also die Wurzel.

Und hier die überarbeitete find:

public Node find (T x , Node<T> f){
    
  if (isEmpty())
      return null;
    else if (x.compareTo(f.getValue()) < 0){			// Def: < 0 = aufg. x kleiner übergebenem x
      f = f.getLeft();
      return find(x, f);
    }     
    else if (x.compareTo(f.getValue()) > 0){			// Def: > 0 = aufg. x größer übergebenem x
      f = f.getRight();
      return find(x, f);
    }
    else {
      return f;
    }
  }

 

[xyfreeman]

Mhm. Ich muss leider noch mal eine ähnliche Frage stellen.

Habe schon wieder das Problem, dass meine Methode x undefiened for the type Node<T> ist.

  public void insert(T x){						
  
  sizecount++;  
  Node<T> nowNode = new Node<T>();
  
  if (isEmpty()){
    if (firstNode() == null)
      this.root.setValue(x);
    else {
      Node<T> newNode = new Node<T>(x);    
    }
  }
  else   	
    if (x.compareTo(root.getValue()) < 0) {
      nowNode = nowNode.getLeft();       		   
      nowNode.insert(x);				//Fehler!      
    }
    else { 
      nowNode = nowNode.getRight(); 
      nowNode.insert(x);				//Fehler!  
    }
  }

Ich möchte einfach mit der nowNode weitermachen, also wieder rekursiv arbeiten. Ich verstehe die obige Meldung auch nicht wirklich, x ist doch genau das was ich auch oben bekomme. Muss ich ihm evt. irgendwie sagen, dass x vom Typ T ist? Wenn ja, wie?

 

[SlaterB]

sollte funktionieren, kommt auf den restlichen Code an,
bei mir kompiliert

public class Node<T extends Comparable<T>> {

	private T value;
	private Node<T> left;
	private Node<T> right;
	private Node<T> root;

	public Node() {
	}

	public Node(T value, Node<T> left, Node<T> right) {
		this.value = value;
		this.left = left;
		this.right = right;
	}

	public Node(T x) {
	}

	public void setValue(T value) {
		this.value = value;
	}

	public T getValue() {
		return value;
	}

	public Node<T> getLeft() {
		return left;
	}

	public Node<T> getRight() {
		return right;
	}

	public void insert(T x) {

		Node<T> nowNode = new Node<T>();

		if (isEmpty()) {
			if (firstNode() == null)
				this.root.setValue(x);
			else {
				Node<T> newNode = new Node<T>(x);
			}
		} else if (x.compareTo(root.getValue()) < 0) {
			nowNode = nowNode.getLeft();
			nowNode.insert(x);
		} else {
			nowNode = nowNode.getRight();
			nowNode.insert(x); 
		}
	}

	private Object firstNode() {
		return null;
	}

	private boolean isEmpty() {
		return false;
	}
}

 

[xyfreeman]

Na dann hat mich Eclipse anscheinend gefopt.

Wobei, ob es wirklich funktioniert, sehe ich dann wohl erst im Praxistest. Trotzdem danke : )

(wobei ich gerade noch andere logische fehler entdeckt habe)