Bài giảng Cấu trúc và dữ liệu giải thuật - Chương 4: Cây - Phạm Thanh An

62 trang ngocly 3990

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc và dữ liệu giải thuật - Chương 4: Cây - Phạm Thanh An", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

bai_giang_cau_truc_va_du_lieu_giai_thuat_chuong_4_cay_pham_t.ppt

Nội dung text: Bài giảng Cấu trúc và dữ liệu giải thuật - Chương 4: Cây - Phạm Thanh An

Chương 4: Cây Ths. Phạm Thanh An Bộ môn Khoa học máy tính - Khoa CNTT Trường Đại học Ngân hàng TP.HCM LOGO
Mục tiêu ❖Trang bị cho sinh viên các khái niệm và ứng dụng cây ❖Cài đặt và thực hiện các phép toán trên cây, đặc biệt là các phép toán trên cây nhị phân nhị phân tìm kiếm.
Nội dung ❖ Định nghĩa và các khái niệm ❖ Cây nhị phân ❖ Cây nhị phân tìm kiếm (BST) ❖ Cây tổng quát
Cây (trong máy tính) Gốc Lá Nhánh Nút
Khái niệm về cây (tree) ❖ Là tập hữu hạn các nút (tree node), sao cho ▪ Có một nút gọi là nút gốc (root) ▪ Các nút còn lại được phân hoạch thành n tập riêng biệt T1, T2 , , Tn, mỗi tập Ti là một cây ▪ Giữa các nút có quan hệ phân cấp (hierarchical relationship) gọi là “quan hệ cha con” ❖ Cây không có nút gọi là cây rỗng (null tree)
Biểu diễn cây ❖Bằng đồ thị ❖Bằng giản đồ ❖Bằng danh sách (các dấu ngoặc lồng nhau) ❖Bằng phương pháp Indentatio
Biểu diễn cây ❖Bằng đồ thị A / B C D A B C D E E F G H F G H I J I J K Cây con
Biểu diễn cây ❖Bằng giản đồ D B A J G H I E C F
Biểu diễn cây ❖ Bằng danh sách (các dấu ngoặc lồng nhau) (/( A (C (F), D (G ( J ) ) ) ), (B (E ( H, I ) ) ) ) A / B C D A B C D E E F G H I J F G H I K L M J ( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) )
Biểu diễn cây ❖Bằng phương pháp Indentatio A C F / D A B G J C D E B F E G H I H J I
Các thuật ngữ ❖ Bậc của nút và bậc của cây A ▪ Nút A: bậc 3, nút C bậc 1 ▪ Bậc của cây: 3 B C D ❖ Nút gốc, Nút lá và nút nhánh E F G H I J ❖ Nút cha (Parent), nút con K L M (children)
Các thuật ngữ ❖Đường đi (path) / A B C D E F G H I J
Các thuật ngữ ❖Mức của nút và chiều cao của cây Root 1 2 Chiều cao 3 của cây: 5 4 5
Các thuật ngữ ❖ Tổ tiên (ancestors) của một / nút ▪ Tổ tiên của nút J A B ❖ Con cháu (Descendant) của C D E một nút: ▪ Con cháu của B F G H I ❖ Các con của cùng một cha gọi là anh em ruột (siblings) J
Cây có thứ tự và Rừng ❖Cây có thứ tự (ordered tree) ▪ Một cây gọi là có thứ tự khi ta thay đổi vị trí của các cây con, ta nhận được một cây mới ❖Rừng (forest) ▪ Tập hợp hữu hạn các cây phân biệt ▪ Nếu bỏ đi nút gốc của một cây, ta sẽ thu được một rừng gồm nhiều cây phân biệt
Cây nhị phân ❖Định nghĩa Cây con Cây con trái phải
Cây nhị phân ❖ Cây nhị phân biểu diễn biểu thức toán học
Tính chất của cây nhị phân ❖ Số nút tối đa mức i trong cây 2i-1 ❖ Số nút tối đa trong cây là 2h-1 (h chiều cao của cây) Chiều cao của cây 1 h log2N (N là số nút trong cây). 2 3 4 5
Cây nhị phân hoàn chỉnh / A B C D I E G J G Các nút ứng với các mức trừ mức cuối đều đạt tối đa, ở mức cuối, các nút đều đạt về phía trái
Cây nhị phân đầy đủ / A B C D I E Các nút đạt tối đa ở cả mọi mức
Cây nhị phân gần đầy / A B C D I E J G G Các nút ứng với các mức trừ mức cuối đều đạt tối đa, ở mức cuối, các nút không dạt đều về phía trái
Tổ chức lưu trữ cây nhị phân ❖ Sử dụng mảng một chiều (lưu trữ kế tiếp) ▪ Đánh số thứ tự từ gốc, tại mỗi mức, đánh số các nút từ trái sang phải, từ mức thấp đến mức cao ❖ Sử dụng liên kết(Lưu trữ liên kết) ▪ Quản lý cây thông qua nút gốc (root) ▪ Mỗi nút cấp phát động, bao gồm dữ liệu và hai liên kết pLeft, pRight, liên kết tới cây con trái và cây con phải ▪ Nút lá có hai liên kết trái phải đều rỗng
Lưu trữ kế tiếp cây nhị phân ❖ Con của nút thứ i là nút thứ 2i+ 1và 2i+2 ❖ Cha của nút thứ j là nút [(j-1)/2] R 0 1 2 A B 3 4 5 6 C D I E R A B C D I E V[0] V[1] V[2] V[3] V[4] V[5] V[6]
Sử dụng Liên kết Root R A B C D E G G
Sử dụng Liên kết ❖Cấu tạo của nút ▪ Tạo lập bằng cách cấp phát bộ nhớ động ▪ Mỗi nút gồm có các thông tin: • Dữ liệu (data) • 2 liên kết pLeft, pRight liên kết đến nút con trái và nút con phải
Cấu trúc của nút Class Node { int Data; Node pLeft; // liên kết đến nút con trái Node pRight; // liên kết đến nút con phải }; Node root = NULL; //gốc của cây Data pLeft Data pRight pLeft pRight
Phép duyệt cây nhị phân ❖Định nghĩa ▪ là phép xử lý các nút trên cây, mỗi nút một lần ❖Duyệt cây theo thứ tự trước (preorder) ❖Duyệt cây theo thứ tự giữa (inorder) ❖Duyệt cây theo thứ tự sau (postorder)
Duyệt cây theo thứ tự trước ❖ Duyệt cây theo thứ tự trước (NLR)- Đệ qui ▪ Thăm gốc ▪ Duyệt cây con trái theo thứ tự trước ▪ Duyệt cây con phải theo thứ tự trước R A B R A C F D G J B E H I C D E F G H I J
Duyệt theo thứ tự trước void preorder(Node root) { if (root != NULL) { - In ra : root.data; preorder(root.pLeft); predorder(root.pRight); } }
Duyệt cây theo thứ tự giữa ❖ Duyệt cây theo thứ tự giữa (LNR) ▪ Duyệt cây con trái theo thứ tự giữa ▪ Thăm gốc ▪ Duyệt cây con phải theo thứ tự giữa R F C A G J D R B H E I A B C D E F G H I J
Duyệt cây theo thứ tự giữa void inorder(Node root) { if (root != NULL) { inorder(root.pLeft); In ra: root.data; indorder(root.pRight); } }
Duyệt cây theo thứ tự sau ❖ Duyệt cây theo thứ tự sau (LRN) ▪ Duyệt cây con trái theo thứ tự sau ▪ Duyệt cây con phải theo thứ tự sau ▪ Thăm gốc R A B C D E F G H II J F C J G D A H I E B R
Duyệt cây theo thứ tự sau void postorder(Node root) { if (root !=null) { postorder(root.pleft); postdorder(root.pright); In ra: root.data; } }
Cây nhị phân tìm kiếm ❖Định nghĩa: (Binary Search Tree – BST) 44 18 88 13 37 59 108 15 23 40 55 71
Cây nhị phân tìm kiếm ❖Khai báo cây Class BSTNode { int Data; BSTNode pLeft; //con trỏ đến nút con trái BSTNode pRight; //con trỏ đến nút con phải }; BSTNode root = NULL; //gốc của cây
Cây nhị phân tìm kiếm ❖Các thao tác trên cây BST ▪ Tìm nút có khóa x ▪ Xóa một nút có khóa là x ▪ Tìm nút có khóa nhỏ nhất ▪ Tìm nút có khóa lớn nhất ▪ Giải phóng cây
Cây nhị phân tìm kiếm ❖int Insert( int X, BSTNode root); ❖int Delete( int X, BSTNode root); ❖BST_Node Find( int X, BSTNode root); ❖BST_Node FindMin( BSTNode root); ❖BST_Node FindMax(BSTNode root); ❖void MakeEmpty( BSTNode root);
Thêm một phần tử vào cây nhị phân tìm kiếm root ❖ Thêm vào phần tử có khóa x 44 X > 44 Thêm X= 50 18 X < 88 88 13 37 59 108 X < 59 15 23 40 55 71 X < 55 50
Thêm một phần tử vào cây nhị phân tìm kiếm int Insert(int X, BST_Node root) { if (root == NULL) { root =new BSTreeNode ; if ( root == NULL ) return -1; // Không thể cấp phát bộ nhớ else { root.Data = X; root.pLeft = root.pRight = NULL; return 1; // Thêm vào thành công } }
Thêm một phần tử vào cây nhị phân tìm kiếm else if (root.Data ==X) return 0 ; // Đã tồn tại trong cây else if ( X< root.Data ) return Insert( X, root.pLeft ); else return Insert( X, root.pRight ); }
Tìm một nút có khóa X ❖Tìm nút có khóa X root 44 X >44 Tìm X=55 18 88 X < 88 13 37 59 108 X < 59 15 23 40 55 71
Tìm một nút có khóa X BSTNode Find( int X, BSTNode root) { if( root == NULL ) return NULL; if ( X root.data) return Find( X, root.pRight ); else return root; }
Tìm một nút có khóa X ❖ Tìm nút có khóa X, không dùng đệ qui BTSNode Find2(int X, BTSNode root) { BTSNode p = root; while (p != NULL) { if(X == p.data) return p; else if(x < p.data) p = p.pLeft; else p = p.pRight; } return NULL; }
Tìm nút có khóa nhỏ nhất BSTNode FindMin( BSTNode root) { if ( root == NULL ) return NULL; else if( root.pLeft == NULL ) return root; else return FindMin( root.pLeft ); }
Tìm nút có khóa lớn nhất BST_Node FindMax(BSTNode root) { if (root != NULL ) while (root.pRight != NULL ) root = root.pRight; return root; }
Xóa một nút có khóa X trên cây BST ❖Xóa một nút có khóa X trên cây BST, có ba trường hợp: ▪ Nút có khóa X là nút lá. ▪ Nút có khóa X chỉ có 1 con (trái hoặc phải). ▪ Nút có khóa X có đủ cả 2 con
Xóa một nút có khóa X Trường hợp 1 :Nút có khóa X trên cây BST là nút lá: root Xóa: X=40 44 18 88 Đơn giản : Xóa nút X, vì nó không móc nối 13 37 59 108 đến nút nào khác 15 23 40 55 71
Xóa một nút có khóa X trên cây BST ❖ Trường hợp 2 : Nút X có một cây con trái hoặc phải root 44 root Xóa X=37 44 Xóa X=37 18 88 18 88 13 37 59 108 13 37 59 108 15 23 55 71 15 40 55 71
Xóa một nút có khóa X trên cây BST ❖ Trường hợp 3 : Nút X có một cây hai con trái và phải Xóa nút X=18 44 root ▪ Hủy gián tiếp 18 88 15 13 37 59 108 15 23 40 55 71 30
Cây nhị phân tìm kiếm (Binary Search Tree – BST) int Delete( int X, BSTNode root) { BSTNode p; if ( root == NULL ) return 0 ; // cây rỗng, không tim thấy else if ( X root.Data ) // xóa trên cây con phải retrurn Delete( X, root.pRight ); else // tìm ra nút cần xóa
Cây nhị phân tìm kiếm (Binary Search Tree – BST) if ( root.pLeft && root.pRight ) // Có hai con { p = FindMax(root.pLeft); //tìm nút có khóa lớn nhất trên con trái root.Data = p.Data; return Delete(root.Data, root.pLeft); } else // có một con hoặc không có con { p = root; if ( root.pLeft == NULL ) // xử lý như không có con root = root.pRight; else if ( root.pRight == NULL ) root = root.pLeft; p = null; } return 1; }
Giải phóng cây BST void MakeEmpty( BST_Node root); { if (root) { MakeEmpty(root.pLeft); MakeEmpty(root.pRight); delete root ; } }
Cây nhị phân liên kết vòng ❖ Định nghĩa ▪ Sử dụng liên kết NULL để lưu trữ liên kết tới nút kế tiếp trong phép duyệt cây nhị phân -> phép duyệt được thực hiện dễ dàng ▪ Sử dụng giá trị kiểm tra liên kết thật (đến nút trong cây) hay liên kết giả (nút trong phép duyệt) ▪ Ltype = true, nếu liên kết trái là liên kết thật ▪ Rtype = true, nếu liên kết phải là liên kết thật LPTR LTYPE INFO RTYPE RPTR
Cây nhị phân liên kết vòng ❖Cây nhị phân liên kết vòng (NLR) R A B 1 R 1 D E 0 A 1 0 B 1 R A D B E R 0 D 0 0 E 0 A B D E
Cây tổng quát ❖Định nghĩa ▪ Cây m phân là cây mà mỗi nút có tối đa m nút con (cây con) ▪ Biểu diễn cây m phân bằng liên kết động • Mỗi nút có m+1 trường, với m mối nối • Với cây m phân đầy đủ, có n(m-1)+1 mối liên kết NULL
Cây tổng quát ❖Biểu diễn cây tổng quát ▪ Biểu diễn cây tổng quát bằng cây nhị phân ▪ Đối với một nút trên cây tổng quát • Một nút con nằm ở vị trí trái nhất (con cả 1) • Một nút kế cận với nút đang xét kể từ trái sang (em kế - 2)
Cây tổng quát ❖Biểu diễn cây tổng quát Data R R FirstChild NextSibling A D B A C H I J G E C D H I B class TreeNode {int info; TreeNode FirstChild; // con cả J G TreeNode NextSibling; //em kê }; E
Cây tổng quát ❖Phép duyệt cây tổng quát NLR(T) ▪ Nếu T rỗng, dừng ▪ Ngược lại, T1, ,Tn là cây con gốc T • Thăm gốc của T • NLR(T1), T1 cây con thứ nhất của gốc T • Duyệt cây con T2, ,Tn của T theo thứ tự trước
Cây tổng quát ❖Phép duyệt cây tổng quát LNR(T) ▪ Nếu T rỗng, dừng ▪ Ngược lại, T1, ,Tn là cây con gốc T • LNR(T1), T1 cây con thứ nhất của gốc T • Thăm gốc của T • Duyệt cây con T2, ,Tn của T theo thứ tự giữa
Cây tổng quát ❖Phép duyệt cây tổng quát LRN(T) ▪ Nếu T rỗng, dừng ▪ Ngược lại, T1, ,Tn là cây con gốc T • LNR(T1), T1 cây con thứ nhất của gốc T • Duyệt cây con T2, ,Tn của T theo thứ tự giữa • Thăm gốc của T
Cây tổng quát ❖Duyệt cây theo mức ▪ Duyệt cây theo chiều rộng ▪ Ý tưởng • Tổ chức thành một hàng đợi • Đưa nút gốc vào hàng đợi • Lặp – Lấy một nút ra khỏi hàng đợi – Duyệt nút T – Đưa các nút con của T (nếu có) vào hàng đợi