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 5 - Đỗ Bích Diệp

Chia sẻ: Nguyên Phương | Ngày: | Loại File: PDF | Số trang:30

Thêm vào BST
Báo xấu
85
lượt xem 7
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 5: Cấu trúc cây" cung cấp cho người học các kiến thức: Các khái niệm, cây tổng quát (ADT cây, biểu diễn cây tổng quát, duyệt cây tổng quát), cây nhị phân (định nghĩa và tính chất, duyệt cây nhị phân, biểu diễn cây nhị phân), ứng dụng của cấu trúc cây cho cây biểu thức. Mời các bạn cùng tham khảo nội dung chi tiết.

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 5 - Đỗ Bích Diệp

  1. Cấu trúc dữ liệu và Giải thuật Cấu trúc dữ liệu và Giải thuật Chương IV: Cấu trúc Cây Cấu trúc Cây z Nội dung 1. Các khái niệm 2. Cây tổng quát 1. ADT Cây 2. Biểu diễn cây tổng quát 3. Duyệt cây tổng quát 3. Cây nhị phân 1. Định nghĩa và tính chất 2. Duyệt cây nhị phân 3. Biểu diễn cây nhị phân 4. Ứng dụng của cấu trúc cây cho cây biểu thức Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 1
  2. Cấu trúc dữ liệu và Giải thuật Định nghĩa Cây − Cây là một cấu trúc phi tuyến, thiết lập trên một tập hữu hạn các “nút” – Tồn tại một nút đặc biệt gọi là “gốc” (root) – Giữa các nút tồn tại một quan hệ phân cấp hay gọi là quan hệ cha con – Một nút trừ nút gốc chỉ có một cha – Một nút có thể có từ 0 đến n con Đỗ Bích Diệp - Khoa CNTT Định nghĩa Cây z Định nghĩa đệ quy về Cây r – Một nút tạo thành một cây. – Nếu có n cây T1, T2, …, r1 r2 rn Tn tách biệt có các nút gốc lần lượt là r1, r2, … , rn; r là một nút có quan hệ cha-con với r1, r2, … , T1 T2 Tn rn thì tồn tại một cây mới T nhận r làm gốc. Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 2
  3. Cấu trúc dữ liệu và Giải thuật Ví dụ Cây Cây thư mục trong máy tính Desktop My Network My My Computer Places Documents WindowsXP CD Driver My Received Floppy(A:) My Pictures My Music (C:) (D:) Files Đỗ Bích Diệp - Khoa CNTT Ví dụ Cây Cây phân cấp chức năng hệ thống thông tin Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 3
  4. Cấu trúc dữ liệu và Giải thuật Ví dụ Cây Cây mục lục Sách Đỗ Bích Diệp - Khoa CNTT Các thuật ngữ liên quan đến cây – Cấp (Degree) của một nút và của cây z Cấp của một nút là số các con của nút đó z Cấp của một cây là cấp cao nhất của một nút trên cây Degree 3 Degree 2 A Degree 4 B C D Degree 1 E F G H I J K Degree 3 P L M N Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 4
  5. Cấu trúc dữ liệu và Giải thuật Các thuật ngữ liên quan đến cây – Đường đi trên cây: z Dãy các nút n1, n2, .., nk trong đó ni là nút cha của ni+1 ( i = 1..k-1) là đường đi từ n1 đến nk Path from A to M A Length = 3 B C D E F G H I J K P L M N Đỗ Bích Diệp - Khoa CNTT Các thuật ngữ liên quan đến cây z Độ sâu hay mức (Depth – Level ) của nút – Độ dài đường đi từ gốc đến nút đó + 1 A Depth 1 B C D Depth 2 E F G H I J K Depth 3 P L M N Depth 4 Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 5
  6. Cấu trúc dữ liệu và Giải thuật Các thuật ngữ liên quan đến cây z Độ cao (Height) của nút – Độ dài đường đi dài nhất từ nút đó đến 1 nút lá trong cây + 1 – Chiều cao của cây là chiều cao của nút gốc của cây đó Height =4 Height =3 A B C D Height = 2 E F G H I J K P L M N Height = 1 Đỗ Bích Diệp - Khoa CNTT Các thuật ngữ liên quan đến cây z Tổ tiên (Ancestor): A,C, G là tổ tiên của M z Hậu duệ (descendants): E, F, G, H, L,M …đều là hậu duệ của A z Anh em (siblings): E, F là một cặp anh em ; L, N là một cặp anh em A B C D E F G H I J K P L M N Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 6
  7. Cấu trúc dữ liệu và Giải thuật Các thuật ngữ liên quan đến cây z Rừng là một tập hợp hữu hạn các cây phân biệt , không giao nhau B C D E F G H I J K L M N Đỗ Bích Diệp - Khoa CNTT Các thao tác cơ bản trên Cây – Các thao tác truy nhập cây z root() : trả ra nút gốc của cây z parent( Tree T, Node p): trả ra nút cha của nút p trong cây T z children(Tree T, Node p): trả ra danh sách các nút con của nút p trong cây T z left_most_child(Tree T, Node p) : trả ra nút con cực trái của nút p z right_most_child(Tree T, Node p) : trả ra nút con cực phải của nút p z left_sibling (Tree T, Node p) : trả ra nút anh em kề cận bên trái của nút p z right_sibling(Tree T, Node p) : trả ra nút anh em kề cận bên phải của nút p – Các thao tác khác z height (Tree T) z size(Tree T) z isRoot (Tree T, Node p); isLeaf (Tree T, Node p); isInternal (Tree T, Node p); Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 7
  8. Cấu trúc dữ liệu và Giải thuật Biểu diễn cây tổng quát – Dựa trên tham chiếu đến nút cha z Cây T có các nút được đánh số từ 1 đến n z Cây T được biểu diễn bằng một danh sách tuyến tính trong đó nút thứ i sẽ chứa một thành phần tham chiếu đến cha của nó z Nếu dùng mảng, A[i] = j nếu j là cha của nút i ; nếu i1là gốc thì A[i] = 0; A 2 3 4 B C D 0 1 1 1 2 3 3 6 6 5 6 7 A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] E G H 8 9 L N Đỗ Bích Diệp - Khoa CNTT Biểu diễn cây tổng quát – Dựa trên danh sách các nút con z 1 nút trong cây có một danh sách các nút con z Danh sách các nút con thường là danh sách móc nối z Trong trường hợp sử dụng danh sách móc nối, các nút đầu danh sách được lưu trong một mảng Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 8
  9. Cấu trúc dữ liệu và Giải thuật Biểu diễn cây tổng quát – Dựa trên danh sách các nút con A[1] 2 3 4 1 A[2] 5 A 2 3 4 B C D A[3] 6 7 5 6 7 A[4] NULL E G H A[5] NULL 8 9 A[6] 8 9 L N A[7] NULL A[8] NULL A[9] NULL Đỗ Bích Diệp - Khoa CNTT Biểu diễn cây tổng quát – Thông qua một cây cấp 2 z Với một nút trong cây , chỉ quan tâm tới 2 quan hệ – Quan hệ 1-1 giữa nút đó và nút con cực trái của nó (con cả) – Quan hệ 1-1 giữa nút đó và nút em kế cận bên phải của nó z Dựa vào nhận định này, người ta biểu diễn được một cây tổng quát dưới dạng một cây nhị phân gọi là cây nhị phân tương đương (equivalent binary tree) z Quy cách của 1 nút trên cây nhị phân tương đương sẽ như sau LCHILD INFO RSIBLING Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 9
  10. Cấu trúc dữ liệu và Giải thuật Biểu diễn cây tổng quát A z Ví dụ: – Cây tổng quát B C D E F G H I K A – Cây nhị phân tương đương B E C F G D H I Đỗ Bích Diệp - Khoa CNTTK Duyệt cây theo thứ tự trước z Duyệt cây là thăm các nút trên cây Algorithm preOrder(v) theo một thứ tự nhất định, mỗi nút thăm 1 lần visit(v) z Khi duyệt theo thứ tự trước, một nút for each child w of v sẽ được thăm trước các hậu duệ preOrder(w) của nó z Ứng dụng: In ra các mục lục của một tài liệu 1 I. A 2 5 9 1. B 2. C 3.D 6 7 8 3 4 1.1 E 1.2 F 2.1 G 2.2 H 2.3 I Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 10
  11. Cấu trúc dữ liệu và Giải thuật Duyệt cây theo thứ tự trước z Duyệt cây là thăm các nút trên cây theo một thứ tự nhất định, mỗi nút Algorithm preOrder(v) thăm 1 lần ⇒ visit(v) z Khi duyệt theo thứ tự trước, một nút for each child w of v sẽ được thăm trước các hậu duệ của nó preOrder(w) z Ứng dụng: In ra các mục lục của một tài liệu 1 I. A 1. B 2. C 3. D 1.1 E 1.2 F 2.1 G 2.2 H 2.3 I Đỗ Bích Diệp - Khoa CNTT Duyệt cây theo thứ tự trước z Duyệt cây là thăm các nút trên cây theo một thứ tự nhất định, mỗi nút Algorithm preOrder(v) thăm 1 lần visit(v) z Khi duyệt theo thứ tự trước, một nút for each child w of v sẽ được thăm trước các hậu duệ của nó ⇒ preOrder(w) z Ứng dụng: In ra các mục lục của một tài liệu 1 I. A 1. B 2. C 3. D 1.1 E 1.2 F 2.1 G 2.2 H 2.3 I Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 11
  12. Cấu trúc dữ liệu và Giải thuật Duyệt cây theo thứ tự trước z Duyệt cây là thăm các nút trên cây theo một thứ tự nhất định, mỗi nút Algorithm preOrder(v) thăm 1 lần ⇒ visit(v) z Khi duyệt theo thứ tự trước, một nút for each child w of v sẽ được thăm trước các hậu duệ preOrder(w) của nó z Ứng dụng: In ra các mục lục của một tài liệu 1 I. A 2 1. B 2. C 3. D 1.1 E 1.2 F 2.1 G 2.2 H 2.3 I Đỗ Bích Diệp - Khoa CNTT Duyệt cây theo thứ tự trước z Duyệt cây là thăm các nút trên cây theo một thứ tự nhất định, mỗi nút Algorithm preOrder(v) thăm 1 lần visit(v) z Khi duyệt theo thứ tự trước, một nút for each child w of v sẽ được thăm trước các hậu duệ của nó ⇒ preOrder(w) z Ứng dụng: In ra các mục lục của một tài liệu 1 I. A 2 1. B 2. C 3. D 1.1 E 1.2 F 2.1 G 2.2 H 2.3 I Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 12
  13. Cấu trúc dữ liệu và Giải thuật Duyệt cây theo thứ tự trước z Duyệt cây là thăm các nút trên cây theo một thứ tự nhất định, mỗi nút Algorithm preOrder(v) thăm 1 lần ⇒ visit(v) z Khi duyệt theo thứ tự trước, một nút for each child w of v sẽ được thăm trước các hậu duệ của nó preOrder(w) z Ứng dụng: In ra các mục lục của một tài liệu 1 I. A 2 1. B 2. C 3. D 3 1.1 E 1.2 F 2.1 G 2.2 H 2.3 I Đỗ Bích Diệp - Khoa CNTT Duyệt cây theo thứ tự trước z Duyệt cây là thăm các nút trên cây theo một thứ tự nhất định, mỗi nút Algorithm preOrder(v) thăm 1 lần visit(v) z Khi duyệt theo thứ tự trước, một nút for each child w of v sẽ được thăm trước các hậu duệ của nó preOrder(w) z Ứng dụng: In ra các mục lục của một tài liệu 1 I. A 2 Thăm nút con 1. B 2. C 3. D tiếp theo 3 1.1 E 1.2 F 2.1 G 2.2 H 2.3 I Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 13
  14. Cấu trúc dữ liệu và Giải thuật Duyệt cây theo thứ tự trước z Duyệt cây là thăm các nút trên cây theo một thứ tự nhất định, mỗi nút Algorithm preOrder(v) thăm 1 lần visit(v) z Khi duyệt theo thứ tự trước, một nút for each child w of v sẽ được thăm trước các hậu duệ của nó ⇒ preOrder(w) z Ứng dụng: In ra các mục lục của một tài liệu 1 I. A 2 1. B 2. C 3. D 3 1.1 E 1.2 F 2.1 G 2.2 H 2.3 I Đỗ Bích Diệp - Khoa CNTT Duyệt cây theo thứ tự trước z Duyệt cây là thăm các nút trên cây theo một thứ tự nhất định, mỗi nút Algorithm preOrder(v) thăm 1 lần Khi duyệt theo thứ tự trước, một nút ⇒ visit(v) z for each child w of v sẽ được thăm trước các hậu duệ của nó preOrder(w) z Ứng dụng: In ra các mục lục của một tài liệu 1 I. A 2 1. B 2. C 3. D 3 4 1.1 E 1.2 F 2.1 G 2.2 H 2.3 I Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 14
  15. Cấu trúc dữ liệu và Giải thuật Duyệt cây theo thứ tự trước z Duyệt cây là thăm các nút trên cây theo một thứ tự nhất định, mỗi nút Algorithm preOrder(v) thăm 1 lần visit(v) z Khi duyệt theo thứ tự trước, một nút for each child w of v sẽ được thăm trước các hậu duệ của nó preOrder(w) z Ứng dụng: In ra các mục lục của một tài liệu Không còn con 1 I. A Quay lại nút gốc 2 1. B 2. C 3. D 3 4 1.1 E 1.2 F 2.1 G 2.2 H 2.3 I Đỗ Bích Diệp - Khoa CNTT Duyệt cây theo thứ tự trước z Duyệt cây là thăm các nút trên cây theo một thứ tự nhất định, mỗi nút Algorithm preOrder(v) thăm 1 lần visit(v) z Khi duyệt theo thứ tự trước, một nút for each child w of v sẽ được thăm trước các hậu duệ của nó preOrder(w) z Ứng dụng: In ra các mục lục của một tài liệu Thăm nút con 1 I. A tiếp theo của gốc 2 1. B 2. C 3. D 3 4 1.1 E 1.2 F 2.1 G 2.2 H 2.3 I Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 15
  16. Cấu trúc dữ liệu và Giải thuật Duyệt cây theo thứ tự trước z Duyệt cây là thăm các nút trên cây theo một thứ tự nhất định, mỗi nút Algorithm preOrder(v) thăm 1 lần visit(v) z Khi duyệt theo thứ tự trước, một nút for each child w of v sẽ được thăm trước các hậu duệ của nó ⇒ preOrder(w) z Ứng dụng: In ra các mục lục của một tài liệu 1 I. A 2 1. B 2. C 3. D 3 4 1.1 E 1.2 F 2.1 G 2.2 H 2.3 I Đỗ Bích Diệp - Khoa CNTT Duyệt cây theo thứ tự trước z Duyệt cây là thăm các nút trên cây theo một thứ tự nhất định, mỗi nút Algorithm preOrder(v) thăm 1 lần ⇒ visit(v) z Khi duyệt theo thứ tự trước, một nút for each child w of v sẽ được thăm trước các hậu duệ của nó preOrder(w) z Ứng dụng: In ra các mục lục của một tài liệu 1 Và tiếp tục như vậy …. I. A 2 1. B 5 2. C 3. D 3 4 1.1 E 1.2 F 2.1 G 2.2 H 2.3 I Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 16
  17. Cấu trúc dữ liệu và Giải thuật Duyệt cây theo thứ tự sau z Duyệt theo thứ tự sau thì một nút Algorithm postOrder(v) sẽ được thăm sau các hậu duệ for each child w of v của nó postOrder(w) z Ứng dụng: Xác định kích thước của các tệp trong một thư mục và visit(v) các thư mục con của 9 cs16/ 8 3 7 todo.txt homeworks/ programs/ 1K 1 2 4 5 6 h1c.doc h1nc.doc DDR.java Stocks.java Robot.java 3K 2K 10K 25K 20K Đỗ Bích Diệp - Khoa CNTT Duyệt cây theo thứ tự giữa z Duyệt theo thứ tự giữa thì một nút Algorithm inOrder(v) sẽ được thăm sau các hậu duệ if (isLeaf(v)) then visit(v) của nó trong cây con cực trái và else trước các hậu duệ trong các cây con tiếp theo inOrder(left_most_child(v)) visit(v) for each child w of v (w is 4 not the left most child) cs16/ inOrder(w) 9 2 6 todo.txt homeworks/ programs/ 1K 1 3 5 7 8 h1c.doc h1nc.doc DDR.java Stocks.java Robot.java 3K 2K 10K 25K 20K Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 17
  18. Cấu trúc dữ liệu và Giải thuật Cây nhị phân ( Binary Tree) – Là cây mà mọi nút trên cây chỉ có tối đa là 2 con. z Cây con của một nút cũng cần phải được phân biệt rõ ràng thành cây con trái (left subtree) và cây con phải (right subtree) A left-subtree right-subtree B C D E F G Đỗ Bích Diệp - Khoa CNTT Ví dụ cây nhị phân – Cây biểu thức số học với các phép toán 2 ngôi + - / x * x z 3 y Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 18
  19. Cấu trúc dữ liệu và Giải thuật Ví dụ cây nhị phân – Cây quyết định Want a fast meal? Yes No How about coffee? On expense account? Yes No Yes No Starbucks Spike’s Al Forno Café Paragon Đỗ Bích Diệp - Khoa CNTT Ví dụ cây nhị phân – Kết quả thi đấu một môn thể thao theo cặp tại nhiều vòng H A H A E H F A D C E B H G F Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 19
  20. Cấu trúc dữ liệu và Giải thuật Các dạng đặc biệt của cây nhị phân z Cây suy biến (degenerate binary tree) – Mỗi nút trong của cây có đúng 1 nút con A A A A C C C C F F F F G G G G (a) (b) (c) (d) Đỗ Bích Diệp - Khoa CNTT Các dạng đặc biệt của cây nhị phân z Cây nhị phân đầy đủ (full A binary tree) – Mỗi nút trong của cây đều B C có đầy đủ 2 con D G E F A z Cây nhị phân gần đầy – Ở mức cuối cùng không B C có đầy đủ các nút D E F G H I J K Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 20
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