El cálculo de la profundidad y descendientes de árbol

Question

Pueden ustedes ayudarme con el algoritmo para hacer estas cosas? Tengo orden previo, a finde, y la orden posterior implementado, y se me da la pista para recorrer el árbol con una de estas órdenes. Estoy usando manchada de etiqueta (o "visita") los nodos.

La profundidad es el número de aristas de la raíz a la hoja inferior, por lo que cada vez que me muevo, añadir 1 a la profundidad? Algo por el estilo?

Ni idea sobre el algoritmo para los descendientes. Están preguntando por el número de nodos de un nodo específico tiene debajo de sí mismo.

Estos son los árboles normales por cierto.

Answer 1

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

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

Para cualquiera, volviendo 0 para un puntero nulo pondría fin a la recursión.

Answer 2

Es una pregunta para hacer la tarea? Mi respuesta supone que es para hacer la tarea.

Los árboles son una estructura de datos recursivo, por lo que los algoritmos que operan en ellos a menudo será recursivo. algoritmos recursivos necesitan un caso base y un caso inductivo. Para los árboles, el caso base será lo que se hace cuando va a visitar un nodo hoja (es decir, un nodo sin hijos). El caso inductivo será lo que se hace cuando va a visitar un nodo interno (es decir, un nodo con al menos un hijo).

Para el cálculo de la profundidad (o "altura" del árbol):

• Caso base: ¿Cuál es la profundidad de un nodo sin hijos
• caso inductivo: Teniendo en cuenta que usted tiene las profundidades de todos sus hijos (que puede ser diferente), ¿cuál es la profundidad del nodo actual que está visitando

Para el cálculo de conteo descendiente:

caso
• Base:? Cuántos descendientes hace un nodo sin hijos tiene
• caso inductivo: Dado que usted conoce el recuento descendiente de todos sus hijos, lo que es el conteo descendiente del nodo actual que está visitando
?

Los animo a hacer preguntas aclaratorias.