Question

1. Zaproponuj algorytm, który bada czy dany skończony ciąg, o elementach należących do pewnego zbioru liniowo uporządkowanego Et, może być ciągiem etykiet drzewa BST zapisanych w porządku preorder i jeśli jest to możliwe, tworzy takie drzewo BST.

Answer 1

Algorytm w załączniku.

 

Przykład 1:

1. n=6
5,3,2,4,5,1
tab[1]=5
tab[2]=3
tab[3]=2
tab[4]=4
tab[5]=5
tab[6]=1
2. i=2,L=0,P=0, k=i+1=3
3. 3<2 NIE
4. L=L+1=1, k=k+1=4
5. 3<4 TAK
6. P=P+1=1, k=k+1=5
7. 3<5 TAK
8. P=P+1=2, k=k+1=6
9. 3<1 NIE
10. L=L+1=2, k=n=6
11. P=2, L=2
12. NIE MOŻNA UTWORZYĆ CIĄGU ETYKIET DRZEWA BINARNEGO


PRZYKŁAD 2
1. N=6
4,3,2,7,9,8
tab[1]=4
tab[2]=3
tab[3]=2
tab[4]=7
tab[5]=9
tab[6]=8
2. i=2,L=0,P=0, k=i+1=3
3. 3<2 NIE
4. L=L+1=1, k=k+1=4
5. 3<7 TAK
6. P=P+1=1, k=k+1=5
7. 3<9 TAK
8. P=P+1=2, k=k+1=6
9. 3<8 TAK
9. P=P+1=3, k=n=6
10. L<2
11. i=i+1=3, k=i+1=4
12. 2<7 TAK
13. P=P+1=4, k=k+1=5
14. 2<9 TAK
15. P=P+1=5, k=k+1=6
16. 2<8 TAK
17. P=P+1=6, k=n=6
18. L<2
19. i=i+1=4, k=i+1=5
20. 7<9 TAK
21. P=7, k=k+1=6
22. 7<8 TAK
23. P=8, k=n=6
24. L<2
25. i=i+1=n-1=5
26. Utwórz drzewo BST

Uwagi:
1. Dla ciągu 1 lub 2 elementowego zawsze stworzymy BST z etykietami w ciągu preorder (korzeń lub korzeń z liściem)
2. Sprawdzamy czy ciąg pdany może być ciągiem etykiet drzewa w kolejności preorder czyli korzeń-->dzieci korzenia(rodzice jako węzeł 1)-->dzieci rodziców z węzła 1 itd.

Jeżeli drzewo ma być BST to należy pamiętać, że wartości kluczy węzłów leżących w lewym poddrzewie węzła muszą być mniejsze lub równe wartości klucza danego węzła - co dany algorytm sprawdza.