Generic Class NET zawiera wiele klas generycznych. Do pokazania, definiowania własnych klas generycznych używa się często tego samego przykładu: drzew binarnych. Nie ma takiej klasy w .NET, która zachowywałaby się jak drzewa binarne. Tak jak powiedziałem wcześniej ten przykład jest często używany, więc nie widzę powodu abym sam tego nie zrobił. Jednak zanim przejdziemy do tworzenia klasy generycznej najpierw opowiem trochę o drzewach binarnych.
Teoria binarnych drzew
Drzewo binarne jest użyteczną strukturą danych, korzysta się z niej w wielu operacjach, włączając w to sortowanie i szybkie wyszukiwanie informacji.
Drzewo binarne jest to rekursywna (*samo-referująca się”) struktura danych, która może być pusta albo zawierać trzy elementy odniesienia. Są referowane jako węzeł (node) z dwóch poddrzew, które są właśnie drzewami binarnymi.
Dwa poddrzewa, to lewe poddrzewo i prawe poddrzewo, ponieważ są rozłączne na dwa kierunki.
Każde poddrzewo jest albo puste, albo zawiera węzeł i inne poddrzewa. W teorii ta struktura może być nieskończona.
Prawdziwa potęga drzew binarnych jest wykazana przy sortowaniu informacji. Jeśli rozpoczniesz z nie ustawioną sekwencją obiektów tego samego typu, możesz jest ustawić w postaci drzewa binarnego, a potem spacerować po drzewie odwiedzając każdy węzeł w ustawionej sekwencji. 
Nie ma to związku z tematem, ale patrząc na te drzewa binarne przypomina mi się teleturniej polsatu drzewko szczęścia. Oglądałem go, gdy byłem w podstawówce. Po każdej poprawnej odpowiedzi uczestnik musiał wybrać właściwe poddrzewo, mając 50% szansy na granie dalej.
Algorytm umieszczenia elementu X w ustawionym drzewie binarnym jest pokazany poniżej:
Zauważ, że algorytm ten jest rekursywny, wywołuje sam siebie po umieszczeniu elementu w lewym, bądź w prawym poddrzewie, w zależności od wartości elementu. Element ten jest porównywany z obecnym węzłem. Jeśli algorytm jest niezrozumiały, nie martw się opisałem krok po kroku, jak go zaimplementować w najprostszy sposób. 
Definicja wyrażenie “większe niż” zależy od typu danych. Dla numerycznej informacji sprawa jest łatwa, to prosta operacja arytmetyczna, która może być nawet wykonana przez człowieka. Dla danych tekstowych oraz innych już tak nie jest. Porównywanie obiektów w .NET wymaga dwóch interfejsów System.IComparable i System.IComparable<T>. O czym opowiem później.
Jeśli zaczynasz z pustym drzewem binarnym i masz nieułożoną sekwencję obiektów, możesz wykonać iteracje w nieposortowanej sekwencji, umieszczając każdy obiekt w drzewie binarnym, używając określonego algorytmu, który wykona posortowanie drzewa. Następny rysunek pokazuje proces konstruowania drzewa z zestawu pięciu liczb całkowitych. Robiąc rysunek w illustratorze dwa razy narysowałem trzeci etap, więc go wyciąłem. 
Gdy już zbudowałeś drzewo, możesz wyświetlić jego zawartość w sekwencji odwiedzenia każdego węzła w turze i wydrukowaniu znalezionej wartości. Algorytm ten też jest rekursywny.
Następujący obrazek pokazuje kroki procesu odczytywania drzewa. Zauważ, że liczby są wyświetlane w rosnącej kolejności. 
Budowanie klasy binarnego drzewa używając Generics
Tyle, jeżeli chodzi o teorię. Czy można zbudować w C# klasę, która reprezentowałaby drzewo binarne niezależne od typu danych? Oczywiście, że się da zrobić. Prawdopodobnie największą przeszkodą będzie porównywanie wartości.
Klasa binarnego drzewa może się sprawdzić w wielu innych aplikacjach. Dlatego zaimplementuje ją, jako projekt biblioteki klas, a nie własną aplikację. Dzięki temu później klasa może być używana w innym miejscu, bez potrzeby ponownej kompilacji. Projekt biblioteki klas jest to zestaw skompilowanych klas, struktur, delegat i tak dalej, w jednej bibliotece. Biblioteka (assembly) jest to plik mający rozszerzenie .dll. Inne projekty i aplikacje będą mogły korzystać z elementów tej biblioteki poprzez dodanie do niej referencji i używania jej przestrzeni nazw.
To też zrobię, w końcu trzeba przetestować klasę binarnego drzewa.
Interfejs System.IComparable i System.IComparable<T>
Algorytm umieszczania węzłów w drzewie binarnym wymaga porównywania wartości w węźle, który już istnieje, i w którym chcemy umieścić wartość. W tym przykładzie użyję typów liczbowych, a one mogą być porównywane za pomocą operatorów (< ,>, ==) . Jednak sprawa naprawdę komplikuje się, gdy używam swoich własnych obiektów.
Jeżeli istnieje potrzeba użycia swojej klasy, wymaga ona porównywania wartości zgodnie z jakąś naturalną zasadą, bądź nie, poprzez implementacje interfejsu IComparable. Ten interfejs zawiera metodę, która nazwa się CompareTo() . Pobiera ona tylko jeden parametr zależny od specyficznego obiektu i jest on porównywany z obecną instancją, zwraca liczbę całkowitą, która informuje o przebiegu porównywania.
| Wartość | Znaczenie |
| Mniejsza niż 0 | Obecna instancja jest mniejsza od wartości danego parametru |
| 0 | Obecna instancja jest równa z wartością danego parametru |
| Większa niż 0 | Obecna instancja jest większa niż wartość danego parametru |
Oto prosty przykład klasy Cuboid, czyli prostopadłościanu.’'
class Cuboid
{
public Cuboid(int a,int b,int c)
{
this.a = a;
this.b = b;
this.c = c;
}
public int Volume()
{
return a * b * c;
}
private int a;
private int b;
private int c;
}Prostopadłościan posiada 3 wartości więc powinien być porównywany według objętości . Prostopadłościan o większej objętości będzie traktowany jako większy od prostopadłościanu o mniejszej objętości.
internal class Cuboid : System.IComparable
{
public int CompareTo(object obj)
{
Cuboid cu2 = obj as Cuboid;
if (this.Volume() == cu2.Volume())
return 0;
if (this.Volume > cu2.Volume())
return 1;
return -1;
}
public Cuboid(int a, int b, int c)
{
this.a = a;
this.b = b;
this.c = c;
}
public int Volume()
{
return a * b * c;
}
private int a;
private int b;
private int c;
}Implementując interfejs IComparable zauważysz, że definiuje ona parametr jako object. Nie jest to bezpieczne typowo. Aby to zrozumieć wystarczy wyobrazić sobie, co się stanie, jeśli umieścisz w metodzie inny obiekt niż Cuboid. Do użycia metody Volume() trzeba byłoby użyć rzutowania, ale co będzie, jeśli się ono błędnie wykona. W tym wypadku zmienna cu2 będzie miała pustą referencje.
Na szczęście przestrzeń nazw System oferuje podobny interfejs generyczny IComparable<T> , który posiada metodę int ComapreTo (T other)
Metoda ta ma parametr typu T, jest bezpieczniejsza w użyciu, niż jej niegeneryczna wersja. Oto implementacja tego interfejsu.
C#class Cuboid : System.IComparable<Cuboid>
{
public int CompareTo(Cuboid other)
{
if (this.Volume() == other.Volume())
return 0;
if (this.Volume > other.Volume())
return 1;
return -1;
} Parametr dla metody ComapreTo musi być zgodny z typem określonym w interfejsie IComparable<Cuboid>. Zasadniczo lepszy jest ten interfejs, ale możesz zaimplementować oba. Wiele typów z .NET tak robi.
Tworzenie klasy Tree of T
Co robić, kiedy chcemy napisać jakiś nowy projekt w C#? Otwieramy Visual Studio 2010 klikamy na nowy projekt i wybieramy z listy projektów “Class Library”. 
Projekt, a raczej bibliotekę trzeba nazwać normalnie. Nazwa “BinaryTree” dobrze opisuje projekt i bibliotekę. 
W Solution Explorer trzeba zmienić nazwę klasy pliku na Tree.cs. Visual Studio powinien zmienić też nazwę klasy.
Aby użyć magii typu T, na początek trzeba dodać do definicji właśnie ten typ z jego nazwą niekoniecznie T, może np. TItem.
public class Tree<TItem>{ }Do tej klasy będzie potrzebny interfejs IComparable od T , który musi łączyć się z naszym typem T. Nie trzeba go implementować, ten fragment pozwala nam na użycie każdego typu danych, musi on jednak implementować ten interfejs i, mimo iż nie znamy jego typu. W tym kodzie będziemy mogli skorzystać z jego metody CompareTo(). Jest możliwe dzięki magii słowa kluczowego where.
public class Tree<TItem> where TItem: IComparable<TItem>
{
}Następnie trzeba dodać automatyczne właściwości, które są typami od T. Drzewo działa rekursywnie, więc klasa zawierać będzie dwie właściwości, które są klasami generycznymi Tree, czyli są to poddrzewa, które mogą mieć kolejne drzewa. Każde drzewo oprócz lewego i prawego poddrzewa zawiera jeszcze wartość obiektu, w naszym przypadku jest to typ T, czyli TItem.
public class Tree<TItem> where TItem: IComparable<TItem>
{
public TItem NodeData { get; set; }
public Tree<TItem> LeftTree { get; set; }
public Tree<TItem> RightTree { get; set; }
}Co jeszcze musi mieć ta klasa.? Konstruktor. Konstruktor będzie pobierał tylko wartość węzła. Pozostałe właściwości oznaczające poddrzewa będą puste, czyli null. Zauważ, że konstruktor jest wywoływany bez typu parametru.
public Tree(TItem nodeValue)
{
this.NodeData = nodeValue;
this.LeftTree = null;
this.RightTree = null;
}Powoli trzeba implementować kod, który pozwali na dodanie poddrzew zgodnie z algorytmem. Najpierw napiszę definicję metody, która powinna pobierać wartość węzła, który jest typu TItem.
public void Insert(TItem newItem)
{
}Metoda Insert implementuje rekursywny algorytm opisany wcześniej w tym wpisie. Programista użyje konstruktora do zainicjowania nowego węzła (nie ma tutaj domyślnego konstruktora), więc metoda Insert będzie zakładać, że drzewo nie ma pustego węzła. Część algorytmu, dla przypomnienia wygląda tak:
Metoda Insert może skorzystać ze zmiennej lokalnej, która będzie odwoływać się do obecnej wartości węzła. Ułatwia to przejrzystość kodu.
public void Insert(TItem newItem)
{
TItem currentNodeValue = this.NodeData;
}Czas na dodanie wyrażenia if-else, które jest częścią tego algorytmu. Metody używają wyrażenia CompareTo() z interfejsu IComparable od T do ustalenia, czy obecna wartość węzła jest większa, niż wartość nowego węzła, który ma być dodany.
public void Insert(TItem newItem)
{
TItem currentNodeValue = this.NodeData;
if (currentNodeValue.CompareTo(newItem) > 0)
{
//tutaj ma trafić element do lewego poddrzewa
}
else
{
//tutaj ma trafić element do prawego poddrzewa
}
}Koncentracja teraz pada na wyrażenie if/else. Rozbijmy to na jeszcze mniejsze części i skoncentrujmy się na kodzie, który ma dodać węzeł do lewego poddrzewa.
Pomimo iż warunek został spełniony wciąż musimy sprawdzić czy lewe poddrzewo jest puste. Jeśli tak jest tworzymy nowe drzewo za pomocą konstruktora i umieszczamy w argumencie konstruktora zmienną, reprezentującą nową wartość, czyli newItem.
if (currentNodeValue.CompareTo(newItem) > 0)
{
if (this.LeftTree == null)
{
this.LeftTree = new Tree<TItem>(newItem);
}
else
{
this.LeftTree.Insert(newItem);
}
}W przeciwnym wypadku umieszczamy newItem w istniejącym lewym poddrzewie wywołując rekursywnie metodę Insert(). Co się dzieje dalej zależy od przykładu.
Teraz czas na kod, który ma dodać węzeł do prawego poddrzewa. Kod jest zbliżony do poprzedniego przykładu tylko teraz lewo jest prawo.
else
{
if (this.RightTree == null)
{
this.RightTree = new Tree<TItem>(newItem);
}
else
{
this.RightTree.Insert(newItem);
}
}Potrzebna będzie jeszcze metoda służąca do spacerowania po drzewie w tej klasie.
public void WalkTree()
{
}W tej metodzie trzeba zaimplementować algorytm wyświetlający wartości drzewa, który opisałem już wcześniej. Ułatwiłem sobie sprawę i wyświetlam wynik drzewa w konsoli.
public void WalkTree()
{
if (this.LeftTree != null)
{
this.LeftTree.WalkTree();
}
Console.WriteLine(this.NodeData.ToString());
if (this.RightTree != null)
{
this.RightTree.WalkTree();
}
}Chociaż użycie StringBulidera w tej metodzie jest wykonalne, w ten sposób jak widać to poniżej. Tylko będę musiał się upewnić czy moje rozumowanie, w tym przypadku jest prawidłowe. Zmienna bool indykuje, czy napis ma wyświetlić wartości w jednej linijce po przecinkach, czy w wielu linijkach od każdej wartości.
public string WalkTree(StringBuilder sb,bool NewLineMode)
{
if (this.LeftTree != null)
{
this.LeftTree.WalkTree(sb,NewLineMode);
}
if (NewLineMode == false)
sb.Append(string.Format("{0} , ", this.NodeData.ToString()));
else sb.AppendLine(this.NodeData.ToString());
if (this.RightTree != null)
{
this.RightTree.WalkTree(sb,NewLineMode);
}
return sb.ToString();
}
To wszystko, co jest potrzebne do klasy Tree. Poniżej zamieściłem cały kod tej klasy, jeśli chcesz to przepisać w całości, a nie we fragmentach.
using System;
using System.Text;
namespace BinaryTree
{
public class Tree<TItem> where TItem : IComparable<TItem>
{
public void Insert(TItem newItem)
{
TItem currentNodeValue = this.NodeData;
if (currentNodeValue.CompareTo(newItem) > 0)
{
if (this.LeftTree == null)
{
this.LeftTree = new Tree<TItem>(newItem);
}
else
{
this.LeftTree.Insert(newItem);
}
}
else
{
if (this.RightTree == null)
{
this.RightTree = new Tree<TItem>(newItem);
}
else
{
this.RightTree.Insert(newItem);
}
}
}
public void WalkTree()
{
if (this.LeftTree != null)
{
this.LeftTree.WalkTree();
}
Console.WriteLine(this.NodeData.ToString());
if (this.RightTree != null)
{
this.RightTree.WalkTree();
}
}
public string WalkTree(StringBuilder sb, bool NewLineMode)
{
if (this.LeftTree != null)
{
this.LeftTree.WalkTree(sb, NewLineMode);
}
if (NewLineMode == false)
sb.Append(string.Format("{0} , ", this.NodeData.ToString()));
else sb.AppendLine(this.NodeData.ToString());
if (this.RightTree != null)
{
this.RightTree.WalkTree(sb, NewLineMode);
}
return sb.ToString();
}
public Tree(TItem nodeValue)
{
this.NodeData = nodeValue;
this.LeftTree = null;
this.RightTree = null;
}
public TItem NodeData { get; set; }
public Tree<TItem> LeftTree { get; set; }
public Tree<TItem> RightTree { get; set; }
}
}
Na koniec, musimy zbudować projekt i to wszystko. 
Po kompilacji projektu została utworzona biblioteka dll w folderze <projekt>/bin/debug/ 
Za chwile sprawdzimy czy klasa Tree działa jak powinna.
Testowanie klasy Tree od T
Bibliotekę Tree najłatwiej przetestować poprzez dodanie kolejnego projektu do Solucji. Pamiętać należy, że solucja może zawierać wiele projektów.
Aplikację, którą dodam, to konsolowa aplikacja, w końcu nie potrzebujemy dodatkowych fajerwerków. 
Projekt nazwałem BinaryTreeTest. W czasie uruchamiania aplikacji konsolowej trzeba pamiętać, że projekt musi być zaznaczony w Solution Explorer. 
Aby aplikacja konsolowa mogła korzystać z biblioteki Binarytree.dll trzeba dodać do niej referencje. Z dialogu dodania referencji wybieramy Projects, a z niej wybieramy BinaryTree project.
Teraz do listy referencji powinna być dodana biblioteka Binarytree.dll
W aplikacji konsolowej, w pliku program.cs trzeba dodać przestrzeń nazw z naszej biblioteki , jest to przestrzeń “BinaryTree”.
using BinaryTree; W metodzie Main, która wykonuje się proceduralnie w konsoli stworzyłem instancje drzewa i umieściłem następujące cyfry.
static void Main(string[] args)
{
Tree<int> tree = new Tree<int>(5);
//główny węzeł
tree.Insert(3);
tree.Insert(10);
tree.Insert(1);
tree.Insert(4);
tree.Insert(-1);
tree.Insert(0);
tree.Insert(4);
tree.Insert(7);
tree.Insert(15);
tree.Insert(16);
tree.Insert(19);
tree.Insert(8);
tree.Insert(10);
tree.Insert(9);
tree.WalkTree();
Console.ReadKey();
}Te wyrażenia tworzą nowe binarne drzewo, które przetrzymuje dane typu int. Konstruktor tworzy inicjujący węzeł, który ma wartość 5. Wyrażenia Insert dodają kolejne węzły do drzewa, a metoda WalkTree wyciąga zawartość węzłów, które powinny być w kolejności rosnącej i tak jest.
C#string wynik = tree.WalkTree(sb,false);
Console.Write(wynik);
Console.WriteLine();
sb.Clear();
string wynik2 = " " + tree.WalkTree(sb, true);
Console.Write(wynik2);
Console.ReadKey(); Sprawdzę tylko jeszcze, czy moja metoda przeciążona WalkTree, zwracająca string działa poprawnie. 
Program powinien wyświetlić następującą sekwencje.
Sprawdźmy, jak drzewo binarne radzi sobie z napisami.
Console.Clear();
Tree<string> tree2 = new Tree<string>("Mortal Kombat");
tree2.Insert("Defender Of Crown");
tree2.Insert("Gobliins");
tree2.Insert("Settlers");
tree2.Insert("Dune 2");
tree2.Insert("Mentor");
tree2.Insert("Franko");
tree2.Insert("Doman");
tree2.Insert("Legion");
tree2.Insert("Misja Harolda");
tree2.Insert("Eksperyment Deflin");
tree2.Insert("Mortal Kombat 2");
tree2.Insert("Shadow of the Beast");
tree2.Insert("Lost Patrol");
tree2.Insert("Monkey Island");
tree2.Insert("Pinbal Fantasies");
tree2.Insert("Genghis Khan");
tree2.Insert("The Lost Vikings");
tree2.Insert("Master Blaster");
tree2.Insert("Ciemna Strona");
tree2.Insert("Another World");
tree2.Insert("Flashback");
tree2.Insert("Lemmings");
tree2.Insert("Blitz Bommbers");
tree2.Insert("Deluxe Galaga");
StringBuilder sb2 = new StringBuilder();
string wynik3 = tree2.WalkTree(sb2, true);
Console.Write(wynik3);
Console.ReadKey();Jak widać moja pamięć do tytułów gier na Amigę nie zna granic. Oto co wyświetliło się w konsoli. 
Lista gier idealnie posortowana alfabetycznie.
Następnym razem omówię jak stworzyć metodę generyczną.
