Drzewa binarne
Przyjmując następującą definicję węzła drzewa binarnego rozwiąż podane zadania.
struct node
{
int dane;
node *left;
node *right;
};
Zad 1 Napisz funkcjÄ™ sprawdzajÄ…cÄ…, czy dany element x znajduje siÄ™ w drzewie.
bool search(node *&korzen, int x)
Zad 2 Napisz funkcje wyznaczające: liczbę węzłów drzewa binarnego, liczbę liści, liczbę prawych
potomków w całym drzewie, wysokość drzewa.
Zad 3 Napisz funkcję sprawdzającą, czy drzewo binarne jest zbalansowane (zrównoważone)
(różnica wysokości lewego i prawego poddrzewa każdego węzła wynosi zero lub jeden).
Zad 4 Napisz funkcjÄ™ sprawdzajÄ…cÄ…, czy drzewo binarne jest drzewem BST (ng. binary search
tree), czyli czy zachodzi następująca własność. Niech x będzie węzłem drzewa. Jeśli y jest
węzłem znajdującym się w lewym poddrzewie węzła x, to dana(x) > dana(y). Jeśli y jest węzłem
znajdującym się w prawym poddrzewie węzła x, to dana(x) < dana(y).
Zad 5 Napisz procedurę usuwającą wszystkie liście danego drzewa binarnego.
Zad 6 Zastosuj procedurypreorder(), inorder(), postorder()do poniższego drzewa,
zakładając, że odwiedzenie węzła p wiąże się z następującym działaniem:
" if(p->left!=NULL && p->dana - p->left->dana < 2)
p->left->dana+=2;
" if(p->left==NULL)
p->right=0;
Zad 7 Pokaż drzewo dla którego metody preorder i inorder generują ten sam ciąg.
Zad 8 Napisz funkcjÄ™ tworzÄ…cÄ…  odbicie lustrzane podanego drzewa binarnego.
Zad 9 Napisz funkcję, która drukuje drzewo jak pokazano poniżej.
1
A
B
D
E
C
F
H
I
G
Zad 10 Dana jest tablica a = [a1, a2, . . . , an] o długości n = 2k - 1, dla całkowitych k > 0.
Napisz funkcję tworzącą drzewo jak pokazano w poniższych przykładach.
" a1 Ò! {a1},
" a1, a2, a3 Ò! {a2, {a1}, {a3}},
" a1, a2, a3, a4, a5, a6, a7 Ò! {a4, {a2, {{a1}, {a3}}}, {a6, {{a5}, {a7}}}}.
Zad 11 Strukturę drzewiastą zdefiniowano następująco:
struct node{
char op; //*, +, -
int num;
node *left, *right;
};
Drzewa zdefiniowane w ten sposób mogą reprezentować wyrażenia arytmetyczne (węzły
wewnętrzne to operatory, a zewnętrzne to liczby). Na przykład wyrażenie (7+8)*(3-2) można
przedstawić jako następujące drzewo:
Napisz funkcję, która oblicza wartość takich drzew (dla drzewa z rysunku funkcja powinna
zwrócić wartość 15).
2