Lekcja: "Algorytmy sortujące - drzewa binarne, sortowanie przez kopcowanie"
Drzewo binarne a tablica
Aby móc przetwarzać za pomocą komputera struktury drzew binarnych musimy zapisać, przedstawić je w pamięci.W tym celu stosujemy n-elementową tablicę (rys. 1) – każdy jej element reprezentuje jeden węzeł drzewa binarnego. Dla określenia związku pomiędzy poszczególnymi indeksami elementów w tablicya położeniem tych elementów w strukturze drzewa binarnego określimy:
element d[1] będzie korzeniem drzewa
i-ty poziom drzewa binarnego wymaga 2i-1 węzłów, które będą kolejno pobierane z tablicy (rys. 2)
W celu określenia k-tego węzła (rys. 3) zostaną wprowadzone następujące oznaczenia – dla węzłów potomnych:
2k – lewy potomek
2k+1 – prawy potomek
węzeł nadrzędny ma indeks równy [k / 2] (dzielenie całkowitoliczbowe)
