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ả
Nội dung trích xuất từ tài liệu:
Giáo trình cấu trúc dữ liệu part 7Cấu trúc dữ liệu Chương III: Cấu trúc câyGiả 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.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ủacâ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útcự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ợptrên.Giải thuật xoá một nút có khoá nhỏ nhất 97 TrangCấu trúc dữ liệu Chương III: Cấu trúc câyHà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);} 98 TrangCấu trúc dữ liệu Chương III: Cấu trúc câyTỔNG KẾT CHƯƠNGChươ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ềmkiế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áchcài đặt các phép toán cơ bản trên các dạng cây khác nhau theo từng cách cài đặt. 99 TrangCấu trúc dữ liệu Chương III: Cấu trúc cây BÀI TẬP1. Trình bày các biểu thức duyệt tiền tự, trung tự, hậu tự của cây sau:2. Duyệt cây theo mức là duyệt bắt đầu từ gốc, rồi duyệt các nút nằm trên mức 1 theo thứ tựtừ trái sang phải, rồi đến các nút nằm trên mức 2 theo thứ tự từ trái sang phải...Và cứ nhưvậy.a. Hãy liệt kê các nút theo thứ tự duyệt theo mức của cây trong bài 1.b. Viết thủ tục duyệt cây theo mức. (Gợi ý: dùng hàng đợi)3. Vẽ cây biểu diễn cho biểu thức ((a+b)+c*(d+e)+f)*(g+h)Trình bày biểu thức tiền tố và hậu tố của biểu thức đã cho.4. Viết chương trình để tính giá trị của biểu thức khi cho:a. Biểu thức tiền tốb. Biểu thức hậu tố.Ví dụ:- đầu vào (input): * + 6 4 5- thì đầu ra (output) sẽ là: 50 vì biểu thức trên là dạng tiền tố của (6+4) * 5Tương tự:- đầu vào (input): 6 4 5 + *- thì đầu ra (output) sẽ là: 54 vì biểu thức trên là dạng hậu tố của 6 * (4+5) 100 TrangCấu trúc dữ liệu Chương III: Cấu trúc cây5. Cho cây nhị phâna. Hãy trình bày các duyệt: tiền tự (node-left-right), trung tự (left-node-right), hậu tự(left-right-node).b. Minh hoạ sự lưu trữ kế tiếp các nút cây này trong mảng.6. Chứng minh rằng: nếu biết biểu thức duyệt tiền tự và trung tự của một cây nhị phân thì tadựng được cây này.Điều đó đúng nữa không? Khi biết biểu thức duyệt:a. Tiền tự và hậu tựb. Trung tự và hậu tự7. Nêu các trường hợp mà các giải thuật trên cây TK ...