Dziś zajmiemy się strukturami drzewiastymi. I na początek mamy taki program:
#include<stdio.h>
#include<stdlib.h>
struct tree
{
int val;
struct tree *left;
struct tree *right;
};
struct tree *dodaj (struct tree *d, int x)
{
struct tree *e;
if(d==NULL){
e=(struct tree *) malloc (sizeof(struct tree));
if (e==NULL) exit(0);
else{
e->val=x;
e->left=NULL;
e->right=NULL;
d=e;
printf("dodaje %d\n", x);
}
}
else{//d!=NULL
if(x>=d->val) d->right=dodaj(d->right,x);
else d->left=dodaj(d->left,x);
}
return d;
}
void wypisz(struct tree *d)
{
if (d!=NULL){
printf("%d ",d->val);
wypisz(d->left);
wypisz(d->right);
}
}
void usun(struct tree *d)
{
if (d!=NULL){
usun(d->left);
usun(d->right);
free(d);
}
}
main(){
struct tree *d=NULL;
d=dodaj(d,4);
d=dodaj(d,6);
d=dodaj(d,2);
d=dodaj(d,1);
d=dodaj(d,5);
wypisz(d);
getchar();
}
Na początek widzimy deklarację odpowiednich bibliotek. Potem mamy deklarację struktury drzewiastej. Dalej deklarację trzech funkcji - dodającej elementy, wypisującej wszystkie elementy drzewa, oraz usuwającej (jeśli chcielibyśmy usunąć jakiś element z drzewa). Na końcu mamy zadeklarowaną funkcję główną. Jak widzimy po funkcji głównej zadaniem tego programu będzie stworzenie z pięciu elementów (4, 6, 2, 1, 5) następującego drzewa BST:
4
/ \
6
/ /
5
Funkcja dodaj odpowiednio filtruje dodawane elementy. Najpierw drzewo BST jest puste, czyli ma wyokość -1. Dodawana jest najpierw wartość 4. Będzie ona korzeniem, do którego będą przyrównywane inne elementy. Potem dodana jest 6 - ona idzie na prawo od 4, bo jest od niej większa. Nastepna jest 2. Ona idzie na lewo od 4, bo jest mniejsza od niej. Potem 1 - jest mniejsza od korzenia i od 2, więc idzie na lewo od 2. i piątka. Ona idzie na prawo od korzenia, bo jest większa i na lewo od 6, bo jest od niej mniejsza. Funkcja usun jest zadeklarowana, ale jak widzimy nie została ona użyta. Jej zadaniem jest usunięcie całego drzewa, lub poszczególnych elementów. I najwazniejsza z funkcji to funkcja wyświetlająca. Wypisuje ona elementy drzewa. Istnieją trzy mozliwości wypisania elementów: preorder, inorder i postorder. Dla powyższej funkcji wypisz będzie zastosowana pierwsza z tych metod wyświetlająca elemenety drzewa. Gdybyśmy przesuneli linijkę printf pomiędzy linijki wypisz, wówczas mielibyśmy do czynienia z funkcją inorder, natomiast, gdyby linijka printf powędrowała za obydwie linijki z użyta funkcją wypisz, to mielibyśmy do czynienia z metodą wyświetlenia postorder. Teraz na czym te metody polegają. Jeśli użyjemy pierwszej z tych metod tak, jak w programie, to program najpierw zaczeni od wypisania korzenia, następnie przejdzie do lewego poddrzewa i potem do prawego. Dzieki temu program nam wypisze elementy w kolejności: 4 2 1 6 5. Kolejna z metod to metoda inorder. Tutaj program najpierw przejdzie do lewego poddrzewa, potem wypisze korzeń i przejdzie do prawego poddrzewa. Dzięki temu program wypisuje elementy w taki sposób: 1 2 4 5 6. Zauważmy, że jest to kolejność uporządkowana. Tak właśie porządkuje się elementy w drzewie I ostatnia metoda to metoda postorder, która przechodzi do lewego poddrzewa, potem do prawego i na końcu wyświetla korzeń. Stąd uporzadkowanie: 1 2 5 6 4.
Teraz napiszemy kilka funkcji odnoszących się do drzew. Pierwszą z nich będzie funkcja, która zliczy wszystkie elementy w strukturze drzewiastej. Funkcja ta wygląda następująco:
int ile(struct tree *d){
if (d==NULL)
return 0;
else{
return ile(d->left)+ile(d->right)+1;
}
W programie głównym funkcję wywołamy w taki sposób:
int ile(d);
Kolejna funkcja ma obliczyć wysokość drzewa. Jak wiadomo każde drzewo ma jakąś wysokość. Jeśli składa się tylko z korzenia mówimy o wysokości 0, jeśli nie ma ani korzenia, ani żadnych innych elementów, mówimy o wysokości -1. Z kolei jeśli drzewo będzie miało korzeń i jedno rozgałęzienie (nie ważne, czy w prawo, czy w lewo), to wtedy wysokośc wynosi 1 i w miarę dodawania nowych rozgałęzień ta liczba będzie się zwiększała. Oto pseudokod tej funkcji:
int wysokosc(struct tree *d){
if(d==NULL)
return 0;
else{
return max(wysokosc(d->left),wysokosc(d->right))+1;
}
Nastepna funkcja ma zliczać ilośc liści w drzewie, czyli takich elementów, które nie posiadają żadnych rozgałęzień. Funkcja ta wygląda mniej więcej tak:
int ile_lisci(struct tree *d){
if(d==NULL)
return 0;
else {
if (d->left==NULL && d -> right==NULL)
return 1;
else return ile_lisci(d->right)+ile_lisci(d->left);
}
}
Następna funkcja będzie kopiowała całą strukturę drzewiastą. Funkcja ta jest następująca:
struct tree *kopia(struct tree *d){
struct tree *e;
if(d==NULL)
return NULL;
else{
e=(struct tree *) malloc (sizeof(struct tree));
if(e=NULL) exit(0);
e->val=d->val;
e->left=kopia(d->left);
e->right=kopia(d->right);
return e;
}
}
A teraz jak przekształcić powyższy kod, aby zwracane było drzewo będące odbiciem lustrzanym. Bardzo prosto się to robi. Wystarczy zmodyfikować 2 linijki:
e->left=kopia(d->right);
e->right=kopia(d->left);
Kolejna funkcja ma za zadanie sprawdzić, czy dwa drzewa mają taki sam kształt. W przypadku, gdy będą miały taki sam, to ma zostac zwrócona wartość 1. W przeciwnym wypadku - wartośc 0. A zatem:
int kształt(struct tree *d1,struct tree *d2);
if(d1==NULL && d2==NULL)
return 1;
else if (d1==NULL && d2!=NULL) || (d1!=NULL && d2==NULL)
return 0;
else //oba różne od NULL
{
ksztalt(d1->left,d2->left) && ksztalt(d1->right,d2->right);
}
I na koniec taka funkcja, której zadaniem jest wypisanie elementu majsymalnego z drzewa. A więc:
struct tree * findmax(struct tree *d){
if (d!=NULL)
while (d->right!=NULL)
d=d->right;
return d;
}