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 – Bài 17: Cấu trúc dữ liệu dạng cây

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

Thêm vào BST
Báo xấu
78
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 – Bài 17: Cấu trúc dữ liệu dạng cây" trình bày kiến thức về khái niệm về cây, các phương pháp duyệt cây. Mời các bạn cùng tham khảo bài giảng để nắm chi tiết kiến thức, hỗ trợ cho quá trình học tập và nghiên cứu.

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 – Bài 17: Cấu trúc dữ liệu dạng cây

  1. Cấu trúc dữ liệu và giải thuật Bài 17. Cấu trúc dữ liệu dạng cây Giảng viên: TS. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com 1 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  2. Lecture 17. Trees (1/2) Nội dung bài học: 17.1. Khái niệm về cây. 17.2. Các phương pháp duyệt cây. Tham khảo: 1. Deshpande Kakde: C and Data structures.chm, Chapter 21: Trees 2. Elliz Horowitz – Fundamentals of Data Structures.chm, Chapter 5: Trees. 3. Kyle Loudon: Mastering Algorithms with C.chm, Chapter 9. Trees. 4. Bài giảng TS Nguyễn Nam Hồng 2 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  3. 17.1. Khái niệm về cây (1/) 17.1.1. Giới thiệu.  Trees được dùng cho cấu trúc dữ liệu dạng phân cấp.  Ví dụ:  Việc phân cấp cấu trúc dữ liệu được dùng cho minh họa lược đồ công việc.  Tổ chức của một đơn vị.  Cây biểu thức. Khoa Công nghệ thông tin BM KHMT BM HTTT BM ANM BM CNPM BM Toán TTMT Phòng TN Giáo viên 1 Giáo viên 2 Ví dụ về cây: Tổ chức Khoa CNTT 3 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  4. 17.1. Khái niệm về cây (2/) 17.1.2. Định nghĩa về tree. Cây được định nghĩa đệ quy như sau: Một cây được định nghĩa bởi một tập các node T có dạng:  Có một node đặc biệt gọi là root.  Các node còn lại được phân chia rời nhau thành n tập dạng T1, T2,…,Tn, trong đó Ti cũng là một cây. 4 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  5. 17.1. Khái niệm về cây (3/) A B C D G H I E F  Hình trên minh họa 1 cây.  Tập hợp các node {A, B, C, D, G, H, I, E, F}.  A là root.  Các node còn lại được chia thành các tập {B, G, H, I}, {C, E, F} và {D}. Mỗi tập trên lại tạo thành 1 cây. 5 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  6. 17.1. Khái niệm về cây (4/) A B C D G H I E F  Minh họa trên không phải là một cây.  Mặc dù:  Tập hợp các node vẫn là {A, B, C, D, G, H, I, E, F}.  A là root.  Node E thuộc 2 tập hợp. 6 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  7. 17.1. Khái niệm về cây (5/) • Bậc của một node: là số node con của node đó. • Bậc của một cây: là bậc lớn nhất của các node trên cây. • Node gốc: là node không có node cha. • Node lá: là node có bậc bằng 0. • Node nhánh: là node có bậc khác 0 và không phải là node gốc. • Mức của một node:  Gọi mức của node root là 1 (cây T0).  Gọi T1, T2, T3, ... , Tn là các cây con của T0  Mức của T1 = Mức của T2 = ... = Mức của Tn = Mức của T0 + 1=2 • Chiều cao của cây hay độ sâu của cây: là mức cao lớn nhất của node trên cây. 7 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  8. 17.1. Khái niệm về cây (6/)  Gốc.  Cạnh (cung). Gốc (root)  Node. node Cạnh (edge, arc)  Lá. A B C D G H I E F Lá (leaf) 8 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  9. 17.1. Khái niệm về cây (7/) Một số ví dụ sử dụng cây:  Cây phả hệ.  Cây quyết định.  Sử dụng cây để tạo queue có độ ưu tiên.  Tổ chức truy cập dữ liệu nhanh, ví dụ như B-tree. 9 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  10. 17.1. Khái niệm về cây (8/) Xây dựng cây:  Có thể xây dựng cây như danh sách liên kết, tuy nhiên mỗi thành phần có nhiều con trỏ (nhiều con). • Mỗi node chứa thông tin về node. • Sử dụng mảng để lưu các con. Ví dụ về khai báo cây: struct node { TreeEntry data; struct node *children[max]; }; 10 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  11. 17.2. Các phương pháp duyệt cây (1/2)  Việc thăm tất cả các node trên cây 1 lần được gọi là duyệt cây.  Với một cây có n node, như vậy có n! cách duyệt cây khác nhau. Tuy nhiên, đa số các phép duyệt cây đó không hữu ích.  Đối với cây tổng quát, có 2 cách duyệt cây thông thường:  Phương pháp duyệt cây theo chiều rộng (Breadth-first traversal)  Phương pháp duyệt cây theo chiều sâu (Depth-first traversal).  Với một cây có n node, độ phức tạp sẽ là O(n). 11 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  12. 17.2. Các phương pháp duyệt cây (2/2) Một số thao tác khi duyệt cây:  Xem tất cả các node trên cây.  Tìm phần tử lớn nhất hay nhỏ nhất trên cây.  Xác định số node có trên cây.  Sao chép cây.  ... 12 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  13. 17.2.1. Duyệt cây theo chiều sâu (1/7)  Các thao tác chính khi duyệt cây:  N: Duyệt node đang xét.  L: Duyệt cây con bên trái của node đang xét.  R: Duyệt các cây con còn lại của node đang xét.  Với các thao trên, có 3 cách cơ bản:  Duyệt tiền thứ tự (Preorder): NLR  Duyệt trung thứ tự (Inorder): LNR  Duyệt hậu thứ tự (Postorder): LRN 13 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  14. 17.2.1. Duyệt cây theo chiều sâu (2/7) Duyệt tiền thứ tự (Preorder): NLR 1. Thăm node đang xét trước các node con của nó. 2. Các node con được thăm theo thứ tự từ trái qua phải. 3. Với mỗi node con, việc thăm được thực hiện theo dạng tiền thứ tự. 14 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  15. 17.2.1. Duyệt cây theo chiều sâu (3/7) Duyệt tiền thứ tự (Preorder): NLR Preorder(node) 1. Thăm node. 2. Với mỗi con k của node: Preorder(k) 1 A 2 B 6 C 9 D 3 4 5 7 8 G H I E F Thứ tự đã duyệt: A B G H I C E F D 15 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  16. 17.2.1. Duyệt cây theo chiều sâu (4/7) Duyệt trung thứ tự (Inorder): LNR 1. Thăm con thứ nhất của node đang xét dạng trung thứ tự. 2. Thăm node đang xét. 3. Thăm các con còn lại của node đang xét dạng trung thứ tự. 16 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  17. 17.2.1. Duyệt cây theo chiều sâu (5/7) Duyệt trung thứ tự (Inorder): LNR Inorder(node) 1. Inorder(FirstChildren). 2. Thăm node. 3. Với mỗi con còn lại k của node: Inorder(k) 5 A 2 B 7 C 9 D 1 3 4 6 8 G H I E F Thứ tự đã duyệt: G B H I A E C F D 17 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  18. 17.2.1. Duyệt cây theo chiều sâu (6/7) Duyệt hậu thứ tự (Postorder): LRN 1. Thăm con thứ nhất của node đang xét dạng hậu thứ tự. 2. Thăm các con còn lại của node đang xét dạng hậu thứ tự. 3. Thăm node đang xét. 18 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  19. 17.2.1. Duyệt cây theo chiều sâu (7/7) Duyệt hậu thứ tự (Postorder): LRN Postorder(node) 1. Postorder(FirstChildren). 2. Với mỗi con còn lại k của node: Postorder(k) 3. Thăm node. 9 A 4 B 7 C 8 D 1 2 3 5 6 G H I E F Thứ tự đã duyệt: G H I B E F C D A 19 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  20. 17.2.2. Duyệt cây theo chiều rộng (1/2)  Thăm các node bắt đầu từ mức thấp nhất cho đến các mức cao.  Tại mỗi mức, thăm từ trái sang phải.  Sử dụng queue hỗ trợ trong quá trình duyệt cây.  Phương pháp này còn được gọi là Level-Order Traversal. 20 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
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