Hallar el diámetro de un árbol - c ++, algoritmo, árbol

He escrito un código para encontrar el diámetro del árbol binario. Pero soy incapaz de averiguar dónde va mal. Las dos funciones que he escrito y su definición son las siguientes:

    int btree::diameteroftree(node* leaf)
{
if (leaf==NULL)
return 0;

int lheight = hieghtoftree(leaf->left);
int rheight = hieghtoftree(leaf->right);

int ldiameter = diameteroftree(leaf->left);
int rdiameter = diameteroftree(leaf->right);

return max(lheight + rheight + 1,max(ldiameter,rdiameter));
}


int btree::hieghtoftree(node* leaf)
{
int left=0,right=0;
if(leaf==NULL)
return -1;
else
{
left=hieghtoftree(leaf->left);
right=hieghtoftree(leaf->right);
if(left > right)
return left +1;
else
return right+1;
}
}

No puedo averiguar a dónde me voy mal aquí. Alguien me puede dejar saber ...

Respuestas

1 para la respuesta № 1

Desea devolver el número de nodos en la ruta más larga. Por lo tanto, el problema en su algoritmo es esta línea:

return max(lheight + rheight + 1,max(ldiameter,rdiameter));

dónde

rootDiameter = lheight + rheight + 1

es la longitud del camino desde el nodo más profundoDel árbol izquierdo al nodo más profundo del árbol derecho. Sin embargo, este cálculo no es correcto. Un solo nodo devuelve una altura de 0, por lo que no se contabilizará. Tienes dos opciones:

1. Cambio hieghtoftree para devolver el número de nodos en la ruta más profunda y no el número de "saltos"
2. Abordar este problema en su resumen

.

return max(lheight + rheight + 3,max(ldiameter,rdiameter));

---

0 para la respuesta № 2

En un árbol dirigido y enraizado, siempre hay como máximo una ruta entre cualquier par de nodos y la ruta más larga a cualquier nodo siempre comienza en la raíz. Se deduce que el diámetro Es simplemente la altura de todo el árbol. height(root), que se puede computar con la recursividad.

height(leaf) = 0
height(node) = max(height(node.left), height(node.right)) + 1

EDITAR: la página a la que te vinculas en el comentario describe el diámetro de un no dirigido árbol. Necesita una representación de árbol diferente, por ejemplo, Una matriz de adyacencia.

---

0 para la respuesta № 3

Considere un árbol de 3 nodos con raíz R y 2 hojas L1, L2. Luego heightoftree (L1) == heightoftree (L2) == -1. Por lo tanto, Diameteroftree (R) sería (-1) + (- 1) +1 = -1?!?

Sugiero devolver -1; -> return 0; y devuelve max (lheight + rheight + 1, max (ldiameter, rdiameter)); -> devolver max (lheight + rheight + 2, max (ldiameter, rdiameter));

El resultado sería el número de bordes en el camino. Si cuenta el número de nodos, agregue uno o reste uno del resultado final de acuerdo con su necesidad.

---