Binärbaum

[supermonkey]

Hallo!
Bin ein Java-Neuling und hab ein paar Fragen.
Ich muss als Aufgabe eine Knotenklasse, welche Nutzdaten und seine beiden Kinder enthält, erstellen.
Das hab ich so gelöst:

public class BinaryTree {

	/**
	 * The first node of the tree
	 */
	private BinaryTree first = null;
	private BinaryTree current = first;

	/**
	 * Node
	 */
	Friend friend;
	/**
	 * left child
	 */
	BinaryTree left;
	/**
	 * right child
	 */
	BinaryTree right;

	BinaryTree(Friend friend, BinaryTree left, BinaryTree right) {
		this.friend = friend;
		this.left = left;
		this.right = right;
	}
}

Nun ist die erste Aufgabe, eine Methode public boolean isLeaf() zu erstellen, die zeigt, ob ein Knoten ein Blatt ist. Da isLeaf() keinen Knoten überliefert bekommt, bin ich mir etwas unsicher. Hab das dann so gelöst:

public boolean isLeaf() {
		BinaryTree testNode = new BinaryTree(friend, left, right);
		if (testNode.left == null && testNode.right == null) {
			return true;
		} else {
			return false;
		}
	}

Ist das so korrekt? (bei testNode bin ich mir unsicher)

Und zu guter letzt noch eine Frage zu der Methode public int getNumberofNodes(), also Anzahl aller Knoten einschließlich der Wurzel. Da hab ich folgendes, bin mir aber sehr unsicher.

public int getNumberofNodes() {

		int counter = 1;

		if (current.right != null) {
			counter++;
			current = current.right;
			getNumberofNodes();
		}
		if (current.left != null) {
			counter++;
			current = current.left;
			getNumberofNodes();
		}

		current = first;
		return counter;
	}

Wäre super, wenn ihr mir eure Meinung sagt und mir Fehler zeigen könntet!

 

[faetzminator]

[c]isLeaf()[/c] kannst du einfach auf [c]this[/c] anwenden:

public boolean isLeaf() {
    return left == null && right == null;
}

Edit zum zweiten Problem: Machs einfach rekursiv:

public int getNumberofNodes() {
    int counter = 1;
    if (right != null) {
       counter += right.getNumberofNodes();
    }
    if (left != null) {
       counter += left.getNumberofNodes();
    }
    return counter;
}

[c]getNumberofNodes()[/c] muss dann einfach auf das Wurzelobjekt angewendet werden.

 

[supermonkey]

Danke! Ging ja schnell!

Waren meine beiden Ausführungen (also v.a. die zweite) eigtl. falsch oder nur umständlich?

 

[faetzminator]

Ich weiss nicht was du da versucht hast. Aber (zu) umständlich ist es sicher.

 

[supermonkey]

Jetzt hab ich noch eine Verständnisfrage. Hab in meinem Konstruktor ja folgendes geschrieben:

BinaryTree(Friend friend, BinaryTree left, BinaryTree right) {
        this.friend = friend;
        this.left = left;
        this.right = right;
    }

Müsst ich nicht aber this.left und this.right = null setzen? Denn ein neuer Knoten hat ja keine Nachfolger oder?
Aber funktioniert dann

public boolean isLeaf() {
    return left == null && right == null;
}

noch? Oder gibt mir die Methode dann imer true zurück?

 

[KrokoDiehl]

Zu deiner Frage:
Nein darfst du nicht null setzen, weil der Konstruktor dir den linken und rechten Teilbaum als Parameter liefert. D.h. du musst diese beiden Parameter auch entsprechend in deinem (neuen) Baum unterbringen. Sonst könnte man sie ja gleich weglassen.
Wenn du einen (weiteren) Konstruktor wie folgt einfügst:

public BinaryTree(Friend friend)

...sprich ohne left und right als Parameter, dann ist dieser neue Baum ein Blatt in dem Sinne, dass er keine Teilbäume hat. Sprich hier kann man die

this.left

und

this.right

nullen.

Aber andererseits kann man den anderen Konstruktor auch mit

BinaryTree meinBaum = new BinaryTree(friend, null, null);

aufrufen

 

[supermonkey]

Ok danke, habs verstanden!

Also brauch ich den andern Konstruktor für die Aufgaben von oben nicht zwingend oder?

 

[KrokoDiehl]

Zwingend nicht aber aus Verständlichkeitsgründen schon. Wenn ich einen Blattknoten anlegen will, würde ich eher einen Konstruktor á la

BinaryTree(Friend)

erwarten. Wenn ich indes eine Wurzel erstelle, würde ich eher etwas wie

BinaryTree(Friend, Left, Right)

erwarten.