Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Cây

Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Cây. Chương này có nội dung trình bày về: định nghĩa và khái niệm cơ bản; một số phép toán trên cây; cài đặt cây; cây nhị phân; cây tìm kiếm nhị phân; cây cân bằng;... Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Cây 8/4/2020 2.2.4 Cài đặt bởi mảng ❖Ưu điểm: ▪ Truy cập nhanh, ngẫu nhiên và như nhau đối với mọi phần tử nhờ vào chỉ số ▪ Thao tác tìm kiếm dễ dàng ❖Nhược điểm ▪ Kích thước mảng trong mọi ngôn ngữ lập trình đều cố định→ Hạn chế độ dài của danh sách, trong khi danh sách thường xuyên thêm bớt không cố định độ dài ▪ Việc thêm bớt khó khăn do phải dịch chuyển nhiều phần tử (thời gian chạy là O(n)) Cấu trúc dữ liệu và giải thuật 79 CHƯƠNG 3: CÂY (9t) 3.1 ĐỊnh nghĩa và khái niệm cơ bản 3.2 Một số phép toán trên cây 3.3 Cài đặt cây 3.4 Cây nhị phân 3.5 Cây tìm kiếm nhị phân 3.6 Cây cân bằng Chương 3. Cây 80 40 8/4/2020 3.1 Định nghĩa và khái niệm cơ bản 3.1.1 Định nghĩa 3.1.2 Các khái niệm cơ bản về cây Chương 3. Cây 81 3.1.1 Định nghĩa Cây: (Tree) ❖ Cây T là một bộ , trong đó: V: Tập hữu hạn các phần tử (nút) E: Tập hữu hạn(cung) thể hiện mối quan hệ phân cấp là quan hệ “ cha – con”. Kí hiệu: T= ❖ Nút gốc (root): là nút không phải là con của bất cứ nút nào ❖ Cây rỗng (null tree): là cây không có nút nào Chương 3. Cây 82 41 8/4/2020 3.1.1 Định nghĩa Các ví dụ về cấu trúc cây ❖Mục lục của một cuốn sách ❖Cấu trúc thư mục trên đĩa máy tính. ❖Sơ đồ nhân sự của tổ chức ❖Cây phả hệ ❖Dùng cây để biểu diễn biểu thức số học, chẳng hạn: ( a+b) x (c-d/e) Chương 3. Cây 83 3.1.1 Định nghĩa x - + c / a b d e Chương 3. Cây 84 42 8/4/2020 3.1.2 Các khái niệm cơ bản về cây ❖Số các con của một nút gọi là cấp/bậc (degree) của nút đó ▪ Nút có bậc bằng 0 gọi là nút lá (leaf) ▪ Các nút không phải nút lá gọi là nút nhánh ( branch) ▪ Bậc cao nhất có trong các nút của một cây gọi là bậc của cây đó. ❖Mức-Level: Gốc của cây có mức 1, nếu một nút có mức i thì các nút con của nút đó có mức i+1. ▪ Chiều cao (height) của cây là số mức lớn nhất của các nút có trên cây đó Chương 3. Cây 85 3.1.2 Các khái niệm cơ bản về cây ❖Cây có thứ tự: là cây mà có xét đến thứ tự giữa các con của một nút ▪ Con trưởng/con cực trái của một nút: là con thứ nhất trong quan hệ thứ tự giữa các nút cùng cha ▪ Em liền kề của một nút: là nút đứng ngay sau trong quan hệ thứ tự giữa các nút cùng cha ❖Cây có nhãn: mỗi nút của cây được gán một nhãn. Nhãn có thể là kiểu số nguyên, kiểu ký tự hay một kiểu dữ liệu khác khác tạp hơn ❖Rừng:Tập hợp hữu hạn các cây phân biệt gọi là một rừng (forest). Chương 3. Cây 86 43 8/4/2020 3.1.2 Các khái niệm cơ bản về cây A 1 B C D 2 E F G H I 3 J K 4 Chương 3. Cây 87 3.2 Một số phép toán trên cây ❖Khởi tạo cây rỗng: void Initialize(TypeTree T); ❖Xác định nút gốc: Ref Root(TypeTree T); ❖Xác định nút cha của một nút: Ref Parent(TypeTree T, TypeNode V); ❖Tìm con trưởng của một nút Ref EldestChild(TypeTree T, TypeNode V); ❖Xác định em liền kề của một nút: Ref NextSibling(TypeTree T,TypeNode V); ❖Duyệt cây: truy cập mọi nút để thực hiện một xử lý nào đó →không sót, không lặp: Void Traverse(TypeTree T); Chương 3. Cây 88 44 8/4/2020 3.3 Cài đặt cây 3.3.1 Cài đặt cây bởi mảng 3.3.2 Cài đặt cây bởi danh sách các con 3.3.3 Cài đặt cây bằng con trỏ 3.3.4 Ứng dụng Chương 3. Cây 89 3.3.1 Cài đặt cây bởi mảng ❖ Quy ước: ❖ Cho cây T có n nút ❖ Gán tên cho các nút lần lượt là 0, 1, 2, .., n-1. ❖ Dùng một mảng một chiều a để lưu trữ cây bằng cách cho a[i] = j với j là nút cha của nút i. Nếu i là nút gốc ta cho a[i] = -1 vì nút gốc không có cha ❖ Nếu cây T là cây có nhãn, ta có thể dùng thêm một mảng một chiều L chứa các nhãn của cây bằng cách cho L[i] = x với x là nhãn của nút i, hoặc khai báo a là một struct có ba trường: trường Parent là một mảng giữ chỉ số nút cha; trường Data là một mảng giữ nhãn của nút và một trường MaxNode giữ số nút hiện tại đang có trên cây Chương 3. Cây 90 45 8/4/2020 3.3.1 Cài đặt cây bởi mảng ❖Nhận xé ...