1. Trang Chủ
  2. Cơ sở dữ liệu
  3. Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 4 - Nguyễn Khánh Phương

Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 4 - Nguyễn Khánh Phương

Chương 4 - Cây. Trong chương này, người học có thể hiểu được một số kiến thức cơ bản về: Định nghĩa và các khái niệm, biểu diễn cây, duyệt cây, cây nhị phân. Mời các bạn cùng tham khảo để biết thêm các nội dung chi tiết. TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG om .c ng co Cấu trúc dữ liệu và thuật toán an th o ng Nguyễn Khánh Phương du u Computer Science department cu School of Information and Communication technology E-mail: phuongnk@soict.hust.edu.vn CuuDuongTh

Thể loại Tài liệu miễn phí Cơ sở dữ liệu

Số trang 182

Ngày tạo 10/10/2021 7:19:31 PM +00:00

Loại tệp PDF

Kích thước 5.04 M

Tên tệp

Tải Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 4... (.pdf)

Xem mẫu

  1. TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG om .c ng co Cấu trúc dữ liệu và thuật toán an th o ng Nguyễn Khánh Phương du u Computer Science department cu School of Information and Communication technology E-mail: phuongnk@soict.hust.edu.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
  2. Nội dung khóa học Chương 1. Các khái niệm cơ bản om Chương 2. Các sơ đồ thuật toán .c ng Chương 3. Các cấu trúc dữ liệu cơ bản co Chương 4. Cây an Chương 5. Sắp xếp th o ng du Chương 6. Tìm kiếm u cu Chương 7. Đồ thị 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  3. TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG om .c ng co Chương 4. Cây an th o ng Nguyễn Khánh Phương du u Computer Science department cu School of Information and Communication technology E-mail: phuongnk@soict.hust.edu.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
  4. Nội dung 1. Định nghĩa và các khái niệm om 2. Biểu diễn cây .c 3. Duyệt cây ng co 4. Cây nhị phân an th o ng du u cu Become Rich Force Others Rob Stock to be Poor Banks Fraud 4 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  5. Nội dung 1. Định nghĩa và các khái niệm om 2. Biểu diễn cây .c 3. Duyệt cây ng co 4. Cây nhị phân an th o ng du u cu Become Rich Force Others Rob Stock to be Poor Banks Fraud 5 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  6. 1. Định nghĩa và các khái niệm 1.1. Định nghĩa om 1.2. Các thuật ngữ .c 1.3. Cây có thứ tự (Ordered tree) ng co an th o ng du u cu NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN 6 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  7. 1. Định nghĩa và các khái niệm 1.1. Định nghĩa om 1.2. Các thuật ngữ .c 1.3. Cây có thứ tự (Ordered tree) ng co an th o ng du u cu NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN 7 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  8. 1.1. Định nghĩa Cây gồm một tập các nút, có 1 nút đặc biệt gọi là gốc (root) và các cạnh nối các nút. om Nút gốc .c Dusty ng nút co Honey B ear B randy an th ng B runhilde T erry C oyote Nugget o du Gill T ansey T weed Zoe C rocus Primrose Nous B elle u cu nút NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN 8 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  9. Cây: Định nghĩa đệ quy • Bước cơ sở: – Cây rỗng: cây không có nút nào om – Cây có 1 nút r : nút r được gọi là gốc của cây .c • Bước đệ quy: ng – Giả sử T1,T2,...,Tk là các cây với gốc tương ứng là r1,r2,...,rk co – Ta có thể xây dựng cây mới bằng cách đặt nút r làm cha (parent) của các nút r1,r2,....,rk : an • Trong cây mới này: r là gốc; T1, T2, . . . , Tk là các cây con của gốc r; Các nút th r1,r2,....,rk được gọi là con (children) của nút r. ng r Gốc (Root) o du u cu r1 r2 rk T1 T2 Tk NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN 9 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  10. Các ứng dụng của cây • Lịch thi đấu • Cây gia phả om • Cây thư mục .c ng • Cấu trúc của 1 quyển sách co • Cây biểu thức an • Sơ đồ phân cấp của 1 cơ quan th ng • …. o du u cu NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt
  11. Các ứng dụng của cây: Biểu đồ lịch thi đấu • Trong đời thường, cây thường được sử dụng để mô tả lịch thi đấu của các giải thể thao theo thể thức đầu loại trực tếp om .c ng France France co Spain France an Brazil Brazil th UK ng Italia Germany Germany o du Ukraine Italia Italia Italia u cu Argentina NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt
  12. Các ứng dụng của cây: Cây gia phả • Cây gia phả của các nhà toán học dòng họ Bernoulli om .c Nikolaus 1623-1708 ng co Johan I Nikolaus Jacob I an 1667-1748 1662-1716 1654-1705 th ng Nikolaus II Daniel Johan II Nikolaus I o 1695-1726 1700-1782 1710-1790 1687-1759 du u cu Johan III Jacob II 1746-1807 1759-1789 NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt
  13. Các ứng dụng của cây: Cây thư mục • Cây thư mục om .c ng co an th o ng du u cu NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt
  14. Các ứng dụng của cây: Mục lục 1 quyển sách om .c ng co an th o ng du u cu NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt
  15. Các ứng dụng của cây: Cây gia phả ngược (Ancestor Tree) • Mỗi người đều có bố mẹ: om Ví dụ: Chiến có cha mẹ là: Thanh và Mai .c ng co Chiến an th ng Thanh Mai o du u cu Giang Minh Thành Lan Anh NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt
  16. Các ứng dụng của cây: Cây biểu thức om + .c / / ng co an 1 3 * 4 th o ng 6 7 du u cu 1/3 + 6*7 / 4 NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt
  17. Các ứng dụng của cây: Sơ đồ tổ chức của cơ quan om Công ty máy tính MU .c ng co Bộ phận bán hàng Bộ phận sản xuất Nghiên cứu và phát triên (R&D) an th ng Mỹ Quốc tế Laptops Desktops o du u cu Châu Âu Châu Á Canada NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt
  18. 1. Định nghĩa và các khái niệm 1.1. Định nghĩa om 1.2. Các thuật ngữ .c 1.3. Cây có thứ tự (Ordered tree) ng co an th o ng du u cu NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN 18 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  19. 1.2. Các thuật ngữ • Nút (node) • Gốc (Root) om • Lá (leaf) .c • Con (child) ng co • Cha (Parent) an • Tổ tiên (Ancestors) th • Hậu duệ (Descendants) ng • Anh em (Sibling) o du • Nút trong (Internal node) u • Chiều cao (Height) cu • Chiều sâu (Depth) NGUYỄN KHÁNH PHƯƠNG Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt
  20. 1.2. Các thuật ngữ • Gốc: nút không có cha (ví dụ: nút A) • Anh em: nút có cùng cha (ví dụ: B, C, D là anh em; I, J, K là anh em; E và F là anh em; G và H là anh em) om • Nút trong: nút có ít nhất 1 con (ví dụ: các nút màu xanh dương: A, B, C, F) .c • Nút ngoài (lá ): nút không có con (ví dụ: các nút xanh lá: E, I, J, K, G, H, D) • Tổ tiên của 1 nút: là các nút cha / ông bà / cụ.. của nút đó. ng • Hậu duệ của 1 nút: là các nút con/cháu/chắt… của nút đó co • Cây con của 1 nút: là cây có gốc là con của nút đó an th Ví dụ: A Con của B: E, F ng Cha của E: B o du Tổ tiên của F: B, A B C D Hậu duệ của B: E, F, I, J, K u cu E F G H Cây con của nút A I J K CuuDuongThanCong.com https://fb.com/tailieudientucntt
nguon tai.lieu . vn
Tin học văn phòng Đồ họa - Thiết kế - Flash Quản trị Web Cơ sở dữ liệu Quản trị mạng Kỹ thuật lập trình Hệ điều hành Phần cứng An ninh - Bảo mật Chứng chỉ quốc tế Thủ thuật máy tính Điện - Điện tử Kinh tế học Hoá học Xã hội học Môi trường