Binärbäume knoten zählen

[Sandro95]

Guten Tag leute ,
ich benötige mal eure Hilfe und zwarhabe ich die Aufgabe bekommen in einem Binärenbaum die Knoten zu zählen .
Dabei hatte ich die idee , in der methode berechneKnotenanz eine zählervar. zu deklarieren, den Baum in in Order durchzulaufen und den zähler zu erhöhen.
Das läuft aberiwie nicht .. könnte mir vlt wer helfen ?

 

[mihe7]

Wenn Du einen beliebigen Knoten nimmst und diesen als Wurzel eines Baums betrachtest, dann ist die Anzahl der Knoten in diesem Baum gleich der Summe der Anzahl der Knoten im linken sowie rechten Teilbaum zzgl. 1 für den Wurzelknoten...

 

[Sandro95]

@mihe7
aber wie implementiere ich das am besten?
ich habe zb die methode public void berechneAnzKnoten(Node node){
den baum traversieren :

if(node!=null) {

traversInOrder(node.leftNode);
System.out.println(node.wert );
traversInOrder(node.rightNode);
}

und dann ?

 

[mihe7]

aber wie implementiere ich das am besten?

Genauso, wie ich es geschrieben habe.

int countNodes(Node node) {
    if (node == null) { return 0; }
    return 1 + countNodes(node.leftNode) + countNodes(node.rightNode);
}

 

[Sandro95]

ich verstehe deine schreib weise nicht ganz.
wenn kein node vorhanden wird 0 zurück gegeben klar.
aber sonst? verstehe ich nicht ganz @mihe7

 

[insert2020]

Man könnte den Spaß noch etwas optimieren.

int countNodes(Node node) {
    int i = (node.leftNode == null ? 0 : 1) + (node.rightNode == null ? 0 : 1);
    if (node.leftNode != null)
        i +=  countNodes(node.leftNode);
    if (node.rightNode != null)
        i +=  countNodes(node.rightNode);
    return i;
}

 

[Sandro95]

@insert2020 "
int i = (node.leftNode == null ? 0 : 1) + (node.rightNode == null ? 0 : 1);


"

wie habe ich die zeile zu verstehen ? so eine schreibweise ist mir neu hatte ich bis dato noch nicht in der uni

 

[TM69]

Guten Tag leute ,
ich benötige mal eure Hilfe und zwarhabe ich die Aufgabe bekommen in einem Binärenbaum die Knoten zu zählen .
Dabei hatte ich die idee , in der methode berechneKnotenanz eine zählervar. zu deklarieren, den Baum in in Order durchzulaufen und den zähler zu erhöhen.
Das läuft aberiwie nicht .. könnte mir vlt wer helfen ?

Man kann es auch noch ganz einfacher haben, wie z.B. Nested Sets bei Datenbanken. http://www.klempert.de/nested_sets/

 

[affot]

wie habe ich die zeile zu verstehen ? so eine schreibweise ist mir neu hatte ich bis dato noch nicht in der uni

Das ist eine verkürzte Schreibweise, aber genau das gleiche wie ne IF-Anweisung.

int i
if(node.leftNode == null){
    i=0;
}else{
    i=1;
}

 

[mihe7]

ich verstehe deine schreib weise nicht ganz.
wenn kein node vorhanden wird 0 zurück gegeben klar.
aber sonst? verstehe ich nicht ganz @mihe7

Was verstehst Du nicht?

 

[insert2020]

Ich hab da noch ein +1 vergessen...

wie habe ich die zeile zu verstehen ? so eine schreibweise ist mir neu hatte ich bis dato noch nicht in der uni

Das liest sich folgendermaßen: Zähle die Anzahl der direkten Kinder und weise sie der Variablen i zu...

 

[Sandro95]

ich danke euch für eure Hilfe ! aber @affot wenn ich i=1 zuweise im else , dann addiere ich die Nodes doch nicht hinzu sondern sage immer wieder das i =1 ist ?

 

[affot]

ich danke euch für eure Hilfe ! aber @affot wenn ich i=1 zuweise im else , dann addiere ich die Nodes doch nicht hinzu sondern sage immer wieder das i =1 ist ?

Oh, ja da habe ich das + übersehen.
Also nochmal anders ausgedrückt, der Ausdruck macht einfach nur:
Bedingung=true ? JA : NEIN

Das heißt wenn links und rechts != null, dann steht doch 1 + 1, wenn links = null dann 1 + 0 und wenn beide = null dann 0 + 0.
Und das wird halt i zugewiesen.

 

[mihe7]

Das heißt wenn links und rechts != null, dann steht doch 1 + 1, wenn links = null dann 1 + 0 und wenn beide = null dann 0 + 0.
Und das wird halt i zugewiesen.

Ja. Mal ein einfaches, leicht verkürztes Beispiel einer rekursiven Funktion.

public int f(int x) {
    if (x <= 1) return 1;
    return x*f(x-1);
}

Was passiert, wenn Du f(4) aufrufst? Naja, es wird das Ergebnis von 4*f(3) zurückgegeben. Um das Ergebnis zu berechnen bräuchten wir f(3)... das wiederum das Ergebnis von 3*f(2) ist. f(2) .. Ergebnis von 2*f(1). f(1)? Ah, ist 1. Und jetzt können wir die Ergebnisse wieder berechnen:
f(2) = 2*f(1) = 2*1 = 2
f(3) = 3*f(2) = 3*2 = 6
f(4) = 4*f(3) = 4*6 = 24

Genau das gleiche passiert beim Zählen der Knoten. Nehmen wir mal einen Baum an, wie unter https://de.wikipedia.org/wiki/Binärbaum#/media/Datei:Binary_tree_array_indices.svg gezeigt.

Wenn Du countNodes für Knoten 1 aufrufst, was berechnet die Funktion?

countNodes(n1) = 1 + countNodes(n2) + countNodes(n3)

Was liefert countNodes(n2)?

countNodes(n2) = 1 + countNodes(n4) + countNodes(n5)
countNodes(n4) = 1 + countNodes(null) + countNodes(null) = 1+0+0 = 1
countNodes(n5) = 1 + countNodes(null) + countNodes(null) = 1+0+0 = 1
Damit ist countNodes(n2) = 1 + 1 + 1 = 3

Somit wird aus countNodes(n1) = 1 + countNodes(n2) + countNodes(n3) schon einmal countNodes(n1) = 1 + 3 + countNodes(n3).

Was liefert countNodes(n3)?

countNodes(n3) = 1 + countNodes(n6) + countNodes(n7)
countNodes(n6) = 1 + countNodes(null) + countNodes(null) = 1+0+0 = 1
countNodes(n7) = 1 + countNodes(null) + countNodes(null) = 1+0+0 = 1

Damit ist countNodes(n3) = 1 + 1 + 1 = 3

Somit wird aus countNodes(n1) = 1 + 3 + countNodes(n3) = 1 + 3 + 3 = 7.

Was das i von @insert2020 betrifft: das ist eine lokale Variable, die für jeden Aufruf der Funktion separat existiert.

 

[insert2020]

Schauen wir uns die Methode nochmal im Detail an... Man hätte sie auch so schreiben können:

public class Node {
	Node left, right;

	public Node(Node l, Node r) {
		left = l;
		right = r;
	}

	int countChilds() {
		boolean downwardsLeft = left != null;
		boolean downwardsRight = right != null;
		int i = (downwardsLeft ? 1 : 0) + (downwardsRight ? 1 : 0);
		if (downwardsLeft)
			i += left.countChilds();
		if (downwardsRight)
			i += right.countChilds();
		return i;
	}

	public static void main(String[] args) {
		Node root = new Node(new Node(null, null), new Node(new Node(new Node(null, new Node(null, null)), null), null));
		// there are 6 times "new"...
		System.out.println(root.countChilds() + 1);
	}
}

Jetzt ist hoffentlich mal ersichtlich, wie sie funktioniert: Für einen aktuellen Knoten wird die Anzahl aller Kinder berechnet...

Aus diesem verrückten Konstrukt int i = (downwardsLeft ? 1 : 0) + (downwardsRight ? 1 : 0);, würde der Compiler wohl so etwas machen:

		int i = 0;
		if (downwardsLeft)
			i++;
		if (downwardsRight)
			i++;

also wenig Zauberei...

 

[Sandro95]

@mihe7 @insert2020 ich danke euch für eure Hilfe jetzt ist mr das ganze schon viel klarer geworden

 

[insert2020]

hatte ich bis dato noch nicht in der uni

Kein Problem. Jetzt hast du 1ne Aufgabe, da kommen noch 99 andere Aufgaben zu Binärbäumen und dann haste es geschafft.
Aber tröste dich, du wirst sukzessive besser darin, da die Aufgaben aufeinander aufbauen...
Zu fragen ist nicht schlimm, nur gibt es genau diese Frage bestimmt schon 100mal...