Bibliothèque Java ou un algorithme pour le calcul des coordonnées des noeuds d'arbres / dessin

Question

Je cherche une bibliothèque qui me donnerait les les coordonnées exactes de chaque noeud dans un arbre (un arbre, pas seulement les arbres binaires).

Le mot Let je définir l'arbre dans la notation suivante

(() (() (() () ())) 

Et une bibliothèque me donne les coordonnées comme ceci:

[500 0]([200 50]() [600 50]([500 100]() [750 100]([600 150]() [700 150]() [800 150]())) 

ou toute autre notation qui représente de manière unique un arbre.

Ce genre de bibliothèque permettrait à un dessin efficace l'espace des arbres et résoudrait aussi le problème des nœuds et des liens qui se chevauchent. Par exemple, si un arbre est une liste enfait, je voudrais que la bibliothèque pour en tenir compte et organiser des noeuds dans une seule colonne ou une ligne, pour économiser l'espace.

Si rien n'existe similaire, un algorithme serait également utile , à condition qu'il puisse être mis en œuvre relativement facilement.

Answer 1

Je pense que le Nested Set modèle de peut vous aider.

L'algorithme est assez simple et très efficace pour les lectures, bien mises à jour de l'arbre sont un peu plus cher, parce que les limites des nœuds doivent être mis à jour de façon en cascade. Voici l'algorithme implémenté dans SQL .