CTDL 2005 chuong 9

Cây nhị phân
Nội dung trích xuất từ tài liệu:
CTDL 2005 chuong 9Chöông 9 – Caây nhò phaânChöô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øybaè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átnhieà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öõuhaï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ùtgoï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ùtgoá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 O D C N Y S E L B T X (a)M- A- - N- - C- - -B M(A(NC(B))DO(Y(TX)ELS))- D (c)- O- - Y- - - T- - - X- - E- - L- - S (b) Hình 9.1 – Caùc caùch bieåu dieãn cuûa caâyGiaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät 183Chöô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ùcnuù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ùttrong (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ùnchuùng ta cuõng caàn goïi teân nhö vaäy ñeå trình baøy giaûi thuaät). Theo hình 9.1, caùc nuùt laù goàm: N, B, D, T, X, E, L, S; caùc nuùt trung gian goàm:A, C, O, Y. Nuùt Y laø cha cuûa hai nuùt T vaø X. T vaø X laø con cuûa Y, vaø laø nuùt anhem vôùi nhau. Ñöôøng ñi (path) töø nuùt n1 ñeán nuùt nk ñöôïc ñònh nghóa laø moät daõy caùc nuùt n1,n2, …, nk sao cho ni laø nuùt cha cuûa nuùt ni+1 vôùi 1≤ i< k. Chieàu daøi (length) ñöôøngñi naøy laø soá caønh treân noù, ñoù laø k-1. Moãi nuùt coù ñöôøng ñi chieàu daøi baèng 0 ñeánchính noù. Trong moät caây, töø nuùt goác ñeán moãi nuùt coøn laïi chæ coù duy nhaát moätñöôøng ñi. Ñoái vôùi moãi nuùt ni, ñoä saâu (depth) hay coøn goïi laø möùc (level) cuûa noù chính laøchieàu daøi ñöôøng ñi duy nhaát töø nuùt goác ñeán noù coäng 1. Nuùt goác coù möùc baèng 1.Chieàu cao (height) cuûa nuùt ni laø chieàu daøi cuûa ñöôøng ñi daøi nhaát töø noù ñeán moätnuùt laù. Moïi nuùt laù coù chieàu cao baèng 1. Chieàu cao cuûa caây baèng chieàu cao cuûanuùt goác. Ñoä saâu cuûa caây baèng ñoä saâu cuûa nuùt laù saâu nhaát, noù luoân baèng chieàu caocuûa caây. Neáu giöõa nuùt n1 vaø nuùt n2 coù moät ñöôøng ñi, thì n1 ñöôc goïi laø nuùt tröôùc(ancestor) cuûa n2 vaø n2 laø nuùt sau (descendant) cuûa n1. M laø nuùt tröôùc cuûa nuùt B. M laø nuùt goác, coù möùc laø 1. Ñöôøng ñi töø M ñeán B laø:M, A, C, B, coù chieàu daøi laø 3. B coù möùc laø 4. B laø nuùt laù, coù chieàu cao laø 1. Chieàu cao cuûa C laø 2, cuûa A laø 3, vaø cuûa M laø 4chính baèng chieàu cao cuûa caây. Moät caây coù theå ñöôïc chia thaønh nhieàu caây con (subtree). Moät caây con laø baát kyømoät caáu truùc caây beân döôùi cuûa nuùt goác. Nuùt ñaàu tieân cuûa caây con laø nuùt goác cuûa noùvaø ñoâi khi ngöôøi ta duøng teân cuûa nuùt naøy ñeå goïi cho caây con. Caây con goác A (haygoïi taét laø caây con A) goàm caùc nuùt A, N, C, B. Moät caây con cuõng coù theå chia thaønhnhieàu caây con khaùc. Khaùi nieäm caây con daãn ñeán ñònh nghóa ñeä quy cho caây nhösau:Giaùo trình Caáu truùc Döõ lieäu vaø Giaûi thuaät ...