Ocena brak

Z jaką strukturą sterującą związane są drzewa? Ilustrując ten związek opisz zasadę przeglądania drzewa w algorytmie sortowania drzewiastego

Autor /Barnim7777 Dodano /29.12.2011

Drzewa związane są z rekurencją.

Opis słowny algorytmu przeglądu drzewa w algorytmie sortowania drzewiastego:

procedura OBEJDŹ drzewo T:

1. jeśli T jest puste to wróć

2. w przeciwnym razie wykonaj co następuje:

- wywołaj obejdź T w lewo

- wypisz element umieszczony w korzeniu

- wywołaj obejdź T w prawo

Zasada przeglądu drzewa w algorytmie sortowania drzewiastego jest taka, że najpierw wywołana zostaje procedura obejdź pod-drzewo z lewej strony, wypisz wartość korzenia i obejdź pod-drzewo z prawej strony. W drzewie BST z lewej umieszczone są elementy mniejsze niż w korzeniu, a z prawej większe. Mamy więc pewność, że dzięki takiej organizacji wypisane zostaną elementy od najmniejszego do największego.

Związek pomiędzy drzewem i rekurencją jest tak silny dlatego, że nawet sam graf kolejnych wywołań rekurencyjnych ma strukturę drzewiastą.

Podobne prace

Do góry