Kiến trúc máy tính - Bài 10

CâyTree.Cây–Cấutrúcdữliệuphi tuyến(TreesNonlineardata structures)ĐHGTVTCNTTKTVTCT2.Mộtsốvídụsửdụngcấu
Nội dung trích xuất từ tài liệu:
Kiến trúc máy tính - Bài 10Bài10.CâyTree 1Cây–Cấutrúcdữliệuphituyến(TreesNonlineardatastructures) ĐHGTVT CT CNTT KTVT 2Mộtsốvídụsửdụngcấutrúcdữliệucây 3 DatastructurestreesCâygiaphả 4 Datastructurestrees Câybiểudiễncáctổchức ĐHGTVT KT ĐĐT CNTT CK … KTVT ĐKH TTBĐ CNPM KHMT VTMạng 5 DatastructurestreesCâybiểudiễnhệthốngfiles Câymôtảsựphânchiahệthốngfiles 6 DatastructurestreesCấutrúccủacuốn Câythểhiện cấutrúcsách thôngtin Câythểhiệncấutrúccủamộtcuốnsách 7 Datastructurestrees Câythể hiệnlựaCâyquyếtđịnh chọnquyết định Bạnđãcógiađìnhriêngchưa? rồi chưa Bạncóbằngđạihọckhông? Khôngchấpnhận có Không Bạncótốtnghiệploạigiỏikhông? Khôngchấpnhận có không Chấpnhận Khôngchấpnhận Câyquyếtđịnhtuyểnnhânviên 8 DatastructurestreesCâynhịphânbiểudiễncácbiểuthứctoánhọc Mộtcâynhịphânbiểudiễnmộtbiểuthức.Câynàybiểudiễn biểuthức((((3+1)*3/((95)+2))((3*(74))+6)).Gi átrị đượckết hợplạitạinúttrongcónhãn“/”là2. 9 DatastructurestreesCâycúphápSXYXXA|a|bYAY|aAa 10 DatastructurestreesTổngkết:Câylàcáchtổchứcdữliệurấthữudụngtrongrấtnhiềuứngdụngkhácnhau ĐHGTVT CT CNTT KTVT 11 DatastructurestreesCâytổngquát Câylàgì? Câylàmộttậpcácnútvớiquanhệchacon (parentchild)giữacácnút.Trongđócómột nútđượcgọilàgốcvànókhôngcócha. Trongkhoahọcmáytính,mộtcâylàmộtmô hìnhtrừutượngcủacấutrúcphâncấp. Cácứngdụng: Tổchứcbiểuđồ  Hệthốngfile  Cácmôitrườnglậptrình…  12 DatastructurestreesMộtsốkháiniệm Gốc(root):gốclànútkhông Câycon:Câybaogồm cónútcha(vd:A) mộtsốnútcủamộtcây banđầu Núttrong:Nútcóítnhấtmột nútcon(Vd:A,B,C,F) A Nútngoài(lá):nútkhôngcó nútcon(Vd:E,I,J,K,G,H, D) B C D Đôsâucủamộtnút: Nútgốccóđộsâulà0,nếu E F G H nútchacóđộsâulàhthìnút concóđộsâulàh+1 Chiềucaocủacây:làgiátrị I J K lớnnhấtcủađộsâucủatất cảcácnút(3) Câycon 13 DatastructurestreesCấutrúcdữliệutrừutượngcây Chúngtaquảnlýcácnút Cácphươngthứctruyvấn: thôngquađịachỉcủa intisInternal(Node*) chúng.  intisExternal(Node*) Cácphươngthứcchung:  intisRoot(Node*) intsize() ...