tailieunhanh - Bài giảng điện tử môn tin học: Cây nhị phân tìm kiếm

Cây nhị phân là cây có các nút đã được khoá hóa và được sắp xếp theo một thứ tự phản ánh vị trí của nút ở trong cây. | Gi¸o ¸n: C©y nhÞ ph©n t×m kiÕm Häc viªn thùc hiÖn: §ång ThÞ Thu Cao häc: K15 Cao häc K15 M«n: øng dông CNTT trong d¹y häc Néi dung chÝnh cña bµi I. §Þnh nghÜa c©y nhÞ ph©n II. BiÓu diÔn c©y nhÞ ph©n III. C¸c phÐp to¸n duyÖt c©y nhÞ ph©n iV. Mét sè thao t¸c trªn c©y nhÞ ph©n Bµi tËp ĐỊNH NGHĨA Cây nhị phân là cây có các nút đã được khoá hóa và được sắp xếp theo một thứ tự phản ánh vị trí của nút ở trong cây. Đặc điểm của cây nhị phân: Mọi nút trên cây chỉ có tối đa 2 con. Với mỗi một nút:+ Toàn bộ những nút ở cây con bên trái của nó đều có khoá nhỏ hơn khoá của nó. + Toàn bộ những nút ở cây con bên phải của nó đều có khoá lớn hơn khoá của nó. Ví dụ: Đây là cây nhị phân với toán tử ứng với gốc, toán hạng 1 ứng với cây con trái, toán hạng 2 ứng với cây con phải + + x * v y - z t u / Một số dạng đặc biệt của cây nhị phân A B C D E a) cây nhi phân lệch trái a A B C D E Cây nhị phân lệch phải b A C B D E D A B C E d c c, d) Cây nhị phân Cây zic- zắc Một số dạng đặc biệt của cây nhị phân (tiếp) Cây nhị phân gần đầy A C G H B E J D F I A C G B E J D F H I Cây nhị phân hoàn chỉnh A C G B E D F Cây nhị phân đầy đủ II. BIỂU DIỄN CÂY NHỊ PHÂN 1. Lưu trữ kế tiếp. Cây nhị phân đầy đủ: - Đánh số cho các nút trên cây theo thứ tự lần lượt từ mức 1 trở lên, hết mức này đến mức khác, từ trái sang phải đối với mỗi mức. Ví dụ: Đánh số cây ở hình dưới như sau: . 7 A C G B E D F 4 5 2 1 3 6 1. Lưu trữ kế tiếp (tiếp). Qui luật: - Con của nút thứ i là các nút 2i và 2i + 1 - Cha của nút thứ j là [j/2] Ta lưu trữ cây nhị phân đầy đủ bằng một vectơ V theo nguyên tắc: nút thứ i của cây được lưu trữ ở V[1]. Đó là cách lưu trữ kế tiếp, biết được địa chỉ nút cha sẽ tính được địa chỉ nút con và ngược lại. Vậy với cây trên ta sẽ có A B C D E F G V[1] V[2] V[3] V[4] V[5] V[6] V[7] 1. Lưu trữ kế tiếp (tiếp). Nhận xét: - Với cây nhị phân hoàn chỉnh mà các nút ở mức cuối đều dạt về phía trái thì cách lưu trữ này vẫn phù hợp. Các cây nhị phân khác thì cách lưu trữ này gây lãng phí do có nhiều phần | Gi¸o ¸n: C©y nhÞ ph©n t×m kiÕm Häc viªn thùc hiÖn: §ång ThÞ Thu Cao häc: K15 Cao häc K15 M«n: øng dông CNTT trong d¹y häc Néi dung chÝnh cña bµi I. §Þnh nghÜa c©y nhÞ ph©n II. BiÓu diÔn c©y nhÞ ph©n III. C¸c phÐp to¸n duyÖt c©y nhÞ ph©n iV. Mét sè thao t¸c trªn c©y nhÞ ph©n Bµi tËp ĐỊNH NGHĨA Cây nhị phân là cây có các nút đã được khoá hóa và được sắp xếp theo một thứ tự phản ánh vị trí của nút ở trong cây. Đặc điểm của cây nhị phân: Mọi nút trên cây chỉ có tối đa 2 con. Với mỗi một nút:+ Toàn bộ những nút ở cây con bên trái của nó đều có khoá nhỏ hơn khoá của nó. + Toàn bộ những nút ở cây con bên phải của nó đều có khoá lớn hơn khoá của nó. Ví dụ: Đây là cây nhị phân với toán tử ứng với gốc, toán hạng 1 ứng với cây con trái, toán hạng 2 ứng với cây con phải + + x * v y - z t u / Một số dạng đặc biệt của cây nhị phân A B C D E a) cây nhi phân lệch trái a A B C D E Cây nhị phân lệch phải b A C B D E D A B C E d c c, d) Cây nhị phân Cây zic- zắc Một số dạng đặc biệt của cây nhị .