TAILIEUCHUNG - 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

Ðức Ân 48 1 ppt

Upload

Bấm vào đây để xem trước nội dung

Tải xuống

TÀI LIỆU LIÊN QUAN

Bài giảng môn Tin học lớp 8 - Bài tập thực hành 1: Bước đầu giải bài toán tin học

14 99 3

Bài giảng Tin học 6 bài 1: Thông tin và tin học

16 149 0

Bài giảng Tin học 6 bài 2: Thông tin và biểu diễn thông tin

19 182 0

Bài giảng môn Tin học lớp 6 - Bài 1: Thông tin và dữ liệu

27 72 3

Bài giảng môn Tin học lớp 6 - Bài 3: Thông tin trong máy tính

29 61 3

Bài giảng môn Tin học lớp 6 - Bài 6: Mạng thông tin toàn cầu

23 76 5

Bài giảng môn Tin học lớp 6 - Bài 2: Xử lí thông tin

18 68 3

Bài giảng môn Tin học lớp 9 - Chủ đề 2: Mạng thông tin toàn cầu Internet

9 77 3

Bài giảng môn Tin học lớp 9 - Chủ đề 4: Bảo vệ thông tin trên máy tính

9 65 3

Bài giảng môn Tin học lớp 9 - Bài tập thực hành 4: Tạo và định dạng bài trình chiếu

15 72 3

TÀI LIỆU XEM NHIỀU

Một Case Về Hematology (1)

8 462064 59

Giới thiệu :Lập trình mã nguồn mở

14 23813 74

Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh

13 11125 536

Câu hỏi và đáp án bài tập tình huống Quản trị học

14 10365 458

Phân tích và làm rõ ý kiến sau: “Bài thơ Tự tình II vừa nói lên bi kịch duyên phận vừa cho thấy khát vọng sống, khát vọng hạnh phúc của Hồ Xuân Hương”

3 9647 106

Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)

249 8638 1148

Tiểu luận: Nội dung tư tưởng Hồ Chí Minh về đạo đức

16 8357 423

Mẫu đơn thông tin ứng viên ngân hàng VIB

8 7943 2249

Đề tài: Dự án kinh doanh thời trang quần áo nữ

17 6979 260

Giáo trình Tư tưởng Hồ Chí Minh - Mạch Quang Thắng (Dành cho bậc ĐH - Không chuyên ngành Lý luận chính trị)

152 6743 1610

TỪ KHÓA LIÊN QUAN

TÀI LIỆU MỚI ĐĂNG

Giáo án mầm non chương trình đổi mới: Gia đình vui nhộn

4 354 1 29-06-2024

Động cơ đốt trong và máy kéo công nghiêp tập 1 part 7

23 287 0 29-06-2024

Trading Strategies Profit Making Techniques For Stock_3

23 226 3 29-06-2024

báo cáo hóa học:" Increased androgen receptor expression in serous carcinoma of the ovary is associated with an improved survival"

6 125 1 29-06-2024

báo cáo hóa học:" Journal of the International AIDS Society: an important step forward"

2 113 0 29-06-2024

Quy Trình Canh Tác Cây Bông Vải

8 130 0 29-06-2024

Hướng dẫn chế độ dinh dưỡng cho người bệnh viêm khớp

5 141 0 29-06-2024

Tổng hợp Đề thi học sinh giỏi môn Sinh lớp 9 cấp huyện vòng 1 năm 2010-2011

12 203 2 29-06-2024

Đề tài " Dự báo về tác động của Tổ chức Thương mại Thế giới WTO đối với các doanh nghiệp xuất khẩu vừa và nhỏ Việt Nam – Những giải pháp đề xuất "

72 155 0 29-06-2024

Giáo dục kỹ năng sống mầm non: Làm gì khi bị trấn lột - Có kẻ lạ mặt rình bám theo bé

4 103 0 29-06-2024

TÀI LIỆU HOT

Mẫu đơn thông tin ứng viên ngân hàng VIB

8 7943 2249

Giáo trình Tư tưởng Hồ Chí Minh - Mạch Quang Thắng (Dành cho bậc ĐH - Không chuyên ngành Lý luận chính trị)

152 6743 1610

Ebook Chào con ba mẹ đã sẵn sàng

112 4020 1300

Ebook Tuyển tập đề bài và bài văn nghị luận xã hội: Phần 1

62 5701 1194

Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)

249 8638 1148

Giáo trình Văn hóa kinh doanh - PGS.TS. Dương Thị Liễu

561 3634 665

Giáo trình Sinh lí học trẻ em: Phần 1 - TS Lê Thanh Vân

122 3846 601

Giáo trình Pháp luật đại cương: Phần 1 - NXB ĐH Sư Phạm

274 4402 545

Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh

13 11125 536

Bài tập nhóm quản lý dự án: Dự án xây dựng quán cafe

35 4292 483