Graficul arbore este o structură comună de date în programare și este adesea folosită în algoritmi. Conținutul acestei structuri se pretează pentru a studia din greu în timpul de depanare, datorită faptului că aproape întotdeauna descris de către un singur nod care invoca descendenții lor. Ie pentru a obține valoarea unui anumit nod, trebuie să efectuați un traversal arbore netrivial. Și apoi o reprezentare vizuală a unui astfel de grafic poate ajunge la salvare. Construirea unui grafic într-o, nu este o sarcină banală compact și ușor de perceput de copac și este cu siguranță o mulțime de decizii. În articol aș vrea să împărtășesc propria mea "roată" pentru această sarcină.
Articolul presupune că în orice moment puteți obține informații despre descendenții unui anumit nod de copaci. Legăturile către un nod de strămoși nu sunt necesare, deoarece nu sunt prezente în toate reprezentările arborilor.
- Punct - descrie un punct cu coordonatele x și y;
- Dimensiune - descrie dimensiunea. Conține câmpuri de înălțime și lățime;
- Dreptunghi - descrie un dreptunghi cu dimensiunile și coordonatele colțului din stânga sus;
- TreeModel - descrie un copac. Vă permite să primiți descendenții și numărul lor pentru un anumit nod.
Principala cerință a algoritmului a fost numărul minim de traverse de copaci pentru a calcula coordonatele fiecărui nod.
Ideea soluției propuse este de a considera ca un descendent nu un nod separat, ci întregul copac pe care îl generează:
Introducem conceptul de "struguri". Un cluster este o structură de date care se referă la un nod de copaci și referințe la același "grup" care corespunde descendenților acelui nod.
Sarcina grupului este de a calcula parametrii localizării nodului la care se referă și de a calcula propriile dimensiuni.
De fapt, o grămadă este o hartă a plasării unui nod și a descendenților săi.
Crearea de fascicule și calcularea coordonatelor din colțul din stânga sus se realizează atunci când arborele este traversat recursiv în profunzime:
Pentru vizualizarea ideilor, ia în considerare exemplul calcularea coordonatelor descendenților nodului rădăcină 0. Algoritmul presupune că acest punct coordonatele nodurilor 4-10 au fost deja calculate, iar dimensiunile arborilor generate de nodurile 1, 2 și 3 sunt cunoscute (distanța orizontală dintre celulele din exemplul este egal cu 0 ):
