Me pregunto si hay una palabra existente para describir un proceso que estoy usando actualmente. Quiero llamarlo "aplanamiento de un árbol", pero siento que debe haber una palabra o frase mejor.Buscando una palabra para "aplanamiento de un árbol"
de entrada:
|--D
--B
| |--C
|
A-E
|
| |--G
--F
|--H
de salida:
[ [A, B, D]
[A, B, C]
[A, E]
[A, F, G]
[A, F, H] ]
¿Hay un nombre establecido para este proceso?
Enumeración de rutas?
DFS transversal?
o mi favorito
arrayfication árbol!
Parece una enumeración de todas las rutas, por lo que la "enumeración de ruta" parece encajar. –
Necesita una primera búsqueda en profundidad para capturar cada ruta desde la raíz hasta una hoja.
pseudo código:
global allPaths = []
R = root
currentPath = []
findPaths(R, currentPath)
findPaths(R, currentPath){
if R has no children,
allPaths.add(currentPath)
else
for each child C in R:
findPaths(C, currentPath + R)
}
yo diría que sólo estás recorriendo el árbol, mientras se mantiene una ruta de acceso al nodo actual. Cuando visitas una hoja, imprimes el camino completo a la hoja.
No creo que haya un nombre específico, pero no es muy diferente de un recorrido muy simple.
¿Qué tal 'Hidratación' (o DeHydrating) según la situación?
No estoy seguro de que un libro de texto enumere eso, pero +1 para el envío real de un 'nombre' :-) –
@pst - ¡¡¡muy apreciado !! – SoftwareGeek
aparentemente algunos cobardes han votado negativamente. ¡qué noche! – SoftwareGeek
De-Normalisation parece ser lo mejor. Porque de hecho, si observas tu nueva estructura, tienes datos redundantes y parece que se correlaciona directamente con la idea conceptual.
¿Qué tal "Chainsawing"
Lo considero como coalescing partes del árbol.
Sí, se llama números de serie a
Si la entrada es el árbol y la salida es la lista de listas que usted cita, usted no está realmente buscando una frase para el proceso, se Estamos buscando un nombre para la subrutina al que llamas. Y el nombre de dicha subrutina debe ser una descripción de lo que devuelve.
¿Qué tal RootPathsOfLeaves? o alguna reorganización de la misma ...
Acabo de encontrar un artículo de wiki en "Disjoint Sets" y el término que utiliza es "compresión de ruta".
Extracto:
... La segunda mejora, llamada ruta de compresión , es una forma de aplanar la estructura del árbol cada vez que se usa Buscar. La idea es que cada nodo visitado en el camino a un nodo raíz también se puede adjuntar directamente al nodo raíz; todos comparten el mismo representante . Para efectuar esto, como Buscar recorre recursivamente el árbol , cambia la referencia primaria de cada nodo para que apunte a la raíz que se encontró . El árbol resultante es mucho más plano que el , lo que acelera las operaciones futuras no solo en estos elementos, sino también en los que los referencian, directamente o indirectamente.
Fabricación de madera contrachapada? –
+1 - el idioma es importante para expresar ideas, señalar el esfuerzo. – SoftwareGeek