Prezentacja drzewa binarnego za pomocą przeglądarki

Na laboratoriach z struktur danych tworzymy drzewo binarne, do prezentacji tego drzewa mieliśmy stworzyć prezentację semigraficzną. Taka prezentacja ma wadę  taką że w oknie konsoli zmieści się tylko mała ilość węzłów. Z moich szybkich szacowań w oknie konsoli nie zmieści się więcej niż 40 węzłów (trzeba zachować hierarchę etc.)

Miałem parę pomysł jak taki graficzną prezentacje zrobić:

• wykorzystać bibliotekę taką jak SDL i wykonać obliczenia pozycji węzłów ręcznie i je połączyć za pomocą lini.
• wykorzystać istniejące oprogramowanie takie jak: Graphviz
• szukać czegoś w związanego z przeglądarką

Pierwsze pomysł odrzuciłem ponieważ wymagał zbyt dużego poświęcenia czasu (programowanie odbywa się w późnych godzinach wieczornych), o drugim wtedy nie pamiętałem.

Wszedłem na Google i rozpocząłem poszukiwania, wiedząc że coś z javascriptem musi być.

Moja pewność była spowodowana znajomością pewnego prawa w oprogramowaniu.

 Atwood’s Law: any application that can be written in JavaScript, will eventually be written in JavaScript.

Rozpocząłem szukanie od strony Google Charts, przeszukałem wszystko i… nic odpowiedniego nie znalazłem, nie było nic tworzeniu grafów.

Niezrażony przeszukałem sieć pod kątem „graphs jquery”. i znalazłem! Ale… znaleziony biblioteki wydały mi się zbyt skomplikowane jak do takiego małego problemu, do wróbla nie strzela się z armaty.

Zawiedziony rozpocząłem na nowo przeszukiwania Google Charts teraz stawiąc na coś co raczej przypomina coś co chcę stworzyć.

W oko padło mi Org Charts (służące do pokazywania hierarchii wewnątrz firm).

Niemalże wszystkie Charts jako dostawcy danych korzystają z google.visualization.DataTable(); jako dostawcy danych do tabel, rysunków etc.

DataTable dla Org Charts może składać się 3 kolumn (o dowolnych nazwach):

• Pierwsza jest wymagana i posiada informacje o nazwie elementu. Ta nazwa musi być unikatowa wewnątrz całej tabeli. Można rozdzielić unikatową nazwę od nazwy wyświetlanej.
• Druga kolumna jest opcjonalna i posiada informacje od rodzicu
• Trzecia kolumna przechowuje tekst ToolTipa (informacji która się pojawia po najechaniu kursorem)

Wypełnienie danych w tabeli było proste, do póki nie doszło do wyświetlania 🙂

Chciałem aby wyświetlał się informacje o NULL’u (czyli że wskaźnik jakieś węzła nie posiada lewo/prawego potomka), a na stronie pokazywał się tylko jeden NULL.

Problemem było nie unikatowość NULL’a. Przypomniało mi się pewna rzecz z języka C#, tam aby coś miało unikalny identyfikator korzystało się z GUID’ów (jest implementacją UUID).

W C++ aby uzyskać GUID trzeba skorzystać z funkcji CoCreateGuid (która jest dostępna w za pomocą pliku nagłówkowego windows.h) w sposób następujący:

GUID guid
CoCreateGuid(&guid); 

Po wykonaniu tej funkcji struktura GUID zostaje zapełniona danymi. Kolejne części identyfikatora znajdują się w polach guid.Data1, guid.Data2, guid.Data3, guid.Data4.

I teraz dzięki unikalnemu GUID’owi oraz możliwości rozdzielenia unikalnego klucza oraz wyświetlanej nazwy, mogłem się cieszyć stroną internetową, która posiada hierarchię drzewa binarnego.

Przykłady wygenerowanych drzew:

Mała ilość danych, wartości wprowadzane z ręki

Dane losowe