Đ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 part 7

Tham khảo tài liệu 'giáo trình cấu trúc dữ liệu part 7', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Cấu trúc dữ liệu Ch ương III Cấu trúc cây Giả sử ta muốn xoá một nút có khoá x trước hết ta phải tìm kiếm nút chứa khoá x trên cây. Xoá nút có khoá 18 lả nút trung gian cổ một nút con Xoá nủt cỏ khoá 1 5 lả nủt trung gian cỏ hai nút con Việc xoá một nút như vậy tất nhiên ta phải bảo đảm cấu trúc cây TKNP không bị phá vỡ. Ta có các trường hợp như hình III.17 Hình III.17 Ví dụ về giải thuật xóa nút trên cây Nếu không tìm thấy nút chứa khoá x thì giải thuật kết thúc. Nếu tìm gặp nút N có chứa khoá x ta có ba trường hợp sau xem hình III.17 Nếu N là lá ta thay nó bởi NULL. N chỉ có một nút con ta thay nó bởi nút con của nó. N có hai nút con ta thay nó bởi nút lớn nhất trên cây con trái của nó nút cực phải của cây con trái hoặc là nút bé nhất trên cây con phải của nó nút cực trái của cây con phải . Trong giải thuật sau ta thay x bởi khoá của nút cực trái của cây con bên phải rồi ta xoá nút cực trái này. Việc xoá nút cực trái của cây con bên phải sẽ rơi vào một trong hai trường hợp trên. Giải thuật xoá một nút có khoá nhỏ nhất Trang 97 Cấu trúc dữ liệu Ch ương III Cấu trúc cây Hàm dưới đây trả về khoá của nút cực trái đồng thời xoá nút này. KeyType DeleteMin Tree Root KeyType k if Root - left NULL k Root - key Root Root - right return k else return DeleteMin Root- left Thủ tục xóa một nút có khoá cho trước trên cây TKNP void DeleteNode key X Tree Root if Root NULL if x Root - Key DeleteNode x Root- left else if x Root - Key DeleteNode x Root- right else if Root - left NULL Root - right NULL Root NULL else if Root - left NULL Root Root - right else if Root - right NULL Root Root - left else Root - Key DeleteMin Root- right Trang 98 Cấu trúc dữ liệu Ch ương III Cấu trúc cây TỔNG KẾT CHƯƠNG Chương này giới thiệu một số khái niệm cơ bản về cây tổng quát cây nhị phân và cây tiềm kiếm nhị phân. Bên cạnh đó chương này cũng đề cập đến cách lưu trữ cây trong bộ nhớ như cài đặt cây bằng mảng con trỏ danh sách các con con trái nhất anh em ruột phải và cách cài đặt các phép toán cơ .