Vous cherchez un mot pour « aplatir un arbre »

Question

Je me demande s'il y a un mot existant pour décrire un processus que je suis actuellement à l'aide. Je veux l'appeler «aplatir un arbre», mais j'ai l'impression qu'il doit y avoir un meilleur mot ou une meilleure expression.

entrée

:

|--D 
--B 
| |--C 
| 
A-E 
| 
| |--G 
--F 
    |--H 

sortie:

[ [A, B, D] 
    [A, B, C] 
    [A, E] 
    [A, F, G] 
    [A, F, H] ] 

Y at-il un nom établi pour ce processus?

Answer 1

de recensement Path?

DFS traversal?

ou mon préféré

Tree arrayfication!

Answer 2

Vous avez besoin d'une profondeur première recherche pour capturer tous les chemins de la racine à une feuille.

Code Pseudo:

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) 
} 

Answer 3

Je dirais que vous êtes juste traverser l'arbre, tout en gardant un chemin vers le noeud courant. Lorsque vous visitez une feuille, vous imprimez le chemin complet de la feuille.

Je ne pense pas qu'il y ait un nom spécifique, mais il est pas très différent d'un traversal très simple.

Answer 4

Que diriez-vous 'Hydratante' (ou à déshydrater) en fonction de la situation?

Answer 5

De-Normalisation semblerait être le meilleur. Car en effet, si vous remarquez votre nouvelle structure, vous avez des données redondantes, et il semblerait qu'elles correspondent directement à l'idée conceptuelle.

Answer 6

Que diriez-vous "scies à chaîne"

Answer 7

je pense à ce que coalescing parties de l'arbre.

Answer 8

Oui, il est appelé sérialisation

Answer 9

Si l'entrée est l'arbre et la sortie est la liste des listes que vous citez, vous ne cherchez pas vraiment une phrase pour le processus , vous Recherchez un nom pour le sous-programme que vous appelez. Et le nom d'un tel sous-programme devrait être une description de ce que renvoie.

Que diriez-vous de RootPathsOfLeaves? ou un réarrangement de celui-ci ...

Answer 10

Je viens de courir à travers un article wiki sur "Disjoint Sets" et le terme qu'il utilise est "compression de chemin".

Extrait:

... La deuxième amélioration, appelée chemin compression, est un moyen d'aplatissement la structure de l'arbre chaque fois que Find est utilisé à ce sujet. L'idée est que chaque nœud visité sur le chemin d'un nœud racine peut également être attaché directement au nœud racine; ils partagent tous le même représentant. Pour effectuer cela, lorsque Find parcourt récursivement l'arborescence , il modifie la référence parent de chaque nœud pour pointer vers la racine qu'il a trouvée . L'arbre qui en résulte est beaucoup plus plat, accélérant les opérations futures non seulement sur ces éléments mais sur ceux qui les référencent, directement ou directement par .