Berechnen der Tiefe und Nachkommen von Baum

Question

Könnt ihr mir helfen, mit dem Algorithmus, diese Dinge zu tun? Ich habe vorbestellen, inorder, und Postorder umgesetzt, und mir den Hinweis gegeben, den Baum mit einem diesen Aufträgen zu durchqueren. Ich bin mit Pünktchen zu Etikett (oder „Besuch“), um die Knoten.

Die Tiefe ist die Anzahl der Kanten von der Wurzel bis zur Unterseite Blatt, so jedes Mal wenn ich bewege, füge ich ein in die Tiefe? So etwas wie das?

Keine Ahnung von den Algorithmus für die Nachkommen. Sie fragen nach der Anzahl der Knoten einen bestimmten Knoten unter sich hat.

Das sind normale Bäume btw.

Answer 1

depth(tree) = 1+ max(depth(tree.left), depth(tree.right));

descendants(tree) = descendants(tree.left) + descendants(tree.right);

Für entweder Gibt 0 zurück für einen Null-Zeiger würde die Rekursion beenden.

Answer 2

Ist das eine Frage für die Hausaufgaben? Meine Antwort nimmt sie für die Hausaufgaben ist.

Bäume sind eine rekursive Datenstruktur, so dass die Algorithmen, die oft auf ihnen arbeiten wird rekursiv sein. Rekursive Algorithmen benötigen einen Basisfall und einen induktiven Fall. Für Bäume, wird der Basisfall sein, was Sie tun, wenn Sie einen Blattknoten besuchen (das heißt ein Knoten ohne Kinder). Der induktive Fall sein wird, was Sie tun, wenn Sie einen internen Knoten besuchen (das heißt ein Knoten mit mindestens einem Kind).

Tiefenberechnungs (oder "Höhe" des Baumes):

• Base Case: Was ist die Tiefe eines Knotens ohne Kinder
• Induktiv Fall: Da Sie die Tiefen aller Ihrer Kinder haben (was anders sein könnte), was die Tiefe des aktuellen Knotens ist Sie besuchen

Für Nachkommen Zählung Berechnung:

• Basisfall: Wie viele Nachkommen hat einen Knoten ohne Kinder haben
• Induktiv Fall: Da Sie den Nachkommen Anzahl aller Ihre Kinder wissen, was ist der Nachkomme Zählung der aktuellen Knotens Sie besuchen
?

Ich ermutige Sie Fragen zu klären stellen.