Binärbaum

[sh33p]

ich möchte einen Binärbaum programmieren.
Ich habe folgende Klasse geschrieben:

public class BinaryNode {
     private BinaryNode father, leftSon, rightSon;
     private int value;

     public BinaryNode(int i) {
       father = leftSon = rightSon = null;
       value = i;
     }
     public void insert(int wert){
       if(father == null){        // Vater hat keine Nachfolger.  Ein elementiger Baum
         father = leftSon;
         father.value = wert;
       }
     }


}

wie füge ich nun einen neuen Wert ein,wenn es bereits nachfolger gibt?

 

[Andi_CH]

Irgendwie fehlt mir die Information wo du einfügen willst - an welcher Stelle?
Oder willst du einfach unten an der ersten freien Stelle anhängen? Das brächte dann irgendwie Backtracking um die zu finden.

 

[sh33p]

ok dann machen wirs so,wenn die zahl kleiner ist wie der Vater, dann soll sie in den linke teilbaum (linker sohn) eingefügt werden).ist sie größer,dann in den rechten

 

[Der Müde Joe]

Das ganze sollte dann natürlich auch vom root her in die tiefe gehen. Sprich
solange es links rein muss und einen linken gibt, eins tiefer in die tiefe.

 

[Michael...]

Deine Logik in insert habe ich nicht verstanden. Wenn kein father, dann wird leftSon zum father? Was sind denn das für Familienverhältnisse? ;-)
Aber bräuchtest Du nicht erstmal eine Methode

public void insert(BinaryNode node)

in der Du entsprechende Prüfungen vornimmst?
bzw. wenn Du Deine insert-Methode behalten willst würde ich die eher so deklarieren:

public BinaryNode insert(int i)

 

[sh33p]

public void insert(BinaryNode node)

muss leider diese verwenden.

 

[Der Müde Joe]

Ein bsp könnte zb so aussehen:

public void insert(T data) {
	root =  insert(data, root);
}

private Node<T> insert(T data, Node<T> node) {
	if(node == null) {
		node = new Node<T>(data);
	} else {
		if(data.compareTo(node.data) <= 0) {
			node.left = insert(data, node.left);
		} else {
			node.right = insert(data, node.right);
		}
	}
	return node;
}

EDIT: mit der Node

private static class Node<T> {
	
	private final T data;
	private Node<T> left;
	private Node<T> right;
	
	public Node(T data) {
		this.data = data;
	}
}

 

[sh33p]

könntest du bitte meine Klasse mit dem zugehörigen konstruktor verwenden?

 

[Andi_CH]

public void insert(BinaryNode node)

muss leider diese verwenden.

Na ja, etwas wirst du ja hoffentlich auch selbst noch schaffen ---

aber immerhin habe ich jetzt begriffen dass der Baum sortiert sein soll - diese Information hast du mir vorenthalten ;-)

 

[Andi_CH]

public class BinaryNode {
	private BinaryNode father, leftSon, rightSon;
	private int value;

	public BinaryNode(int i) {
		father = leftSon = rightSon = null;
		value = i;
	}

	public void insert(BinaryNode node) {
		if (node.value == this.value)
			throw new IllegalArgumentException();
		if (node.value < this.value) {
			// links einfügen
			if (leftSon==null) {
// Ja hier muss man was tun
			} else {
// und hier auch
			}
		} else {
			// rehts einfügen
			if (rightSon==null) {
// und hier auch
			} else {
// und hier auch
			}
		}
	}

	public String toString() {
		String retVal = "";
		if (leftSon!=null)
			retVal += leftSon;
		retVal += this.value + " ";
		if (rightSon != null)
			retVal += rightSon;
		return retVal;
	}
}

public class TreeTest {

	public static void main(String[] args) {
		BinaryNode root = null;
		root = new BinaryNode(5);
		System.out.println(root);
		root.insert(new BinaryNode(3));
		System.out.println(root);
		root.insert(new BinaryNode(2));
		System.out.println(root);
		root.insert(new BinaryNode(6));
		System.out.println(root);
		root.insert(new BinaryNode(4));
		System.out.println(root);
	}
}

Output:

5 
3 5 
2 3 5 
2 3 5 6 
2 3 4 5 6