Esta es una pregunta simple de la teoría de algoritmos. La diferencia entre ellos es que en un caso se cuenta el número de nodos y en otro número de bordes en el camino más corto entre el nodo raíz y el nodo concreto. ¿Cual es cual?¿Cuál es la diferencia entre la profundidad y la altura del árbol?
supe que la profundidad y la altura son propiedades de un nodo:
El profundidad de un nodo es el número de aristas desde el nodo a nodo raíz del árbol.
un nodo raíz tendrá una profundidad de 0.
El altura de un nodo es el número de aristas en la camino más largo desde el nodo a una hoja.
Un nodo hoja tendrá una altura de 0.
propiedades de un árbol :
El altura de un árbol sería la altura de su nodo raíz, o
de manera equivalente, la profundidad de su nodo más profundo.
El diámetro (o anchura) de un árbol es el número de nodos en el camino más largo entre dos nodos hoja. El árbol de abajo tiene un diámetro de 6 nodos.
+1 estaba a punto de agregar presupuesto con el mismo contenido desde aquí: http://en.wikipedia.org/wiki/Tree_%28data_structure%29 –
hmm Pensé que la terminología no es ambigua, sin embargo, gracias por el enlace. –
es que significa altura == profundidad máxima – roottraveller
Según Cormen et al. Introducción a los algoritmos (Apéndice B.5.3), la profundidad de un nodo X en un árbol T se define como la longitud de la ruta simple (número de bordes) desde el nodo raíz de T a X. La altura de un nodo Y es el número de aristas en el más largo sendero descendente simple de Y a una hoja. La altura de un árbol se define como la altura de su nodo raíz.
Tenga en cuenta que una ruta simple es una ruta sin repetir vértices.
La altura de un árboles igual a la profundidad máxima de un árbol. La profundidad de un nodo y la altura de un nodo no son necesariamente iguales. Ver la Figura B.6 de la 3ª Edición de Cormen et al. para una ilustración de estos conceptos.
A veces he visto problemas para que uno cuente nodos (vértices) en lugar de bordes, así que solicite una aclaración si no está seguro de contar los nodos o aristas durante un examen o una entrevista de trabajo.
¿Existe alguna diferencia en el recuento de nodos y bordes? Parece que ambos darán el mismo resultado. Corrígeme si estoy equivocado. –
Son diferentes, por ejemplo, si tiene un árbol binario, root-> left = b, root-> right = null, si cuenta edge, la profundidad de root es 1, si cuenta nodos, la profundidad de root será 2. – jdhao
respuesta simple:
Profundidad:
1. árbol: Número de bordes/arco desde el nodo raíz hasta el nodo hoja del árbol se llama como la profundidad del árbol.
2.Nodo: Número de aristas/arco desde el nodo raíz a ese nodo se llama como la Profundidad de ese nodo.
altura y la profundidad de un árbol es igual ...
pero la altura y la profundidad de un nodo no es igual porque ...
la altura se calcula por la que atraviesa desde el nodo dado a la más profunda posible hoja.
profundidad se calcula a partir de recorrido desde la raíz hasta el nodo dado .....
"la altura se calcula al atravesar desde la hoja hasta el nodo dado" no es correcta, la hoja debe ser la más profunda entre todas las hojas del nodo dado. – mightyWOZ
Otra manera de entender los conceptos es el siguiente: Profundidad: Dibujar una línea horizontal en la posición de la raíz y tratar esta línea como suelo. Entonces la profundidad de la raíz es 0, y todos sus hijos crecen hacia abajo para que cada nivel de nodos tenga la profundidad actual + 1.
Altura: La misma línea horizontal pero esta vez la posición de tierra son los nodos externos, que es el hoja de árbol y contar hacia arriba.
Quería hacer esta publicación porque soy estudiante de pregrado de CS y cada vez utilizo más OpenDSA y otros libros de texto de código abierto. Parece que la forma en que se enseña la altura y la profundidad ha cambiado de una generación a otra, y estoy publicando esto para que todos sepan que esta discrepancia ahora existe y que con suerte no causará errores en ninguna programas! Gracias.
Desde el OpenDSA Data Structures & Algos book:
Si n , n , ..., n k es una secuencia de nodos en el árbol de tal que n i es el matriz de n i 1 para 1 < = i < k, entonces esta secuencia se llama una ruta desde n a n k. La longitud de la ruta es k-1. Si hay una ruta desde el nodo R al nodo M, entonces R es un antecesor de M, y M es un descendiente de R. Por lo tanto, todos los nodos en el árbol son descendientes de la raíz del árbol, mientras que la raíz es el antecesor de todos los nodos. La profundidad de un nodo M en el árbol es la longitud de la ruta desde la raíz del árbol a M. La altura de un árbol es una más que la profundidad del nodo más profundo del árbol. Todos los nodos de profundidad d están en el nivel d en el árbol. La raíz es el único nodo en el nivel 0, y su profundidad es 0.
Figura 7.2.1: Un árbol binario. El nodo A es la raíz. Los nodos B y C son Los hijos de A. Los nodos B y D juntos forman un subárbol. El nodo B tiene dos hijos: su hijo izquierdo es el árbol vacío y su hijo derecho es D. Los nodos A, C y E son antepasados de G. Los nodos D, E y F componen el nivel 2 del árbol; el nodo A está en el nivel 0. Los bordes de A a C a E a G forman una ruta de longitud 3. Los nodos D, G, H e I son hojas. Los nodos A, B, C, E y F son nodos internos. La profundidad de I es 3. La altura de este árbol es 4.
Consejo: para evitar confusiones entre terminologías: 1. Altura: imagina medir la altura de una persona, lo hacemos de punta a cabeza (hoja a raíz). 2. Profundidad: imagina medir la profundidad de un mar, lo hacemos desde la superficie de la tierra hasta el fondo del océano (de la raíz a la hoja). – Yesh
@ Yesh Esta es una gran analogía. –