Bài giảng Cấu trúc dữ liệu 1: Chương 4A - Huỳnh Cao Thế Cường

Chương 2 cung cấp kiến thức về cấu trúc cây (trees). Chương này gồm có những nội dung chính sau: Các thuật ngữ cơ bản trên cây, kiểu dữ liệu trừu tượng cây, cài đặt cây, cây nhị phân, cây tìm kiếm nhị phân. Mời các bạn tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu 1: Chương 4A - Huỳnh Cao Thế Cường TRƯỜNGĐẠIHỌCANGIANGKHOAKỸTHUẬTCÔNGNGHỆMÔITRƯỜNG CẤUTRÚCDỮLIỆU1 Giảngviênphụtrách: HUỲNHCAOTHẾCƯỜNG BộmônTinhọc email:hctcuong@agu.edu.vn 1 1 CẤU TRÚC CÂY (TREES)CácthuậtngữcơbảntrêncâyKiểudữliệutrừutượngcâyCàiđặtcâyCâynhịphânCâytìmkiếmnhịphân 2 CÁC THUẬT NGỮ CƠ BẢN TRÊN CÂYCâylàmộttậphợpcácphầntửgọilànút(nodes),trong đócómộtnútđượcphânbiệtgọilànútgốc(root).Mốiquanhệchacon(parenthood):đểxácđịnhhệ thốngcấutrúctrêncácnút.Mỗinút,trừnútgốc,códuynhấtmộtnútcha.Mộtnút cóthểcónhiềunútconhoặckhôngcónútconnào.MỗinútbiểudiễnmộtphầntửtrongtậphợpđangxétMốiquanhệchaconđượcbiểudiễntheoquiướcnút chaởdòngtrênnútconởdòngdướivàđượcnốibởi mộtđoạnthẳng. 3 Các thuật ngữ cơ bảnĐịnhnghĩa  Mộtnútđơnđộclàmộtcây.Nútnàycũngchínhlànút gốccủacây.  GiảsửtacónlàmộtnútđơnđộcvàkcâyT1,..,Tkvới cácnútgốctươngứnglàn1,..,nkthìcóthểxâydựng mộtcâymớibằngcáchchonútnlàchacủacácnútn1,.., nk.CâymớinàycónútgốclànútnvàcáccâyT1,..,Tk đượcgọilàcáccâycon.Tậprỗngcũngđượccoilàmột câyvàgọilàcâyrỗngkíhiệu. 4Các thuật ngữ cơ bản 5 Các thuật ngữ cơ bảnNếun1,..,nklàmộtchuỗicácnúttrêncâysaochonilànút chacủanútni+1,vớii=1..k1,thìchuỗinàygọilàmột đườngđitrêncây(hayngắngọnlàđườngđi)từn1đến nk.Độdàiđườngđiđượcđịnhnghĩabằngsốnúttrên đườngđitrừ1.Nhưvậyđộdàiđườngđitừmộtnútđến chínhnóbằngkhông. 6 Các thuật ngữ cơ bản alàtiềnbối(ancestor)củab,cònbgọilàhậuduệ (descendant)củanúta:Nếucóđườngđitừnútađếnnútb  mộtnútvừalàtiềnbốivừalàhậuduệcủachínhnó.  Tiềnbốihoặchậuduệcủamộtnútkhácvớichínhnó gọilàtiềnbốihoặchậuduệthựcsự.  Trêncâynútgốckhôngcótiềnbốithựcsự.nútlá(leaf):lànútkhôngcóhậuduệthựcsự.núttrunggian(interior):LànútkhôngphảilàláCâyconcủamộtcâylàmộtnútcùngvớitấtcảcáchậu duệcủanó. 7 Các thuật ngữ cơ bảnChiềucaocủamộtnút:độdàiđườngđilớnnhấttừnút đótớilá.Chiềucaocủacây:chiềucaocủanútgốc.Độsâucủamộtnút:độdàiđườngđitừnútgốcđếnnút đó.Cácnútcócùngmộtđộsâuitagọilàcácnútcócùng mộtmứci.  Theođịnhnghĩanàythìnútgốcởmức0,cácnútconcủa nútgốcởmức1. 8 Các thuật ngữ cơ bảnThứtựcácnúttrongcây  Nếutaphânbiệtthứtựcácnútconcủacùngmộtnútthì câygọilàcâycóthứtự,thứtựquiướctừtráisang phải.  Trongtrườnghợptakhôngphânbiệtrõràngthứtựcác nútthìtagọilàcâykhôngcóthứtự. • Cácnútconcùngmộtnútchagọilàcácnútanhem ruột(siblings). • Quanhệtráisangphảicủacácanhemruộtcóthể mởrộngchohainútbấtkỳtheoquitắc:nếua,blà haianhemruộtvàabêntráibthìcáchậuduệcủaa làbêntráimọihậuduệcủab. 9Các thuật ngữ cơ bản 10 Các thuật ngữ cơ bảnCácthứtựduyệtcâyquantrọng  Duyệtcâylàmộtquitắcchophépđiqualầnlượttấtcả cácnútcủacâymỗinútđúngmộtlần,danhsáchliệtkê cácnút(tênnúthoặcgiátrịchứabêntrongnút)theothứ tựđiquagọilàdanhsáchduyệtcây.  Cóbacáchduyệtcâyquantrọng: • Duyệttiềntự(preorder)NLR • Duyệttrungtự(inorder)LNR • Duyệthậutự(posorder)LRN 11 Các thuật ngữ cơ bảnĐịnhnghĩacácphépduyệtcâytổngquátmộtcáchđệ qui:  Câyrỗngthìdanhsáchduyệtcâylàrỗngvànóđược coilàbiểuthứcduyệttiềntự,trungtự,hậutựcủacây.  Câychỉcómộtnútthìdanhsáchduyệtcâygồmchỉ mộtnútđóvànóđượccoilàbiểuthứcduyệttiềntự, trungtự,hậutựcủacây. 12 Các thuật ngữ cơ bảnNgượclại:giảsửcâyTcónútgốclànvàcócáccâycon làT1,..,Tnthì:  BiểuthứcduyệttiềntựcủacâyTlàli ...