Binärbäume knoten zählen

Diskutiere Binärbäume knoten zählen im Java Basics - Anfänger-Themen Bereich.
S

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

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...
 
S

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 ?
 
S

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
 
I

insert2020

Man könnte den Spaß noch etwas optimieren. ;)
Java:
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;
}
 
S

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
 
T

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/
 
A

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.

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

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 ?
 
A

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

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.
Java:
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.
 
I

insert2020

Schauen wir uns die Methode nochmal im Detail an... Man hätte sie auch so schreiben können:
Java:
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:
Java:
		int i = 0;
		if (downwardsLeft)
			i++;
		if (downwardsRight)
			i++;
also wenig Zauberei...
 
I

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... :D
 
Thema: 

Binärbäume knoten zählen

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben