tailieunhanh - Tài liệu hướng dẫn thực hành môn Cấu trúc dữ liệu và giải thuật - Bài 4: Cây nhị phân tìm kiếm

Hoàn tất bài thực hành này, sinh viên có thể: Hiểu được các thành phần của cây nhị phân tìm kiếm; thành thạo các thao tác trên cây nhị phân tìm kiếm: tạo cây, thêm phần tử, xóa phần tử, duyệt cây nhị phân tìm kiếm; áp dụng cấu trúc dữ liệu cây nhị phân tìm kiếm vào việc giải quyết một số bài toán đơn giản. | CÂY NH PHÂN TÌM KI M M C TIÊU Hoàn t t bài th c hành này, sinh viên có th : - Hi u ư c các thành ph n c a cây nh phân tìm ki m. - Thành th o các thao tác trên cây nh phân tìm ki m: t o cây, thêm ph n t , xóa ph n t , duy t cây nh phân tìm ki m. - Áp d ng c u trúc d li u cây nh phân tìm ki m vào vi c gi i quy t m t s bài toán ơn gi n. Th i gian th c hành: t 120 phút n 400 phút TÓM T T Cây nh phân tìm ki m là cây có t i a 2 nhánh (cây con), nhánh trái và nhánh ph i. Cây nh phân tìm ki m có các tính ch t sau: - Khóa c a t t c các nút thu c cây con trái nh hơn khóa nút g c. - Khóa c a nút g c nh hơn khóa c a t t c các nút thu c cây con ph i. - Cây con trái và cây con ph i c a nút g c cũng là cây nh phân tìm ki m M t s khái ni m: Nút lá có cao b ng 1 Trang 1 - Tài li u hư ng d n th c hành môn C u trúc d HCMUS 2010 li u và gi i thu t Ví d cây nh phân tìm ki m: Trong m i nút c a cây nh phân tìm ki m, thông tin liên k t là vô cùng quan tr ng. Ch c n m t x lý không c n th n có th làm m t ph n liên k t này thì cây s b ‘gãy’ cây con liên quan ng v i liên k t ó (không th truy xu t ti p t t c các nút c a nhánh con b m t). Các thao tác cơ b n trên cây nh phân tìm ki m: - Thêm 1 nút: d a vào tính ch t c a cây nh phân tìm ki m tìm v trí thêm nút m i. o T o cây: t cây r ng, l n lư t thêm các nút vào cây b ng phương th c thêm nút vào cây nh phân tìm ki m Xóa 1 nút: là nút lá, là nút có 1 nhánh con, là nút có 2 nhánh con. - Duy t cây nh phân tìm ki m: có th i ư c h t các ph n t trên cây nh phân tìm ki m: duy t trư c (NLR), duy t gi a (LNR), duy t sau (LRN). Do tính ch t c a cây nh phân tìm ki m, phép duy t gi a cho phép duy t các khóa c a cây theo th t tăng d n Trang 2 - Tài li u hư ng d n th c hành môn C u trúc d HCMUS 2010 li u và gi i thu t N I DUNG TH C HÀNH Cơ b n Sinh viên c k phát bi u bài t p và th c hi n theo hư ng d n: T ch c m t cây nh phân tìm ki m trong ó m i ph n t ch a thông tin d li u là s nguyên. Ngư i dùng s nh p các giá tr .