Fehler Binärbaum

[xyt4n]

Hallo,

ich habe eine Klasse geschrieben die ein Binärbaum konstruieren sollte und eine Testklasse, die es testen sollte.

Leider bekomme ich nur die "Spitze" des Baumes zurück. Ich finde meinen Fehler nicht. 🙁

public class Tree {

	private int value;
	private Tree left;
	private Tree right;
	private Tree node;

	public Tree(int i) {
		left = right = node = null;
		value = i;
	}

	public void insert(Tree node) {
		if (this.value < node.value) {
			if (left == null)
				left.value = node.value;
			else
				left.insert(node);
		} else if (this.value > node.value) {
			if (right == null)
				right.value = node.value;
			else
				right.insert(node);
		} else if (this.value == node.value) {
			// Fehlermeldung
			throw new IllegalArgumentException();
		}
	}

	public void print() {
		System.out.println(value);
		if (left != null)
			left.print();
		if (right != null)
			right.print();
	}
}

import org.junit.Test;

public class TreeentryTest {

	@Test
	public void test() {
		int[] a = { 1, 2, 3, 4, 5 };
		Tree t = new Tree(3);
		t.print();
		t.insert(new Tree(1));
		t.print();
		t.insert(new Tree(2));
		t.print();
		t.insert(new Tree(3));
		t.print();
		t.insert(new Tree(4));
		t.print();

	}
}

 

[Xalker]

Lass bei insert das value weg.
left.value = node.value; => left = node;
right.value = node.value; => right = node;

	public void insert(Tree node) {
		if (this.value < node.value) {
			if (left == null) {
				left = node;
			} else
				left.insert(node);
		} else if (this.value > node.value) {
			if (right == null) {
				right = node;
			} else
				right.insert(node);
		} else if (this.value == node.value) {
			System.out.println("ungültiger Wert:" + node.value);
			throw new IllegalArgumentException();
		}
	}

Ob es korrekt ist, das bei fehlerhaften/doppelten Wert abgebrochen wird, weiß ich nicht.

Für eine bessere Ausgabe habe ich folgendes:

	public void print() {
		System.out.println("Node:" + value);

		if (left != null) {
			System.out.print("Left:");
			left.print();
		}

		if (right != null) {
			System.out.print("Right:");
			right.print();
		}
	}

 

[hüteüberhüte]

Warum

Tree node;

, was hat das für eine Bewandtnis?

 

[xyt4n]

Vielen Dank! Es funktioniert. Ich muss das Program jetzt so ändern, dass es ein sortiertes Feld als Baum ausgibt, hast du ein Tipp für mich?

Warum

Tree node;

, was hat das für eine Bewandtnis?

Wie meinst du das?

Edit: Also mir ist klar, dass ich ein Algorithmus brauche, der mir die Mitte des Arrays berechnet und ich muss es dann rekursiv auf die Klasse anwenden, aber ich weiß nicht wie ich das praktisch umsetzen soll.

 

[Xalker]

Ist jetzt aber dann ein anderer Ansatz:
(Ansatz übernommen aus Link Forum)

public class TreeentryTest {

	@Test
	public void test() {
		int[] a = { 1, 2, 3, 4, 5, 9 };
		int i;
		Tree root = new Tree(a[0]);

		LinkedList<Tree> listOfNodes = new LinkedList<Tree>();
		listOfNodes.add(root);

		boolean fertig = false;
		i = 1;
		while (!fertig) {
			LinkedList<Tree> tempList = (LinkedList<Tree>) listOfNodes.clone();
			for (Tree node : tempList) {
				listOfNodes.remove();

				// LEFT und RIGHT kann man noch etwas zusammenfassen, wenn man will       
				// LEFT
				if (i < a.length) {
					Tree tree = new Tree(a[i]);
					node.setLeft(tree);
					i++;
					listOfNodes.add(tree);
				}

				// RIGHT
				if (i < a.length) {
					Tree tree = new Tree(a[i]);
					node.setRight(tree);
					i++;
					listOfNodes.add(tree);
				}

				node.printTree();

				if (i >= a.length) {
					fertig = true;
					break;
				}
			}
		}
	}
}

public class Tree {
	private int value;
	private Tree left;
	private Tree right;

	public Tree(int value) {
		super();
		this.value = value;
		left = right = null;
	}

	public void printTree() {
		System.out.println("Node:" + value);

		if (left != null) {
			System.out.println("Left:" + left.value);
		}

		if (right != null) {
			System.out.println("Right:" + right.value);
		}
		
		System.out.println();
	}

	public Tree getLeft() {
		return left;
	}

	public void setLeft(Tree left) {
		this.left = left;
	}

	public Tree getRight() {
		return right;
	}

	public void setRight(Tree right) {
		this.right = right;
	}

}

 

[hüteüberhüte]

Wie meinst du das?

Wie, wie ich das meine?

Bis jetzt ist es ein Binärbaum, dessen Knoten/Blätter/Elemente aus Listen bestehen. Ist das gewünscht?

 

[JohannisderKaeufer]

Edit: Also mir ist klar, dass ich ein Algorithmus brauche, der mir die Mitte des Arrays berechnet und ich muss es dann rekursiv auf die Klasse anwenden, aber ich weiß nicht wie ich das praktisch umsetzen soll.

Ein erster Schritt hierzu ist es die Tiefe und das Gewicht des Baumes/der Teilbäume zu berechnen.