Guten Abend Community,
momentan schreibe ich an einem binären Suchbaum, über den ich iterieren möchte. Sobald ich aber meinen Iterator, der nach der Tiefensuche iteriert, ausführe erhalte ich eine NullPointerException. Dieser Nullpointer ergibt sich, sobald ich in der Zeile "stack.push(current)", also tippe ich darauf, dass mein "current" nichts ist. Sobald ich aber anstatt dem Startwert, die Wurzel "root" am Anfang der Klasse verwende, erhalte ich ebenfalls einen NullPointer. Nun ist meine Frage, mit was ich meinen Startwert nun instanziieren muss oder ob mein Ansatz generell falsch ist? Generell habe ich etwas Schwierigkeiten den Iterator zu schreiben und wäre über jegliche Tipps und Anregungen sehr dankbar. Ich habe folgende Klasse geschrieben und habe zwar nur mit der Iterator()-Methode ein paar Probleme, dennoch poste ich die gesamte Klasse, damit sich Fragen im Vorfeld ergeben sollten bzw. man die Struktur besser erkennen kann. Danke im Voraus
momentan schreibe ich an einem binären Suchbaum, über den ich iterieren möchte. Sobald ich aber meinen Iterator, der nach der Tiefensuche iteriert, ausführe erhalte ich eine NullPointerException. Dieser Nullpointer ergibt sich, sobald ich in der Zeile "stack.push(current)", also tippe ich darauf, dass mein "current" nichts ist. Sobald ich aber anstatt dem Startwert, die Wurzel "root" am Anfang der Klasse verwende, erhalte ich ebenfalls einen NullPointer. Nun ist meine Frage, mit was ich meinen Startwert nun instanziieren muss oder ob mein Ansatz generell falsch ist? Generell habe ich etwas Schwierigkeiten den Iterator zu schreiben und wäre über jegliche Tipps und Anregungen sehr dankbar. Ich habe folgende Klasse geschrieben und habe zwar nur mit der Iterator()-Methode ein paar Probleme, dennoch poste ich die gesamte Klasse, damit sich Fragen im Vorfeld ergeben sollten bzw. man die Struktur besser erkennen kann. Danke im Voraus
Java:
public class AuDTree<E extends Comparable<? super E>> implements AuDTreeInterface<E> {
private class Node{
public Node left;
public Node right;
public Node parent;
public E value;
public Node(E value){
left = null;
right = null;
parent = null;
this.value = value;
}
}
public Node root;
public AuDTree(){
this.root = null;
}
@Override
public boolean isEmpty() {
if(root == null){
return true;
}
else{
return false;
}
}
@Override
public int count() {
return count(root);
}
private int count(Node n) {
if (n == null) return 0;
else {
int l = 1;
l += count(n.left);
l += count(n.right);
return l;
}
}
@Override
public int getHeight() {
return getHeight(root);
}
private int getHeight(Node n) {
if (n == null) {
return -1;
}
return Math.max(getHeight(n.left), getHeight(n.right)) + 1;
}
@Override
public boolean isAVLTree() {
return isAVLTree(root);
}
public boolean isAVLTree(Node n){
if(root == null) return true;
if(root.value.compareTo(getMinValue()) <= 0 || root.value.compareTo(getMaxValue()) >=0) {
return false;
}
else{
if(n.left != null)isAVLTree(n.left);
if(n.right != null)isAVLTree(n.right);
if(getHeight(n.left) - getHeight(n.right) > 1 || getHeight(n.right) - getHeight(n.left) > 1 ){
return false;
}
return true;
}
}
@Override
public boolean contains(E value) {
if(isEmpty()) return false;
else{
Node current = root;
while (current != null) {
int comparison = value.compareTo(current.value);
if (comparison == 0) {
return true;
} else if (comparison < 0) {
current = current.left;
} else { //comparison > 0
current = current.right;
}
}
return false;
}
}
@Override
public void insert(E value) throws ElementExistsException {
if(contains(value)) throw new ElementExistsException();
else{
if(root == null) root = new Node(value);
else{
Node father = null;
Node k = root;
while(k != null){
father = k;
if(value.compareTo(k.value) < 0){
k = k.left;
}
else{
if(value.compareTo(k.value) > 0){
k = k.right;
}
}
}
if(value.compareTo(father.value) < 0){
father.left = new Node(value);
}
else{
father.right = new Node(value);
}
}
}
}
@Override
public void remove(E value) throws ElementExistsException {
if(!contains(value)) throw new ElementExistsException("Gibts nicht!");
else{
Node node = finds(value);
node = deleteNode(node);
}
}
private Node deleteNode(Node node){
Node newNode = node;
if(node.left == null && node.right == null) newNode = null;
else if(node.left != null && node.right == null) newNode = node.left;
else if(node.left == null && node.right != null) newNode = node.right;
else{
if(quantityofchildren(biggest(node.left)) == 0){
newNode = biggest(node.left);
}
else{
Node secondNode = node;
newNode = biggest(node.left);
secondNode = biggest(node.left).left;
}
}
return node;
}
private Node finds(E value){
Node current = root;
while (current != null) {
int comparison = value.compareTo(current.value);
if (comparison == 0) {
return current;
} else if (comparison < 0) {
current = current.left;
} else { //comparison > 0
current = current.right;
}
}
return current;
}
private int quantityofchildren(Node node){
return getHeight(node);
}
private String leftorrightchildren(Node node){
if(node.value.compareTo(node.parent.value) > 0) return "right";
else return "left";
}
private Node biggest(Node node){
Node start = node;
while(start.right != null){
start = start.right;
}
return start;
}
private E smallest(Node node){
Node start = node;
while(start.left != null){
start = start.left;
}
return start.value;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>(){
Node start;
Node current;
int counter;
Stack<Node> stack;
public void iterator() {
start = new Node(null);
counter++;
stack = new Stack<Node>();
current = start;
stack.empty();
}
@Override
public boolean hasNext() {
if(counter == count(root)) return false;
else return true;
}
@Override
public E next() {
stack.push(current);
counter++;
if(current.left.value != null) return current.left.value;
else return current.right.value;
}
};
}
@Override
public Iterator<E> iteratorBFS() {
return new Iterator<E>(){
@Override
public boolean hasNext() {
// TODO Auto-generated method stub
return false;
}
@Override
public E next() {
// TODO Auto-generated method stub
return null;
}
};
}
@Override
public E getMinValue() {
Node node = root;
while(node.left != null){
node = node.left;
}
return node.value;
}
@Override
public E getMaxValue() {
Node node = root;
while(node.right != null){
node = node.right;
}
return node.value;
}
public static void main(String[] args) {
AuDTree<Integer> a = new AuDTree<Integer>();
a.insert(3);
a.insert(2);
a.insert(4);
a.insert(1);
a.insert(0);
// System.out.println(a.finds(4));
// a.insert(5);
// a.insert(4);
// a.insert(3);
// System.out.println(a.count());
// System.out.println(a.contains(3));
// System.out.println(a.getHeight());
// System.out.println(a.contains(10));
// System.out.println(a.isAVLTree());
// System.out.println(a.getMinValue());
// System.out.println(a.getMaxValue());
// a.remove(0);
for(Integer element : a){
System.out.println(element);
}
}
}
