W katalogu domowym utworzyć podkatalog drzewa-int. Utworzyć w nim plik Makefile i pozostałe pliki, po jednym dla każdej funkcji:
/*
* main.h
*
* Plik naglowkowy - drzewa binarne.
*/
#include <stdio.h>
#include <stdlib.h>
/* typ logiczny */
typedef int bool;
#define TRUE 1
#define FALSE 0
typedef int Cargo;
/* definicja struktury */
struct btree {
Cargo data; /* dane elementu */
int count; /* licznik wystapien */
struct btree *left; /* wskaznik do lewego elementu */
struct btree *right; /* wskaznik do prawego elementu */
};
int cmp_cargo(Cargo a, Cargo b);
bool add_btree(struct btree **top_ptr, Cargo item);
/* Wstawienie elementu do drzewa */
bool find_btree(struct btree *top, Cargo item);
/* Szukanie elementu w drzewie */
void print_btree(struct btree *top);
/* Wypisanie zawartosci drzewa */
void print_indented(struct btree *top, int level);
/* Ladne rysowanie drzewa */
int count_btree(struct btree *top);
/* Zliczenie liczby wezlow w drzewie */
bool del_btree(struct btree **top_ptr, Cargo item);
/* Usuniecie elementu z drzewa */
#define is_empty(top) ((top == NULL) ? TRUE : FALSE)
/* bool is_empty(struct btree *top); */
/*
* main.c
*/
#include "main.h"
int main(void)
{
Cargo number = 22; /* przykladowa liczba do sprawdzania */
/* Inicjalizujemy puste drzewo */
struct btree *root = NULL;
printf("Wielkosc drzewa: %d\n", count_btree(root));
print_indented(root, 0);
add_btree(&root, 22);
printf("Wielkosc drzewa: %d\n", count_btree(root));
print_indented(root, 0);
add_btree(&root, 11);
printf("Wielkosc drzewa: %d\n", count_btree(root));
print_indented(root, 0);
add_btree(&root,11);
printf("Wielkosc drzewa: %d\n", count_btree(root));
print_indented(root, 0);
add_btree(&root, 33);
printf("Wielkosc drzewa: %d\n", count_btree(root));
print_indented(root,0);
if (find_btree(root, number) == FALSE)
printf("Nie znaleziono %d w drzewie\n", number);
else
printf("Znaleziono %d w drzewie\n", number);
if (del_btree(&root, 33) == FALSE)
printf("Nie zmniejszono drzewa\n");
else
printf("Zmniejszono drzewo\n");
return 0;
}
/*
* add_btree.c
*
* Kod umieszczajacy w drzewie nowy element.
*/
#include "main.h"
bool add_btree(struct btree **top_ptr, Cargo item)
{
if ((*top_ptr) == NULL) { /* pusty wezel */
/* przydzielenie pamieci nowej strukturze */
(*top_ptr) = malloc(sizeof(struct btree));
if ((*top_ptr) == NULL)
return FALSE;
(*top_ptr)->left = NULL;
(*top_ptr)->right = NULL;
(*top_ptr)->count = 1;
(*top_ptr)->data = item; /* wstawienie liczby do pola struktury */
} else { /* sprawdzamy, gdzie wstawic element */
if (cmp_cargo((*top_ptr)->data, item) < 0) /* wieksze na prawo */
add_btree(&(*top_ptr)->right, item);
else if (cmp_cargo((*top_ptr)->data, item) > 0) /* mniejsze na lewo */
add_btree(&(*top_ptr)->left, item);
else /* taki element jest w drzewie */
(*top_ptr)->count += 1;
}
return TRUE;
}
/*
* find_btree.c
*/
#include "main.h"
bool find_btree(struct btree *top, Cargo item)
{
bool status;
if (top == NULL)
return FALSE;
if (cmp_cargo(top->data, item) == 0)
return TRUE;
status = find_btree(top->left, item);
if (status == FALSE)
status = find_btree(top->right, item);
return status;
}
/*
* print_btree.c
*/
#include "main.h"
void print_btree(struct btree *top)
{
if (top != NULL) {
print_btree(top->left);
printf("%d (%d)\n", top->data, top->count);
print_btree(top->right);
}
return;
}
/*
* print_indented.c
*/
#include "main.h"
void print_indented(struct btree *top, int level)
{
int i;
if (top != NULL) {
print_indented(top->left, level+1);
for (i = 0; i < level; ++i)
printf(" ");
printf("%d (%d)\n", top->data, top->count);
print_indented(top->right, level+1);
}
return;
}
/*
* count_btree.c
*/
#include "main.h"
int count_btree(struct btree *top)
{
int counter = 0;
if (top != NULL) {
counter += count_btree(top->left);
++counter;
counter += count_btree(top->right);
}
return counter;
}
Dopisać brakujące funkcje, skompilować i uruchomić program.
W katalogu domowym utworzyć podkatalog drzewa-char. Utworzyć w nim plik Makefile i pozostałe pliki, po jednym dla każdej funkcji:
/*
* main.h
*
* Plik naglowkowy.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* typ logiczny */
typedef int bool;
#define TRUE 1
#define FALSE 0
typedef char *Cargo;
/* definicja struktury */
struct btree {
Cargo data; /* dane elementu */
int count; /* licznik wystapien */
struct btree *left; /* wskaznik do lewego elementu */
struct btree *right; /* wskaznik do prawego elementu */
};
int cmp_cargo(Cargo a, Cargo b);
bool add_btree(struct btree **top_ptr, Cargo item);
/* Wstawienie elementu do drzewa */
bool find_btree(struct btree *top, Cargo item);
/* Szukanie elementu w drzewie */
void print_btree(struct btree *top);
/* Wypisanie zawartosci drzewa */
void print_indented(struct btree *top, int level);
/* Ladne rysowanie drzewa */
int count_btree(struct btree *top);
/* Zliczenie liczby ROZNYCH elementow w drzewie */
bool del_btree(struct btree **top_ptr, Cargo item);
/* Usuniecie elementu z drzewa */
#define is_empty(top) ((top == NULL) ? TRUE : FALSE)
/* bool is_empty(struct btree *top); */
/*
* main.c
*/
#include "main.h"
int main(void)
{
Cargo napis = "dwa"; /* przykladowy napis do sprawdzania */
/* Inicjalizujemy puste drzewo */
struct btree *root = NULL;
printf("Wielkosc drzewa: %d\n", count_btree(root));
print_btree(root);
add_btree(&root, "jeden");
printf("Wielkosc drzewa: %d\n", count_btree(root));
print_btree(root);
add_btree(&root, "jeden");
printf("Wielkosc drzewa: %d\n", count_btree(root));
print_btree(root);
add_btree(&root, "dwa");
printf("Wielkosc drzewa: %d\n", count_btree(root));
print_btree(root);
add_btree(&root, "trzy");
printf("Wielkosc drzewa: %d\n", count_btree(root));
print_btree(root);
if (find_btree(root, napis) == FALSE)
printf("Nie znaleziono %s w drzewie\n", napis);
else
printf("Znaleziono %s w drzewie\n", napis);
if (del_btree(&root, napis) == FALSE)
printf("Nie zmniejszono drzewa\n");
else
printf("Zmniejszono drzewo\n");
print_btree(root);
return 0;
}
/*
* add_btree.c
*
* Kod umieszczajacy w drzewie nowy element.
*/
#include "main.h"
bool add_btree(struct btree **top_ptr, Cargo item)
{
int result; /* wynik dzialania funkcji strcmp() */
if ((*top_ptr) == NULL) { /* pusty wezel */
/* przydzielenie pamieci nowej strukturze */
(*top_ptr) = malloc(sizeof(struct btree));
if ((*top_ptr) == NULL)
return FALSE; /* brak pamieci */
(*top_ptr)->left = NULL;
(*top_ptr)->right = NULL;
(*top_ptr)->count = 1;
/* wstawienie do pola struktury */
(*top_ptr)->data = malloc((unsigned)(strlen(item)+1));
if ((*top_ptr)->data == NULL) {
free(*top_ptr);
(*top_ptr) = NULL;
return FALSE;
} else
strcpy((*top_ptr)->data, item);
} else { /* sprawdzamy, gdzie wstawic element */
result = cmp_cargo((*top_ptr)->data, item);
if (result < 0) /* wieksze na prawo */
add_btree(&(*top_ptr)->right, item);
else if (result > 0) /* mniejsze na lewo */
add_btree(&(*top_ptr)->left, item);
else /* taki element jest w drzewie */
(*top_ptr)->count += 1;
}
return TRUE;
}
/*
* print_btree.c
*/
#include "main.h"
void print_btree(struct btree *top)
{
if (top != NULL) {
print_btree(top->left);
printf("%s (%d)\n", top->data, top->count);
print_btree(top->right);
}
return;
}
Dopisać brakujące funkcje, skompilować i uruchomić program.
Napisać funkcję obliczającą wysokość drzewa binarnego.
int height_btree(struct btree *top);
Napisać funkcję liczącą liście drzewa binarnego. Liście to węzły, które nie mają potomków.
int leafs_btree(struct btree *top);
Napisać funkcje wypisujące zawartość drzewa w kolejności preorder (węzeł, lewe, prawe), inorder (lewe, węzeł, prawe), postorder (lewe, prawe, węzeł), poziomami.