Bài tập lớn: Cây nhị phân tìm kiếm

Sử dụng cấu trúc dạng cây, chúng ta cần dùng giải thuật nào với từng dạng dữ liệu để đạt hiệu quả cao nhất. Để giải quyết vấn đề trên ta cùng tìm hiểu một số phương pháp duyệt cây. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài tập lớn: Cây nhị phân tìm kiếm[Typetext] 1[Typetext]M ỤCL ỤC 2[Typetext] LờimởđầuCùngvớisựpháttriểncủakhoahọckĩthuật,côngnghệthôngtinnóichungvàbộmôncấutrúcdữliệuvàgiảithuậtnóiriêngngàycàngđượcứngdụngrộngrãitrongnhiềulĩnhvực.Vớimộtcơsởdữliệukhổnglồ,việcđưaramộtphươngphápnhằmgiảiquyếtvấnđềtìmkiếmdữliệucóhiệuquảvànhanhchóngnhấtluônđượcsựquantâmcủacácnhàpháttriểnphầnmềm.Thôngthườngdữliệuđượcbiểudiễndướidạngdanhsáchliênkết.Việctruysuấtdữliệuchưađạthiệuquảcao.Sửdụngcấutrúcdữliệucâylàmộtgiảipháplàmtănghiệusuấttrongcácthaotácxửlý.Vấnđềđặtra:vớiviệcsửdụngcấutrúcdạngcây,chúngtacầndùnggiảithuậtnàovớitừngdạngdữliệuđểđạthiệuquảcaonhất.Đểgiảiquyếtvấnđềtrêntacùngtìmhiểumộtsốphươngphápduyệtcây. 3[Typetext]I. CƠSỞLÝTHUYẾT I.1. Câynhịphântìmkiếm Cây(Trees)làmộttậphợphữuhạncácphầntửgọilànútcây(Node),trong đócómộtnútđặcbiệtgọilànútgốc(Root).Trêntậphợpcácnútnàycó mộtquanhệphâncấpgọilàquanhệchacon. Câynhịphântìmkiếm(binarysearchtree–BST)làcâynhịphântrongđótại mỗinút,khóacủanútđangxétlớnhơnnútkhóacủatấtcảcácnútthuộccây contráivànhỏhơntấtcảnútkhóathuộccâyconphải. Vídụ I.2. Mộtsốkháiniệm Mộtnútđơnđộccũnglàmộtcây. Tậphợprỗngcũnglàmộtcâymàtagọilàcâyrỗng. Mứccủamộtnút: +Nútgốc:Mức0. +Cácnútcáchnútgốcicạnhđượcgọilànútởmứci. Nútgốc(Root):Lànútkhôngcónútcha. Nútlá(leaf):Lànútkhôngcónútcon. Chiềucaocủamộtnút:Làđộdàiđườngđitừnútđóđếnnútláxanhất.. Chiềucaocủamộtcây:Làchiềucaocủanútgốc. 4[Typetext] Bậccủamộtnút:Làsốnútconcủanútđó. Bậccủamộtcây:Làbậccaonhấtcủacácnúttrongcây.II. MÔTẢCÁCTHAOTÁCTRÊNCÂYNHỊPHÂNTÌMKIẾM II.1. KhaibáocàiđặtcâynhịphânĐểbiểudiễncâynhịphântachọnphươngphápcấpphátliênkết.ứngvớimộtnútcủa,tadùngmộtbiếnđộnglưutrữcácthôngtin. Thôngtinlưutrữtạinút. Địachỉnútgốccủacâycontráitrongbộnhớ. Địachỉcủanútgốccủacâyconphảitrongbộnhớ. Khaibáotươngứngnhưsau: #include #include typedefintitem; structNODE { intkey; NODE*Left,*Right; typedefNODE*TREE; II.2. Hàmkhởitạorỗng voidkhoitaorong(TREE&T){ T=NULL; } II.3. Hàmkiểmtrarỗng intktrarong(TREET){ if(T==ULL) return1; 5[Typetext] else return0; } II.4. Hàmthêmmộtnút Hàmnàychophépchúngtanhậpthêmmộtsốvàodãysốmàtađãnhậpvà xétsốđóđểsắpxếpvàovịtrícủamộtnúttrongcây. Xảyrahaitrườnghợp: Câyrỗng. Câykhôngrỗng. NếuXtrùngvớigốcthìtakhôngthểthêmnode. NếuXgốcthìtathêmvàobênphải. II.5. Hàmxóamộtnút. Hàmchophéptaxóamộtnúttrongcâytìmkiếmnhịphân. Xảyrahaitrườnghợp. Câyrỗng. Câykhácrỗng. Xlànútlá. Xchỉcómộtcontrái(phải). Xcóđủcảhaicon Xâydựngthêmhàmtìmkiếm. Hàmtìmkiếmcónhiệmvụxácđịnhvịtrícủanútcầnxóa. II.6. Hàmnhậpmộtcâytìmkiếmnhịphân Chophéptanhậpnsốtamuốn,nsốđósẽtạothànhnnúttrongcây nhịphân. Hàmcònlàmthêmnhiệmvụsắpxếpvịtríđứngcủacácnútvừa nhập. 6[Typetext] II.7. Hàmduyệtcây II.7.1. Duyệttheothứtựtrước Hàmcónhiệmvụ: Thămnútgốc. Thămcácnútgốccủacâycontráitheothứtựtrước. Thămcácnútgốccủacâyconphảitheothứtựtrước. II.7.2. Duyệttheothứtựgiữa Hàmcónhiệmvụ: Thăm ...