Hallo, die Aufgabe ist es an Hand des Interface <> einen <> zu Implementieren und wir dürfen die Vorgaben nicht verändern:
Das Interface:
Hier die einzelne Knotenklasse:
Und hier die Binäre Baum Klasse:
Ich bin jetzt beim einfügen und will das eigentlich rekursiv machen, aber dazu braucht man ja eigentlich irgendwie noch den Baum, deswegen dachte ich an eine HIlfsmethode, aber ich kann nicht auf insert rekursiv zugreifen, einfach weil ich in der Strucktur nicht so ganz druchblicke
könnte mir da jemand behilflich sein, vllt. erklären was ich falsch mache
lg
Das Interface:
Java:
package tree;
/**
* Describes a simple interface for interferring with a tree-like structure.
*
* @param <T> The type the tree is to store in its nodes.
*/
public interface Tree<T extends Comparable<T>> {
/**
* Inserts a value into the tree. Doubled values are overwritten.
* A value doubles some other value if the following condition is true:
* <code>o1.compareTo(o2) == 0</code>
* Null values are not added into the tree.
*
* @param e The value to be inserted into the tree.
*/
public void insert(T e);
/**
* Searches the tree for a value <code>e</code> and returns the node containing it,
* if it is found.
*
* @param e The value to be searched for.
* @return The value e, if it exists, or <code>null</code> if the value
* was not found
*/
public T find(T e);
/**
* Removes the value <code>e</code> from the tree.
*
* @param e The value to be removed.
*/
public T delete(T e);
/**
* Returns the list containing all elements of the tree
* sorted using a pre-order traversing.
*
* <emph>Implicates the subnodes are ordered</emph>
*
* @return The list in the pre-order visit order.
*/
public Object[] traversePreOrder();
/**
* Returns the list containing all elements of the tree
* sorted by an in-order traversing
*
* <emph>Implicates a binary tree</emph>
*
* @return The list in the in-order visit order.
*/
public Object[] traverseInOrder();
/**
* Returns the list containing all elements from the tree
* sorted by a post-order traversing.
*
* <emph>Implicates the subnodes are ordered</emph>
*
* @return The list in the post-order visit order.
*/
public Object[] traversePostOrder();
}Hier die einzelne Knotenklasse:
Java:
package tree;
import java.util.LinkedList;
class BinarySearchTreeNode<T extends Comparable<T>> implements Comparable<BinarySearchTreeNode<T>> {
private BinarySearchTreeNode<T> left;
private BinarySearchTreeNode<T> right;
private T value;
BinarySearchTreeNode(T value, BinarySearchTreeNode<T> left, BinarySearchTreeNode<T> right) {
this.value = value;
this.left = left;
this.right = right;
}
BinarySearchTreeNode(T value) {
this(value, null, null);
}
BinarySearchTreeNode<T> getLeft() {
return left;
}
void setLeft(BinarySearchTreeNode<T> left) {
this.left = left;
}
BinarySearchTreeNode<T> getRight() {
return right;
}
void setRight(BinarySearchTreeNode<T> right) {
this.right = right;
}
T getValue() {
return value;
}
void setValue(T value) {
this.value = value;
}
@Override
public int compareTo(BinarySearchTreeNode<T> o) {
return value.compareTo(o.getValue());
}
}Und hier die Binäre Baum Klasse:
Java:
package tree;
import java.util.LinkedList;
/**
* Represents a binary search tree.
*
* @param <T>
* The type of the object that are to be stored in the tree.
*/
public class BinarySearchTree<T extends Comparable<T>> implements Tree<T> {
private BinarySearchTreeNode<T> root;
private int elements;
/**
* Constructs an empty tree.
*/
public BinarySearchTree() {
elements = 0;
root = null;
}
@Override
public void insert(T e) {
//TODO: your implementation here
// Wenn das Element null ist
if (e == null)
return;
//Wenn der Baum leer(null) ist
if (this.root == null){
this.root.setValue(e);
this.root.setLeft(null);
this.root.setRight(null);
}
//wenn das Element gleich der Wurzel ist
if ( e.compareTo( root.getValue() )==0 )
return;
//Wenn das Element kleiner der Wurzel ist
if ( e.compareTo( root.getValue() )== -1 ){
insertHelp(root.getLeft(),e);
}
}
public void insertHelp (BinarySearchTreeNode<T> binNode, T e){
if (root == null)
root = new BinarySearchTreeNode(e);
else
root.insertHelp(root.getLeft(),e);
}
@Override
public T find(T e) {
//TODO: your implementation here
return null;
}
@Override
public T delete(T e) {
//TODO: your implementation here
return null;
}
@Override
public Object[] traversePreOrder() {
//TODO: your implementation here
return null;
}
@Override
public Object[] traverseInOrder() {
//TODO: your implementation here
return null;
}
@Override
public Object[] traversePostOrder() {
//TODO: your implementation here
return null;
}
/**
* Constructs a tree containing the values from the list, by constructing a
* empty tree and successively adding the specified elements.
*
* @param <T>
* The type argument specifing the type of the items to be stored
* in the tree.
* @param vals
* The values to be inserted into the tree.
* @return Returns a tree containing the specified elements.
*/
public static <T extends Comparable<T>> BinarySearchTree<T> createTree(
T[] vals) {
BinarySearchTree<T> tree = new BinarySearchTree<T>();
for (T val : vals) {
tree.insert(val);
}
return tree;
}
/**
* A setter for the root-element.
*/
void setRoot(BinarySearchTreeNode<T> root) {
this.root = root;
}
/**
* A getter for the root-element.
*
* @return The root node.
*/
BinarySearchTreeNode<T> getRoot() {
return root;
}
/**
* A getter for the elements-field.
*
* @return The count of elements currently in the tree.
*/
public int getNumOfElements() {
return elements;
}
}Ich bin jetzt beim einfügen und will das eigentlich rekursiv machen, aber dazu braucht man ja eigentlich irgendwie noch den Baum, deswegen dachte ich an eine HIlfsmethode, aber ich kann nicht auf insert rekursiv zugreifen, einfach weil ich in der Strucktur nicht so ganz druchblicke
könnte mir da jemand behilflich sein, vllt. erklären was ich falsch mache
lg
