Suchbäume

[ersti[09]]

Hallo, ich hab die Aufgabe mal in den Anhang gepostet.

Mein Ansatz war wie folgt:

public class BinarySearchTree<K> {
  public BinarySearchTree () {
    head = new TreeNode<K>(null);
    nullNode = new TreeNode<K>(null);
    nullNode.setLeft(nullNode);
    nullNode.setRight(nullNode);
    head.setRight(nullNode);
  }
...
}

Allerdings hab ich noch nicht so ganz raus, wie ich die "..." ersetze. Für den Rest habe ich leider auch keinen Ansatz. Vielleicht ist mir da jemand behilflich? Vielen Dank schonmla

 

[Meldanor]

Implementier erstmal die Methode, ob ein Element im Baum enthalten ist, nämlich lookup(K key).
Das mit dem Hinzufügen funktioniert dann ähnlich.
Da ein binärer Suchbaum so aufgebaut ist, dass jeder Teilbaum maximal zwei Elemente besitzt und der linke Teilbaum kleiner ist als der rechte Teilbaum.
Wenn du dann die Wurzel hast und das Element, musst du schauen, ob du links oder rechts gehen musst und dann betrachtest du nur noch den entstehenden Teilbaum(also wenn du nach links gegangen bist, nur noch den linken anschauen und umgekehrt).
So gehste durch den Baum und wenn du dein Element gefunden hast, isses drin.
Wenn nicht, musst du es so einfügen, dass es ein binärer Suchbaum bleibt.

Der Rest baut darauf auf. Hat man erstmal verstanden, wie man durch einen binären Suchbaum geht, baut der Rest ungefähr darauf auf.

 

[ersti[09]]

Ja ok. Bei lookup muss ich ja eigentlich nur vergleichen, ob key = null oder != 0 ist?
Aber wo schreibe ich die Methode rein? in den BinarySearchTree oder nur in den SearchTree?
Das ist halt das Problem was ich habe, ich weiß nicht wo ich die Methoden reinschreibe

 

[Meldanor]

Beim BinarySearchTree. Ein SearchTree hat zwar auch eigenschaften eines BinarySearchTrees, ist aber anders aufgebaut(jeder Knoten kann mehr als nur 2 Kindknoten haben, ein BinarySearchTree hat maximal 2).

 

[ersti[09]]

so?

public class BinarySearchTree<K> implements SearchTree<K>{
  public BinarySearchTree () {
    head = new TreeNode<K>(null);
    nullNode = new TreeNode<K>(null);
    nullNode.setLeft(nullNode);
    nullNode.setRight(nullNode);
    head.setRight(nullNode);
  }
  
  static class TreeNode<K extends Comparable<K> > {
  	  K key;
  	  TreeNode<K> left = null, right = null;
  	  
  }
  	  
  public boolean lookup(K key) {
  	  if(key == null) 
    	  	  return false;
    	  else
  	    	  return true;
  }
 
  public boolean insert(K key) {
  	  TreeNode<K> parent = head, child = head.getRight();
  	  while (child != nullNode) {
  	  	  parent = child;
  	  	  int cmp = child.compareKeyTo(key);
  	  	  if (cmp = 0)
  	  	  	  return false;
  	  	  else if (cmp > 0)
  	  	  	  child = child.getLeft();
  	  	  else 
  	  	  	  child = child.getRight();
  	  }
  	  
  	  TreeNode<K> node = new TreeNode<K> (key);
  	  node.setLeft(nullNode);
  	  node.setRight(nullNode);
  	  if (parent.compareKeyTo(key) > 0)
  	  	  parent.setLeft(node);
  	  else
  	  	  parent.setRight(node);
  	  return true;
  	  
  }
  
  public K getMaxElement() {
  	  TreeNode<K< n = head.getRight();
  	  while (n.getRight() != nullNode)
  	  	  n = n.getRight();
  	  return n.getKey();
  }
  
  public K getMinElement()
  
  
}

das kann ja nicht richtig sein...