Calcolo profondità e discendenti di albero

Question

Può voi ragazzi mi può aiutare con l'algoritmo per fare queste cose? Ho preorder, inorder, e postorder implementato, e mi sono dato il suggerimento per attraversare l'albero con uno di questi ordini. Sto usando Dotty di etichetta (o "visita"), i nodi.

La profondità è il numero di spigoli dalla radice alla foglia di fondo, così ogni volta che mi muovo, aggiungo uno alla profondità? Qualcosa del genere?

Non ho idea circa l'algoritmo per discendenti. Essi chiedono circa il numero di nodi un nodo specifico è sotto se stesso.

Si tratta di alberi normali btw.

Answer 1

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

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

Per entrambi, restituendo 0 per un puntatore nullo finirebbe ricorsione.

Answer 2

Si tratta di una domanda per compiti a casa? La mia risposta presuppone lo è per i compiti a casa.

Gli alberi sono una struttura dati ricorsiva, così gli algoritmi che operano su di essi saranno spesso ricorsiva. algoritmi ricorsivi bisogno di un caso base e un caso induttivo. Per gli alberi, il caso base sarà quello che si fa quando si sta visitando un nodo foglia (cioè un nodo senza figli). Il caso induttiva sarà quello che si fa quando si sta visitando un nodo interno (cioè un nodo con almeno un bambino).

Per calcolare la profondità (o "altezza" della struttura ad albero):

• Caso base:? Qual è la profondità di un nodo senza figli
• caso induttivo:? Dato che si hanno le profondità di tutti i tuoi figli (che può essere diverso), qual è la profondità del nodo corrente che si sta visitando

Per il calcolo conteggio discendente:

caso
• Base: Come molti discendenti fa un nodo senza figli hanno
• caso induttivo: Dato che si conosce il conteggio discendente di tutti i tuoi figli, che cosa è il conteggio discendente del nodo corrente che si sta visitando
?

vi incoraggio a chiedere chiarire le questioni.