Binär-Baum Anzahl der Knoten mit einem bestimmten Maß
Ich muss ein Programm schreiben, dass zählt die Anzahl der Knoten ab einer bestimmten Stufe in binäre
Baum.
Ich meine < numberofnodes(int level){} >
Versuchte ich es schreiben, ohne jeglichen Erfolg, da ich nicht, wie man zu einem bestimmten Niveau, dann gehen
zur Anzahl der Knoten.
- Ist dieses Hausaufgaben? Was haben Sie bisher ausprobiert?
- Es klingt verdächtig nach Hausaufgaben an mich
- Wenn diese Hausaufgaben, markieren Sie Sie als solche. Was haben Sie zu tun versuchen?
- wissen Sie, wie Sie zählen Sie alle Knoten in einem binären Baum? Wenn ja, können Sie erweitern, dass dieses problem mit ein wenig extra etwas von tracking-Informationen. Wenn nicht, sollten Sie wahrscheinlich beginnen mit dem lernen, wie zu zählen Knoten in einem binären Baum.
- von der FAQ: "nicht eine Frage Bearbeiten, hinzufügen, um die Hausaufgaben-tag. Wenn es irgendeinen Zweifel, es ist am besten, lassen Sie es wie es ist." -
- Danke, werde ich unterlassen, das nächste mal. Als für diesen Beitrag, ich denke, die user können die Markierung entfernen, wenn es nicht die Hausaufgaben (was ich bezweifle)
- wahrscheinlich scheint (Hausaufgaben) zu mir. Trotzdem, lass dich nicht mobben Neulinge zu hart 🙂
- Ich glaube nicht, dass es wirklich ist definitiv ein Konsens (siehe Etikette auf retagging Fragen als Hausaufgabe). IMHO Fragen, die natürlich Aussehen wie eine Hausaufgabe kann als gut eingestuft werden als solche, und wenn es wirklich falsch ist die OP kann immer zurückgesetzt werden.
- danke für den link, ich habe nicht gesehen, dass man noch. Ich habe gerade vor kurzem sah (und beantwortet) eine Frage, die offensichtlich auch aussah, Hausaufgaben (ziemlich triviale Frage von einem offensichtlich ahnungslosen Mitmenschen), und erwies sich als eine echte Produktion der Aufgabe (nach OP). Also ich bin ein bisschen warier jetzt.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Tun Sie es mit einer rekursiven Funktion, die nur bis auf eine bestimmte Ebene.
Gut, es gibt viele Möglichkeiten, wie Sie dies tun können. Am besten ist, um einen eindimensionalen array, das verfolgen der Anzahl von Knoten, die Sie hinzufügen/entfernen auf jeder Ebene. Unter Berücksichtigung der Anforderung, dass wäre der einfachste Weg.
Jedoch, wenn die mit nur einem binären Baum, Sie haben zu Durchlaufen und gehen Sie zu viele Ebenen und zählen die Knoten, ich sehe keine andere alternative.
Gehen bis zu einem gewissen level, werden Sie normalerweise brauchen, um eine variable als "current_depth', die um die Ebene, die Sie sind in. Wenn Sie erreichen Ihr Interesse und, dass die Knoten nur einmal besucht (in der Regel ein um-traversal würde genügen) können Sie die Inkrement-Zählung. Hoffe, das half.
Gehe ich davon aus, dass Ihre binäre Baum ist nicht unbedingt vollständige (d.h. nicht jeder Knoten hat zwei oder null Kinder oder wird dies trivial). Ich gehe auch davon aus, dass Sie sollen zählen, nur die Knoten auf einer bestimmten Ebene, nicht auf diesem Niveau oder tiefer.
Gibt es viele Möglichkeiten, das zu tun, was Sie gefragt, aber Sie können denken, dies als ein graph search problem - Sie erhalten ein Startknoten (Wurzel des Baumes), einen Weg zu Durchlaufen Kanten (Kind links) und die Kriterien einer bestimmten Entfernung von der Wurzel.
Zu diesem Zeitpunkt haben Sie wahrscheinlich gelernt graph-such-algorithmen - Algorithmus klingt wie eine Natürliche fit für Ihre Aufgabe?
Allgemein:
Die Rekursion.
In jeder iteration der Rekursion, die Sie brauchen, um zu Messen, irgendwie das, was Ebene sind Sie an, und daher wissen, wie weit unten in der Struktur, die Sie brauchen, darüber hinaus zu gehen, wo Sie jetzt sind.
Rekursion-Teile:
Ich denke, der einfachste Weg ist, Folgen einfach die rekursive Natur des Baumes mit einem Akku zu verfolgen, das aktuelle Niveau (oder vielleicht die Anzahl der Ebenen, die übrigen abstammen).
Den nicht-rekursiven Zweig dieser Funktion, wenn Sie auf die Ebene in Frage. An diesem Punkt haben Sie einfach 1 zurück (weil Sie fanden einen Knoten auf dieser Ebene).
Den rekursiven Zweig, einfach die Summe der Anzahl der Knoten auf dieser Ebene werden zurückgegeben, die von der linken und rechten rekursive Aufrufe.
Dies ist der pseudo-code, dieser nimmt die Wurzel hat level 0
So, um die Anzahl der Knoten der Stufe 3 rufen Sie