Hallo,
ich habe ein Problem beim Anhängen eines Knotens. Bisher werden komischerweise nur Zahlen von 1-9 korrekt dargestellt. Es sollen aber alle positiven sowie negativen Zahlen dargestellt werden können. Zahlen die größer als der vorangegangene Knoten sind, müssen rechts abgebildet werden und kleinere Zahlen links.
Das Löschen eines Endknotens funktioniert problemlos (Zahlen 2, 6, 8), wenn jedoch die Zahl 7 löscht, tritt ein "NullPointerException" auf. In diesem Bsp. sollte jeweils der längste Zweig nachrutschen, in diesem Fall die 9 ersetzt die 7. Sind beide Zweige gleich lang, dann soll der größere Wert nachrutschen.
Kann mir dabei jemand aus der Community vielleicht helfen? Komme da leider nicht weiter.
Danke schonmal im Voraus!
Node.java
BinaryTreeTest.java
BinaryTree.java
ich habe ein Problem beim Anhängen eines Knotens. Bisher werden komischerweise nur Zahlen von 1-9 korrekt dargestellt. Es sollen aber alle positiven sowie negativen Zahlen dargestellt werden können. Zahlen die größer als der vorangegangene Knoten sind, müssen rechts abgebildet werden und kleinere Zahlen links.
Das Löschen eines Endknotens funktioniert problemlos (Zahlen 2, 6, 8), wenn jedoch die Zahl 7 löscht, tritt ein "NullPointerException" auf. In diesem Bsp. sollte jeweils der längste Zweig nachrutschen, in diesem Fall die 9 ersetzt die 7. Sind beide Zweige gleich lang, dann soll der größere Wert nachrutschen.
Kann mir dabei jemand aus der Community vielleicht helfen? Komme da leider nicht weiter.
Danke schonmal im Voraus!
Node.java
Java:
package binaerbaum2;
import java.io.Serializable;
import java.util.List;
public class Node implements Serializable{
private Node left;
private Node right;
private Integer value;
public Node(Integer value) {
this.value = value;
}
/**
* @return the UebergabeObjekt
*/
public Integer getValue() {
return value;
}
@Override
public String toString() {
return value.toString();
}
public boolean add(int thatValue) {
int result = BinaryTree.comparator.compare(this.value, thatValue);
System.out.println(result);
if(result == 0) { //Objekt bereits vorhanden - tue nichts
return false;
} else if(result > 0) { //Objekt ist größer -> rechter Sohn
if (right == null) {
right = new Node(thatValue);
return true;
} else {
return right.add(thatValue);
}
} else { //Objekt ist kleiner -> linker Sohn
if (left == null) {
left = new Node(thatValue);
return true;
} else {
return left.add(thatValue);
}
}
}
public int getDepth() {
int leftDepth = left == null ? 0 : left.getDepth();
int rightDepth = right == null ? 0 : right.getDepth();
return 1 + Math.max(leftDepth, rightDepth);
}
public boolean delete(int thatValue) {
int result = BinaryTree.comparator.compare(this.value, thatValue);
if(result == 0) { //Objekt gefunden - löschen
if (left == null && right == null) {
value = null;
} else if (left != null && (right == null || Math.random() < 0.5)) {
value = left.getValue();
left = left.left;
right = left.right;
} else {
value = right.getValue();
left = right.left;
right = right.right;
}
return true;
} else if(result > 0) { //Objekt ist größer -> rechter Sohn
if (right == null) {
System.out.println("\nKnoten konnte nicht gefunden werden.");
return false;
} else {
if(right.delete(thatValue)) {
if (right.getValue() == null) {
right = null;
}
return true;
} else {
return false;
}
}
} else { //Objekt ist kleiner -> linker Sohn
if(left == null) {
return false;
} else {
if(left.delete(thatValue)) {
if (left.getValue() == null) {
left = null;
}
return true;
} else {
return false;
}
}
}
}
void display(StringBuilder sb, String upperPrefix, String prefix, String lowerPrefix) {
if (left != null) {
left.display(sb, upperPrefix + " ", upperPrefix + "/--", upperPrefix + "| ");
}
sb.append(prefix).append(value).append('\n');
if (right != null) {
right.display(sb, lowerPrefix + "| ", lowerPrefix + "\\--", lowerPrefix + " ");
}
}
void toList(List<Object> result) {
if(left != null) {
left.toList(result);
}
result.add(value);
if(right != null) {
right.toList(result);
}
}
}BinaryTreeTest.java
Java:
package binaerbaum2;
import java.io.*;
import java.util.*;
public class BinaryTreeTest {
BinaryTree binearTree;
private final int ANHAENGEN = 1;
private final int ENTFERNEN = 2;
private final int BAUMAUSGABE = 3;
private final int SPEICHERN = 4;
private final int LADEN = 5;
private final int ENDE = 9;
private int wert;
private Scanner scanner = new Scanner(System.in);
public BinaryTreeTest() {
}
public void start() {
int menueAuswahl = -1;
binearTree = new BinaryTree();
do {
System.out.println("<<<<<<<<<<<<< M E N U E >>>>>>>>>>>>");
System.out.println("** Bitte treffen Sie eine Auswahl **");
System.out.println("<<<<<<<<<<<<<<<<< >>>>>>>>>>>>>>>>>>");
try {
menueAuswahl = auswaehlen();
switch (menueAuswahl) {
case ANHAENGEN:
System.out.print("Bitte Zahl eingeben: ");
wert = scanner.nextInt();
binearTree.add(wert);
break;
case ENTFERNEN:
System.out.print("Bitte Zahl eingeben: ");
wert = scanner.nextInt();
binearTree.delete(wert);
break;
case BAUMAUSGABE:
System.out.println("<<<<<<<<<<<<<<<<< >>>>>>>>>>>>>>>>>>");
System.out.println(" B A U M A U S G A B E");
System.out.println("<<<<<<<<<<<<<<<<< >>>>>>>>>>>>>>>>>>\n");
System.out.println(binearTree.toString());
break;
case LADEN:
System.out.println("\n******** Binärbaum einlesen ********");
this.deserialize("binaerbaum.txt");
break;
case SPEICHERN:
System.out.println("\n******** Binärbaum speichern *******");
this.serialize("binaerbaum.txt");
break;
case ENDE:
break;
default:
System.out.println("\n************************************");
System.out.println("Bitte eine gültige Eingabe machen.");
System.out.println("************************************\n");
}
} catch (Exception e) {
e.printStackTrace();
menueAuswahl = ENDE;
}
} while (menueAuswahl != ENDE);
}
public int auswaehlen() {
System.out.print(
"*** Taste " + ANHAENGEN + ": Knoten anhaengen ******\n" +
"*** Taste " + ENTFERNEN + ": Knoten entfernen ******\n" +
"*** Taste " + BAUMAUSGABE + ": Binärbaum ausgeben ****\n" +
"*** Taste " + SPEICHERN + ": Binärbaum speichern ***\n" +
"*** Taste " + LADEN + ": Binärbaum laden *******\n" +
"*** Taste " + ENDE + ": Programm beenden. *****\n");
System.out.println("<<<<<<<<<<<<<<<<< >>>>>>>>>>>>>>>>>>");
System.out.print("Eingabe: ");
return scanner.nextInt();
}
public void serialize(String filename){
try{
FileOutputStream file = new FileOutputStream( filename );
ObjectOutputStream o = new ObjectOutputStream( file );
o.writeObject(this.binearTree);
o.close();
System.out.println("Baum in binaerbaum.txt gespeichert.");
System.out.println("************************************\n");
}catch ( IOException e ) {
System.err.println( e );
}
}
void deserialize( String filename ){
try{
FileInputStream file = new FileInputStream( filename );
ObjectInputStream o = new ObjectInputStream( file );
this.binearTree = (BinaryTree) o.readObject();
o.close();
System.out.println("Baum wurde erfolgreich eingelesen.");
System.out.println("************************************\n");
}
catch ( IOException e ) {
System.err.println( e );
}
catch ( ClassNotFoundException e ) {
System.err.println( e );
}
}
public static void main(String[] args) {
try {
BinaryTreeTest testlauf = new BinaryTreeTest();
System.out.println("***********************************");
System.out.println(" B I N A R Y T R E E");
System.out.println("***********************************");
System.out.println(" S O R T E D E D I T I O N");
System.out.println("-----------------------------------");
System.out.println(" V. 1.0\n");
testlauf.start();
} catch (Exception e) {
e.printStackTrace();
}
}
}BinaryTree.java
Java:
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package binaerbaum2;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class BinaryTree implements Serializable {
private Node root;
public static Comparator<Integer> comparator = new Comparator<Integer>(){
public int compare(Integer o1, Integer o2) {
return o1.toString().compareTo(o2.toString());
}
};
private int size;
/**
* Hinzuefuegen von Objekten
*
* @param uebergabeObjekt
* Das uebergeben Object
*/
public void add(int value) {
if (root == null) {
root = new Node(value);
size ++;
} else {
if(root.add(value)) {
size++;
}
}
}
/*
* (non-Javadoc)
*
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
if (root != null) {
StringBuilder sb = new StringBuilder();
root.display(sb, "","","");
return sb.toString();
} else {
return "<leerer Baum>";
}
}
public List<Object> toList() {
List<Object> result = new ArrayList<Object>();
if (root != null) {
root.toList(result);
}
return result;
}
/**
* @return the anzahlKnoten
*
*/
public int getSize() {
return size;
}
/**
* Loescht ein uebergebenes Object
*
* @param uebergabe
* Das yu loeschende Object
*/
public void delete(Integer value) {
if (root != null) {
if (root.delete(value)) {
size--;
}
if (root.getValue() == null) {
root = null;
}
}
}
/**
* @return the gesamtEtagen
*/
public int getDepth() {
if(root == null) {
return 0;
} else {
return root.getDepth();
}
}
}
