Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
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 ?
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...
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 ?
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 ?
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.
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
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++;
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...