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ęź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 <iostream>

using namespace std;

struct node {

int key;

node *left, *right;

};

node *_create_node( int key )

{

//tworzenie węzła ze wskazanym kluczem

node *temp;

temp = new node;

temp -> right = temp -> left = NULL;

temp -> key = key;

return temp;

}

int _remove_min(node **start)

{

// przesuwanie poddrzewa

if ( !(*start)->left )

{

int result ( (*start) -> key );

node *temp ( (*start) );

(*start) = (*start) -> right;

delete temp;

return result;

3

Podstawy programowania. Wykład 13 – drzewa

Małgorzata Nalbach-Moszyńska

}

return _remove_min( & ((*start)->left) );

}

node *_insert(int key, node **where)

{

// wstawianie wezla ze wskazanym kluczem

if ( (*where) == NULL )

{

return ( (*where) = _create_node( key ) );

}

if ( key >= (*where) -> key )

{

return _insert( key, &( (*where) -> right) );

}

else

{

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 );

}

}

bool insert(node **_root, int key)

4

Podstawy programowania. Wykład 13 – drzewa

Małgorzata Nalbach-Moszyńska

{

cout<<"Wstawiam "<<key <<endl;

return _insert( key, _root ) != NULL;

}

bool _remove(int key, node **where)

{

// koniec szukania

if ( (*where) == NULL )

return false;

// szukamy w prawym

if ( key > (*where)->key )

return _remove( key, &((*where)->right) );

// szukamy w lewym

if ( key < (*where)->key )

return _remove( key, &((*where)->left) );

// znaleziono

// bez poddrzew lisc

if ( !(*where)->left && !(*where)->right)

{

delete (*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 = _remove_min( &((*where)->right) );

return true;

}

bool remove(node *_root, int key)

{

cout << "Usuwam " << key<<endl;

return _remove( key, &_root );

}

bool member(node *_root, int key)

{

5

Podstawy programowania. Wykład 13 – drzewa

Małgorzata Nalbach-Moszyńska

// sprawdzanie, czy w drzewie istnieje wezel ze wskazanym kluczem (zwracamy bool) cout << "Sprawdzam "<< key<<endl; return _member( key, _root ) != NULL;

}

void printAsc( node *root)

{

//Wyswietlam w porzadku rosnacym

if (root == NULL) return; // puste

if (root->left == NULL and root->right==NULL)

cout << root->key<< '\t'; // lisc

else

{

if (root->left != NULL)printAsc(root->left);

cout << root->key<< '\t';

if (root->right != NULL)printAsc(root->right);

}

}

void printDesc(node *root)

{

// Wyswietlam w porzadku malejacym

if (root == NULL) return; // puste

if (root->left == NULL and root->right==NULL)

cout << root->key<< '\t'; // lisc

else

{

if (root->right != NULL)printDesc(root->right);

cout << root->key<< '\t';

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);

cout <<"Drukujemy rosnaco"<<endl;

printAsc(bst);

6

Podstawy programowania. Wykład 13 – drzewa

Małgorzata Nalbach-Moszyńska

cout<< endl<<"Drukujemy malejaco"<<endl; printDesc(bst);

cout<< endl;

remove(bst, 7);

cout <<"Drukujemy rosnaco"<<endl;

printAsc(bst);

remove(bst, 4);

cout << "member(bst, 4) (winno byc 0)" << member(bst,4) << endl; cout << "member(bst, 5) (winno byc 1)" << member(bst,5) << endl; cout << "member(bst, 7) (winno byc 1)" << member(bst,7) << endl; remove(bst,5);

cout << "member(bst,5) (winno byc 0)" << member(bst,5) << endl; 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

4

7

1

9

2

8

3

3

7

3

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

1

9

3

8

2

5

4

3

3

Pytanie: W jakiej kolejności powinny przychodzić dane, żeby drzewo było zrównoważone?

8