Calcul de la profondeur et des descendants de l'arbre

Question

Pouvez-vous m'aider avec l'algorithme pour faire ces choses? J'ai préordonné, inorder, et postorder mis en œuvre, et je suis donné l'indice de traverser l'arbre avec l'un de ces ordres. J'utilise dotty pour étiqueter (ou "visiter") les nœuds.

La profondeur est le nombre d'arêtes de la racine à la feuille du bas, donc à chaque fois que je bouge, j'ajoute +1 à la profondeur? Quelque chose comme ca?

Aucune idée de l'algorithme pour les descendants. Ils posent des questions sur le nombre de nœuds qu'un nœud 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 l'un ou pour l'autre, renvoyer 0 pour un pointeur null terminerait la récursivité.

Answer 2

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

Les arbres sont une structure de données récursive, de sorte que les algorithmes qui fonctionnent sur eux sont souvent récursifs. Les algorithmes récursifs nécessitent un cas de base et un cas inductif. Pour les arbres, le scénario de base correspond à ce que vous faites lorsque vous visitez un nœud feuille (c'est-à-dire un nœud sans enfants). Le cas inductif sera ce que vous faites lorsque vous visitez un noeud interne (c'est-à-dire un noeud avec au moins un enfant).

Pour calculer la profondeur (ou « hauteur » de l'arbre):

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

Pour le calcul descendant nombre:

• cas de base: Combien de descendants d'un noeud ne sans enfants ont?
• Cas inductif: Étant donné que vous connaissez le nombre de descendants de tous vos enfants, quel est le nombre de descendant du noeud actuel que vous visitez?

Je vous encourage à poser des questions de clarification.