intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST
Báo xấu
34
lượt xem 8
download
 
  Download Vui lòng tải xuống để xem tài liệu đầ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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 8/4/2020 3.3.1 Cài đặt cây bởi mảng ❖Nhận xét ▪ Hàm PARENT(n,T) tốn chỉ một hằng thời gian ▪ Các hàm đòi hỏi thông tin về các con không làm việc tốt (vì phải tốn vòng lặp để dò tìm), vd: tìm nút con trái nhất của nút i là không thể xác định được. ❖Khắc phục bằng qui ước: ▪ Đánh số theo thứ tự tăng dần bắt đầu tại nút gốc. ▪ Nút cha được đánh số trước các nút con. ▪ Các nút con cùng một nút cha được đánh số lần lượt từ trái sang phải →Cách lưu trữ này chỉ phù hợp với cây mà các nút của cây khác nhau từng đôi một Chương 3. Cây 91 3.3.1 Cài đặt cây bởi mảng ❖Ví dụ 0 A 1 B 2 C 3 D 4 E 5 I 6 J F G H 7 8 9 A B C D E I J F G H … Nhãn của các nút trên cây -1 0 0 1 1 2 2 4 4 4 … Cha của nút trên cây 0 1 2 3 4 5 6 7 8 9 … Chỉ số của mảng Chương 3. Cây 92 46
  8. 8/4/2020 3.3.1 Cài đặt cây bởi mảng ❖ Khai báo cấu trúc dữ liệu #define MAXSIZE ... /* chỉ số tối đa của mảng */ typedef ... DataType; typedef int Node; typedef struct { DataType Data[MAXSIZE];/* Nhãn của nút trong cây */ Node Parent[MAXSIZE]; /* Cha của các nút trong cây */ int MaxNode; /* Số nút thực sự trong cây */ } Tree; Chương 3. Cây 93 3.3.1 Cài đặt cây bởi mảng ❖Cài đặt các phép toán (yêu cầu sv viết chương trình) Chương 3. Cây 94 47
  9. 8/4/2020 3.3.2 Cài đặt cây bởi danh sách các con ❖Quy ước: ▪ Mỗi nút có một danh sách các nút con. ▪ Vì số nút con của một nút là không biết trước nên dùng danh sách liên kết. ❖Khai báo cấu trúc dữ liệu typedef struct node { DataType Item; node *next; } typedef node *childlist; childlist tree[maxsize]; ❖Ví dụ: Chương 3. Cây 95 3.3.2 Cài đặt cây bởi danh sách các con Chương 3. Cây 96 48
  10. 8/4/2020 3.3.2 Cài đặt cây bởi danh sách các con ❖Nhận xét ❖Các hàm đòi hỏi thông tin về các con làm việc rất thuận lợi, nhưng hàm PARENT lại không làm việc tốt. ❖Ví dụ: tìm nút cha của nút G đòi hỏi ta phải duyệt tất cả các danh sách chứa các nút con. Chương 3. Cây 97 3.4 Cây nhị phân (Binary Tree) 3.4.1 Khái niệm 3.4.2 Biểu diễn và các thao tác trên cây 3.4.3 Ứng dụng Chương 3. Cây 98 49
  11. 8/4/2020 3.4.1 Khái niệm ❖Cây nhị phân là cây mà mỗi đỉnh có tối đa 2 cây con ❖Cây nhị phân suy biến: cây lệch trái, cây lệch phải, cây dích dắc 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 Chương 3. Cây 99 3.4.1 Khái niệm ❖Cây nhị phân hoàn chỉnh(Perfect/Full binary tree): Là cây nhị phân mà mọi nút đều có đủ hai con, trừ những nút ở mức cao nhất đều là nút lá (không có con) Chương 3. Cây 100 50
  12. 8/4/2020 3.4.1 Khái niệm ❖Cây nhị phân đầy đủ ( Complete Binary tree): là cây nhị phân mà nếu liệt kê các nút theo trình tự từ mức thấp đến mức cao, ở mỗi mức thì theo trình tự từ trái sang phải ta sẽ được một dãy liên tục không khuyết nút nào. (cây đầy đủ trái) Chương 3. Cây 101 3.4.2 Biểu diễn và các phép toán trên cây ❖Biểu diễn bằng mảng ▪ Đánh số thứ tự các nút theo thứ tự “ trên – dưới” và “trái – phải”. ▪ Với nút i thì • nút con trái của nó 2i và nút con phải là 2i+1. • Nút cha là [i/2]. Chương 3. Cây 102 51
  13. 8/4/2020 3.4.2 Biểu diễn và các phép toán trên cây ❖Ví dụ A 1 1 2 3 4 5 6 7 A B E C D F G 2 B E 3 C D F G 4 5 6 7 Chương 3. Cây 103 3.4.2 Biểu diễn và các phép toán trên cây ❖Ưu điểm: ▪ Cấu trúc mảng tạo thuận lợi khi triển khai các phép toán. ▪ Truy cập nhanh chóng vào bất cứ nút nào, chi phí truy cập là đồng đều cho mọi nút. (từ con→cha và ngược lại đều dễ dàng) ❖Nhược điểm: ▪ Lãng phí bộ nhớ nếu cây gầy, khuyết nhiều nút Chương 3. Cây 104 52
  14. 8/4/2020 3.4.2 Biểu diễn và các phép toán trên cây ❖Biểu diễn bằng danh sách liên kết ❖Quy ước: Mỗi nút là một bản ghi bao gồm: ▪ Trường Data lưu giá trị ▪ Trường Left chứa liên kết trỏ tới nút con trái hoặc Null. ▪ Trường Right chứa liên kết trỏ tới nút con phải hoặc Null. → Nút gốc sẽ là nút đầu tiên của danh sách móc nối, các nút lá có trường Left và Right đều chứa giá trị Null. Chương 3. Cây 105 3.4.2 Biểu diễn và các phép toán trên cây Chương 3. Cây 106 53
  15. 8/4/2020 3.4.2 Biểu diễn và các phép toán trên cây ❖Khai báo cấu trúc dữ liệu typedef struct node { int data; struct node *left; struct node *right; }node; typdef struct node *btree; Chương 3. Cây 107 3.4.2 Biểu diễn và các phép toán trên cây ❖Duyệt cây nhị phân: là thực hiện một thao tác xử lý phần dữ liệu trong mọi nút đúng một lần. ❖Quy tắc duyệt: nút nào cũng được ‘thăm’ và mỗi nút được ‘thăm’ đúng một lần. ❖Cách duyệt: dựa theo thứ tự duyệt của nút gốc, cây con trái và cây con phải. Phép duyệt được thực hiện một cách đệ quy. ▪ Duyệt theo thứ tự trước (preorder traversal) ▪ Duyệt theo thứ tự giữa (inorder traversal) ▪ Duyệt theo thứ tự sau (postorder traversal) Chương 3. Cây 108 54
  16. 8/4/2020 3.4.2 Biểu diễn và các phép toán trên cây ❖Duyệt theo thứ tự trước ▪ Thăm nút → xử lý dữ liệu ▪ Duyệt cây con trái theo thứ tự trước ▪ Duyệt cây con phải theo thứ tự trước Thứ tự duyệt: abdce Chương 3. Cây 109 3.4.2 Biểu diễn và các phép toán trên cây ❖Duyệt theo thứ tự sau: ▪ Duyệt cây con trái theo thứ tự ▪ Duyệt cây con phải theo thứ tự trước ▪ Thăm nút Thứ tự duyệt: dbeca Chương 3. Cây 110 55
  17. 8/4/2020 3.4.2 Biểu diễn và các phép toán trên cây ❖Duyệt theo thứ tự giữa ▪ Duyệt cây con trái theo thứ tự giữa ▪ Thăm nút ▪ Duyệt cây con phải theo thứ tự giưa Thứ tự duyệt: bdaec Chương 3. Cây 111 3.4.2 Biểu diễn và các phép toán trên cây ❖Ví dụ: Chương 3. Cây 112 56
  18. 8/4/2020 3.4.2 Biểu diễn và các phép toán trên cây ❖Cài đặt chương trình void firstorder(btree t){ // duyệt thứ tự trước if (t==NULL) exit(0); else { coutleft); cout
  19. 8/4/2020 3.4.3 Ứng dụng ❖Ứng dụng của phép duyệt cây ▪ Tính chiều cao của cây (yêu cầu viết hàm) ▪ Tính số nút/số nút lá của cây (yêu cầu viết hàm) ▪ Tính kích thước của cây ▪ Sao chép cây ▪ … ❖ứng dụng của cây nhị phân ▪ Biều diễn biểu thức: Tính giá trị biểu thức, tính đạo hàm ▪ Cây quyết định Chương 3. Cây 115 3.5 Cây nhị phân tìm kiếm 3.5.1 Khái niệm 3.5.2 Biểu diễn và các thao tác 3.5.3 Ứng dụng Chương 3. Cây 116 58
  20. 8/4/2020 3.5.1 Khái niệm ❖Cây nhị phân tìm kiếm là một cây nhị phân mà mỗi nút của nó đều được gán một giá trị khóa và mọi nút trên cây phải thỏa mãn: ❖Giá trị của các nút của cây con trái nhỏ hơn giá trị của nút gốc; ❖Giá trị của các nút cây con phải lớn hơn giá trị của nút gốc; ❖Cây con trái và cây con phải cũng là cây tìm kiếm nhị phân. ❖Các giá trị khóa là khác nhau. Chương 3. Cây 117 3.5.1 Khái niệm ❖Ví dụ Chương 3. Cây 118 59
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2