Đang chuẩn bị liên kết để tải về tài liệu:
Giáo trình Cấu trúc dữ liệu & giải thuật: Phần 2

Giáo trình Cấu trúc dữ liệu & giải thuật - Phần 2 gồm có những nội dung chính sau: Cây nhị phân, cây nhiều nhánh, hàng ưu tiên, bảng và truy xuất thông tin, đồ thị, ứng dụng của ngăn xếp, ứng dụng của hàng đợi, ứng dụng xử lý văn bản. . | Chöông 9 – Caây nhò phaân Chöông 9 – CAÂY NHÒ PHAÂN So vôùi hieän thöïc lieân tuïc cuûa caùc caáu truùc döõ lieäu, caùc danh saùch lieân keát coù nhöõng öu ñieåm lôùn veà tính meàm deûo. Nhöng chuùng cuõng coù moät ñieåm yeáu, ñoù laø söï tuaàn töï, chuùng ñöôïc toå chöùc theo caùch maø vieäc di chuyeån treân chuùng chæ coù theå qua töøng phaàn töû moät. Trong chöông naøy chuùng ta khaéc phuïc nhöôïc ñieåm naøy baèng caùch söû duïng caùc caáu truùc döõ lieäu caây chöùa con troû. Caây ñöôïc duøng trong raát nhieàu öùng duïng, ñaëc bieät trong vieäc truy xuaát döõ lieäu. 9.1. Caùc khaùi nieäm cô baûn veà caây Moät caây (tree) - hình 9.1- goàm moät taäp höõu haïn caùc nuùt (node) vaø moät taäp höõu haïn caùc caønh (branch) noái giöõa caùc nuùt. Caønh ñi vaøo nuùt goïi laø caønh vaøo (indegree), caønh ñi ra khoûi nuùt goïi laø caønh ra (outdegree). Soá caønh ra töø moät nuùt goïi laø baäc (degree) cuûa nuùt ñoù. Neáu caây khoâng roãng thì phaûi coù moät nuùt goïi laø nuùt goác (root), nuùt naøy khoâng coù caønh vaøo. Caây trong hình 9.1 coù M laø nuùt goác. Caùc nuùt coøn laïi, moãi nuùt phaûi coù chính xaùc moät caønh vaøo. Taát caû caùc nuùt ñeàu coù theå coù 0, 1, hoaëc nhieàu hôn soá caønh ra. M A N O D C B Y T E L S X (a) M - A D N C - B O (b) Y E L S M(A(NC(B))DO(Y(TX)ELS)) (c) T X Hình 9.1 – Caùc caùch bieåu dieãn cuûa caây Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät 183 Chöông 9 – Caây nhò phaân Nuùt laù (leaf) ñöôïc ñònh nghóa nhö laø nuùt cuûa caây maø soá caønh ra baèng 0. Caùc nuùt khoâng phaûi nuùt goác hoaëc nuùt laù thì ñöôïc goïi laø nuùt trung gian hay nuùt trong (internal node). Nuùt coù soá caønh ra khaùc 0 coù theå goïi laø nuùt cha (parent) cuûa caùc nuùt maø caønh ra cuûa noù ñi vaøo, caùc nuùt naøy cuõng ñöôïc goïi laø caùc nuùt con (child) cuûa noù. Caùc nuùt cuøng cha ñöôïc goïi laø caùc nuùt anh em (sibling) vôùi nhau. Nuùt treân nuùt cha coù theå goïi laø nuùt oâng (grandparent, trong moät soá baøi toaùn chuùng ta