Wyklad 08, Studia - Politechnika Opolska, Semestr 3, Systemy Operacyjne

//-->.pos {position:absolute; z-index: 0; left: 0px; top: 0px;}DrzewaRównoważne definicje drzewa wolnego(przypomnienie):• Acykliczny, spójny graf nieskierowany,• Graf nieskierowany, w którym każde dwa wierzchołki łączy ze sobą dokładnie jedna ścieżkaprosta,• Graf nieskierowany, w którym każda krawędź jest mostem (usunięcie dowolnej krawędzirozspójnia graf),• G spójny i |E|=|V|-1,• G acykliczny i |E|=|V|-1,• G acykliczny, ale dodanie krawędzi tworzy cyklDrzewemjest drzewo wolne z wyróżnionym wierzchołkiem –korzeniem.Zastosowania drzew:••••••••struktura katalogów i plików na dysku,struktura uczelni,rozdziały książki,wyrażenia arytmetyczne,drzewo genealogiczne,menu telefonu komórkowego,struktura firmy,podział administracyjny kraju.Slajd 1AiSD - Wykład8–DrzewaPrzykłady drzewAiSD - Wykład8–DrzewaSlajd 2Drzewa gierAiSD - Wykład8–DrzewaSlajd 3Dalsze definicjeKażdy węzełxdrzewa oprócz korzenia jest wskazywany przez dokładnie jeden węzełpoprzedniy.•yjestrodzicem(poprzednikiem)x.•xjestdzieckiem(następnikiem)y.Węzeł bez następników jestliściem.Droga od korzenia do liścia jestgałęzią.Wysokością węzław drzewie nazywamy długość najdłuższej ścieżki od tego węzła do liścia.Wysokością drzewajest wysokość jego korzenia.Głębokością węzław drzewie jest długość ścieżki od korzenia do tego węzła.RABCIJKObiegnięcie drzewa dookoła:R A I P I A R B R C J C K C R(ile razy?)RAIPB CJ KpreorderP I A B J K C RpostorderPIARB JCKinorderPAiSD - Wykład8–DrzewaSlajd 4Przechodzenie drzew (binarnych)Wdrzewie binarnymwęzeł zawiera dokładnie dwa wskaźniki do węzłów potomnych(oraz ewentualnie do rodzica)Przechodzenie (odwiedzanie) wierzchołków drzewa binarnego w kolejności:preorder− odwiedź korzeń− przejdź lewe poddrzewo− przejdź prawe poddrzewopostorder− przejdź lewe poddrzewo− przejdź prawe poddrzewo− odwiedź korzeńinorder− przejdź lewe poddrzewo− odwiedź korzeń− przejdź prawe poddrzewovoidtraverse(link h){if (h == 0) return;visit(h);traverse(h->l);traverse(h->r);}AiSD - Wykład8–DrzewaSlajd 5

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

kachorra.htw.pl