Podstawy programowania. Wykład 13  drzewa
Małgorzata Nalbach-Moszyńska
13.Drzewa. .......................................................................................................................1
13.1 Budowa drzewa.......................................................................................................1
13.2 Operacje na drzewach .............................................................................................2
13.3 Reprezentacja drzew ...............................................................................................2
13.4 Przykładowa implementacja....................................................................................3
13.5 Kształt drzewa ........................................................................................................7
13.5.1 Dane pierwsze.................................................................................................7
13.5.2 Dane drugie (inna kolejność)...........................................................................8
13. Drzewa.
13.1 Budowa drzewa
Drzewa składają się z wierzchołków (węzłów) oraz łączących je krawędzi.
Jeśli drzewo nie jest puste, tzn. liczba wierzchołków jest większa od zera, jeden z nich jest
wyró\
niony i nazywany korzeniem drzewa.
Ciąg krawędzi łączących węzły nazywa się ście\
ką.
Liczba krawędzi w ście\
ce od korzenia do węzła jest nazywana długością  liczba ta
określa poziom węzła.
Wysokością drzewa jest największy poziom istniejący w drzewie.
Wszystkie wierzchołki połączone z danym wierzchołkiem, a le\
ące na następnym poziomie
są nazywane dziećmi tego węzła.
Wierzchołek mo\
e mieć dowolną liczbę dzieci. Jeśli nie ma ich wcale nazywany jest liściem.
Wierzchołek jest rodzicem dla ka\
dego swojego dziecka.
Ka\
dy węzeł ma dokładnie jednego rodzica, wyjątkiem jest korzeń drzewa, który nie ma
rodzica.
Specjalne znaczenie w informatyce mają drzewa binarne, w których liczba dzieci
ograniczona jest do dwóch. Szczególnie popularne są BST, przechowujące dane w sposób
uporządkowany.
Drzewa, których wierzchołki posiadają więcej ni\
dwoje dzieci są nazywane drzewami
wy\
szych rzędów, np. drzewo trie, drzewo trójkowe, B-drzewo .
1
Podstawy programowania. Wykład 13  drzewa
Małgorzata Nalbach-Moszyńska
liść
Rysunek 1 Przykładowe drzewo
13.2 Operacje na drzewach
Podstawowe operacje na drzewach to:
" przechodzenie wszystkich elementów drzewa (np po to, by wyświetlić),
" wyszukanie konkretnego elementu,
" dodanie nowego elementu w określonym miejscu drzewa,
" usunięcie elementu.
Pod pojęciem przechodzenia drzewa rozumie się odwiedzanie kolejnych wierzchołków,
zgodnie z zale\
nościami rodzic-dziecko. Jeśli przy przechodzeniu drzewa na wierzchołkach
są wykonywane pewne działania, to mówi się wówczas o przechodzeniu:
" preorder - gdy działanie jest wykonywane najpierw na rodzicu, następnie na dzieciach;
" postorder - gdy działanie jest wykonywane najpierw na wszystkich dzieciach, na końcu na
rodzicu.
W przypadku drzew binarnych (oraz pewnych innych typów drzew) istnieje jeszcze
metoda inorder, gdzie najpierw wykonywane jest działanie na jednym z dzieci, następnie na
rodzicu i na końcu na drugim dziecku.
13.3 Reprezentacja drzew
Fizycznie drzewa są reprezentowane za pomocą struktur wiązanych  ogólnie pojedynczy
wierzchołek przechowuje dane oraz dowiązania do swoich dzieci.
Przykład definicji typu drzewa binarnego, w którym dane (napisy) występują w ka\
dym
węz
le (język C):
struct drzewo {
struct drzewo *lewy_syn;
struct drzewo *prawy_syn;
char *dane;
};
2
Podstawy programowania. Wykład 13  drzewa
Małgorzata Nalbach-Moszyńska
Rysunek 2 Przykład drzewa binarnego BST (ang. Binary Search Tree)
13.4 Przykładowa implementacja
#include
#include
typedef struct nodee {
int key;
struct nodee *left, *right;
}node;
typedef char bool;
#define false 0;
#define true 1;
node *_create_node( int key )
{
/*tworzenie węzła ze wskazanym kluczem */
node *temp;
temp = malloc(sizeof(node));
temp -> right = temp -> left = NULL;
temp -> key = key;
return temp;
}
int _remv_min(node **start)
{
/* przesuwanie poddrzewa */
if ( !(*start)->left )
{
int result;
node *temp;
result = (*start) -> key;
temp = *start;
(*start) = (*start) -> right;
3
Podstawy programowania. Wykład 13  drzewa
Małgorzata Nalbach-Moszyńska
free(temp);
return result;
}
return _remv_min( & ((*start)->left) );
}
node *_insert(int key, node **where)
{
/* wstawianie wezla ze wskazanym kluczem */
if ( (*where) == NULL )
{
printf("***Korzen NULL\n");
return ( (*where) = _create_node( key ) );
}
else
if ( key >= (*where) -> key )
{
printf("***Do prawego\n");
return _insert( key, &( (*where) -> right) );
}
else
{
printf("***Do lewego\n");
return _insert( key, &( (*where) -> left ) );
}
}
node *_member( int key, node *where )
{
/* sprawdzanie, czy w drzewie istnieje
wezel ze wskazanym kluczem (zwracamy wskaznik)*/
/* dotarto do konca drzewa */
if ( where == NULL )
{
return NULL ;
}
/* znaleziono element */
if ( key == where -> key )
{
return where;
}
/* w zaleznosci od wart klucza szukamy w lewym lub prawym
poddrzewie */
if ( key >= where-> key )
{
return _member( key, where -> right );
}
else
{
return _member( key, where -> left );
}
}
4
Podstawy programowania. Wykład 13  drzewa
Małgorzata Nalbach-Moszyńska
bool insert(node **_root, int key)
{
printf("Wstawiam %d\n",key);
return _insert( key, _root ) != NULL;
}
bool _remv(int key, node **where)
{
/* koniec szukania */
if ( (*where) == NULL )
return false;
/* szukamy w prawym */
if ( key > (*where)->key )
return _remv( key, &((*where)->right) );
/* szukamy w lewym */
if ( key < (*where)->key )
return _remv( key, &((*where)->left) );
/* znaleziono */
/* bez poddrzew lisc */
if ( !(*where)->left && !(*where)->right)
{
free (*where);
(*where) = NULL;
return true;
}
/* jest tylko prawe */
if ( !(*where)->left )
{
(*where) = (*where)->right;
return true;
}
/* jest tylko lewe */
if ( !(*where)->right )
{
(*where) = (*where)->left;
return true;
}
/* sa oba */
(*where)->key = _remv_min( &((*where)->right) );
return true;
}
bool remv(node *_root, int key)
{
printf( "Usuwam %d\n", key);
return _remv( key, &_root );
}
bool member(node *_root, int key)
{
/* sprawdzanie, czy w drzewie istnieje wezel ze wskazanym kluczem
(zwracamy bool)*/
printf( "Sprawdzam %d\n", key);
return _member( key, _root ) != NULL;
}
5
Podstawy programowania. Wykład 13  drzewa
Małgorzata Nalbach-Moszyńska
void printAsc( node *root)
{
/* Wyswietlam w porzadku rosnacym */
if (root == NULL) return; /* puste */
if (root->left == NULL && root->right==NULL)
printf("%d\t",root->key) ; /* lisc */
else
{
if (root->left != NULL)printAsc(root->left);
printf("%d\t",root->key) ;
if (root->right != NULL)printAsc(root->right);
}
}
void printDesc(node *root)
{
/* Wyswietlam w porzadku malejacym */
if (root == NULL) return; /* puste */
if (root->left == NULL && root->right==NULL)
printf("%d\t",root->key) ; /* lisc */
else
{
if (root->right != NULL)printDesc(root->right);
printf("%d\t",root->key) ;
if (root->left != NULL)printDesc(root->left);
}
}
int main()
{
node *bst = NULL; /*korzen drzewa */
insert(&bst, 5);
insert(&bst, 4);
insert(&bst, 7);
insert (&bst, 1);
insert (&bst, 2);
insert (&bst, 9);
insert (&bst, 3);
insert (&bst, 8);
insert (&bst, 3);
insert (&bst, 3);
printf("Drukujemy rosnaco\n");
printAsc(bst);
printf( "\nDrukujemy malejaco\n");
printDesc(bst);
printf("\nUsuwamy 7\n");
remv(bst, 7);
printf("Drukujemy rosnaco\n");
printAsc(bst);
printf("\nUsuwamy 4\n");
remv(bst, 4);
printf( "member(bst, 4) (winno byc 0) %d\n", member(bst,4));
6
Podstawy programowania. Wykład 13  drzewa
Małgorzata Nalbach-Moszyńska
printf( "member(bst, 5) (winno byc 1) %d\n", member(bst,5));
printf( "member(bst, 7) (winno byc 1) %d\n", member(bst,7));
printf("\nUsuwamy 5\n");
remv(bst,5);
printf( "member(bst, 5) (winno byc 0) %d\n", member(bst,5));
return 0;
}
13.5 Kształt drzewa
Kształt drzewa zale\
y od kolejności dodawania wierzchołków.
13.5.1 Dane pierwsze
Przykładowe dane tworzą następujące drzewo:
5, 4, 7, 1, 2, 9, 3, 8, 3, 3
5
7
4
1
9
2
8
3
3
3
7
Podstawy programowania. Wykład 13  drzewa
Małgorzata Nalbach-Moszyńska
13.5.2 Dane drugie (inna kolejność)
Przykładowe dane tworzą następujące drzewo:
7, 1, 3, 5, 4, 2, 9, 3, 8, 3
7
9
1
3 8
2
5
4
3
3
Pytanie: W jakiej kolejności powinny przychodzić dane, \
eby drzewo było
zrównowa\
one?
8