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 procedury preorder(), 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 = [a
1
, a
2
, . . . , a
n
] o długości n = 2
k
− 1, dla całkowitych k > 0.
Napisz funkcję tworzącą drzewo jak pokazano w poniższych przykładach.
• a
1
⇒ {a
1
},
• a
1
, a
2
, a
3
⇒ {a
2
, {a
1
}, {a
3
}},
• a
1
, a
2
, a
3
, a
4
, a
5
, a
6
, a
7
⇒ {a
4
, {a
2
, {{a
1
}, {a
3
}}}, {a
6
, {{a
5
}, {a
7
}}}}.
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