ALG6

146 Rozdział 5. Struktury danycti

Jak widać, inteligentne użycie tablic może nam podsunąć możliwości z trudem] uzyskiwane w przypadku optymalnych, listowych struktur danych.

Popatrzmy dla przykładu na implementację tablicową drzew, w których nie stI zapamiętywane informacje dotyczące potomków danego węzła (tzn. nie interesuje j nas zstępowanie w stronę liści), ale informacje o rodzicach danego potomka.

Terminologia używająca określeń: ojciec, syn, potomek lewy, potomek pra\\\ I etc. jest ogólnie spotykana w książkach poświęconych strukturom drzewiastymi - również anglojęzycznych. W tym miejscu warto być może przytoczyć anegdotę! dotyczącą właśnie tego typu określeń, które mogą osoby nieprzyzwyczajone I prowadzić do konfuzji. W 1993 roku uczestniczyłem w kursie języka angielskiego] przeznaczonym dla Francuzów i prowadzonym przez przybyłą do Francji Amery- j kankę o dość ekstrawaganckim sposobie bycia. W trakcie kursu należało przygotować małe exposś na dowolny w zasadzie, ale techniczny temat. Jeden z francuskich studentów omówił pewien algorytm dotyczący rozproszonych baz danych, w którym dość sporo miejsca zajmowało wyjaśnienie drzewiastej struktury danych, służącej do reprezentacji pewnych istotnych dla algorytmu danych. Terminologia, której używał do opisu drzewa, była identyczna z zaprezentowaną powyżej: ojciec, syn, potomek itp. Anglosasi są ogólnie dość uczuleni na punkcie jawnego rozróżniania fonu osobowych (on, ona) od bezosobowych, obejmujących w zasadzie wszystko oprócz osób (określane w sposób ogólny zaimkiem it), Student, o którym jest mowa, omawiał coś o charakterze bez wątpienia bezosobowym - strukturę danych, ale od czasu do czasu używał określeń „zarezerwowanych" normalnie dla istot ludzkich - ojciec, syn... Amerykanka słuchała jego przemowy przez dobrych kilka minut, otwierając coraz szerzej oczy, aż w końcu nie wytrzymała, wyskoczyła na środek klasy i przerwała Francuzowi: “What father? What child? Please show me where is the zizi' here!” - pokazując jednocześnie na narysowane na tablicy drzewo...

Ale wróćmy do tematu i pokażmy wreszcie obiecaną implementację drzew przy pomocy tablic, tak aby uzyskać informację o węzłach „ojcach”. Rysunek 5-23 przedstawia drzewo służące do zapamięty wania liter (czyli pole ra/jest typu char).

		syn	ojciec
	0	c	0
C„	1	A	0
-r Ar	2	B	0
	3	Z	0
B, Z,	4	A	1
A Ą *	5	C	1
	6	D	1
	7	M	2
D, M, K, L,	8	K	3
	9	L	3

Rys. S - 23.

Tablicowa reprezentacja drzewa.

A

A, C,

W ten sposób francuskie dzieci określają nieodłączny atrybut każdego mężczyzny.