Calcul de la profondeur et les descendants d'arbres

Question

Pouvez-vous les gars me aider avec l'algorithme de faire ces choses? Je précommande, afinde et postorder mis en œuvre, et je me donne l'indice de traverser l'arbre avec une de ces commandes. J'utilise Dotty l'étiquette (ou « visite ») les noeuds.

La profondeur est le nombre d'arêtes de la racine à la feuille de fond, donc à chaque fois que je propose, j'ajoute +1 à la profondeur? Quelque chose comme ça?

Aucune idée de l'algorithme pour les descendants. Ils demandent le nombre de noeuds d'un noeud spécifique a sous lui-même.

Ce sont des arbres normaux btw.

Answer 1

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

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

Pour les deux, le retour 0 pour un pointeur NULL mettrait fin à la récursivité.

Answer 2

Est-ce une question pour les devoirs? Ma réponse suppose qu'il est pour les devoirs.

Les arbres sont une structure de données récursive, de sorte que les algorithmes qui fonctionnent sur eux seront souvent récursive. algorithmes récursifs ont besoin d'un cas de base et un cas inductif. Pour les arbres, le cas de base sera ce que vous faites lorsque vous visitez un nœud feuille (à savoir un noeud sans enfant). Le cas inductif sera ce que vous faites lorsque vous visitez un noeud interne (à savoir un noeud avec au moins un enfant).

Pour la profondeur de calcul (ou "hauteur" de l'arbre):

• Cas de base: Quelle est la profondeur d'un nœud sans enfant
• cas inductive: Étant donné que vous avez les profondeurs de tous vos enfants (qui pourrait être différente), quelle est la profondeur du nœud actuel que vous visitez

Pour calculer le nombre descendant:

• Cas de base: Combien de descendants d'un noeud sans ne les enfants ont
• cas inductive: Compte tenu de ce que vous connaissez le nombre descendant de tous vos enfants, le nombre de descendants du noeud courant que vous visitez
?

Je vous encourage à demander des éclaircissements.