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

Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 4 Cây trình bày các nội dung chính như: Ứng dụng của dữ liệu trừu tượng cây, ứng dụng cây gia phả, ứng dụng cây thư mục, cấu trúc dữ liệu trừu tượng cây,. | Chương 4 : Cây Trịnh Anh Phúc, Nguyễn Đức Nghĩa 1 Bộ 1 môn Khoa Học Máy Tính, Viện CNTT & TT, Trường Đại Học Bách Khoa Hà Nội. Ngày 5 tháng 11 năm 2014 Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuật Cấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 11 năm 2014 Ngày 5 tháng 1 / 70 Giới thiệu 1 Định nghĩa và các khái niệm Định nghĩa cây Các thuật ngữ chính Cây có thứ tự Cây có nhãn Cấu trúc dữ liệu trừu tượng cây 2 Cây nhị phân Định nghĩa và tính chất 3 Các ứng dụng của cây Cây nhị phân biểu thức Cây quyết định Mã Huffman Cây gọi đệ qui 4 Tổng kết Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuật Cấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 11 năm 2014 Ngày 5 tháng 2 / 70 Định nghĩa và các khái niệm Định nghĩa cây Cây bao gồm các nút, có một nút đặt biệt được gọi là nút gốc (root ) và các cạnh nối các nút. Cây được định nghĩa đệ qui như sau Bước cơ sở : một nút r được coi là cây và r được gọi là gốc cây. Bước đệ qui : Giả sử T1 , T2 , · · · , Tk là các cây với gốc là r1 , r2 , · · · , rk , ta có thể xây dựng cây mới bằng cách đặt r làm nút cha (parent) của các nút r1 , r2 , · · · , rk . Trong cây mới tạo ra r là gốc và T1 , T2 , · · · , Tk là các cây con của gốc r . Các nút r1 , r2 , · · · , rk được gọi là con của nút r . Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuật Cấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 11 năm 2014 Ngày 5 tháng 3 / 70 Định nghĩa và các khái niệm Định nghĩa cây (tiếp) Hình minh họa định nghĩa đệ qui của cây r r1 r2 . rk T1 T2 . Tk Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuật Cấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 11 năm 2014 Ngày 5 tháng 4 / 70 Định nghĩa và các khái niệm Các ứng dụng của dữ liệu trừu tượng cây Cây trong ứng dụng thực tế Biểu đồ lịch thi đấu Cây gia phả Biều đồ phân cấp quản lý Cây thư mục quản lý file Cây biểu thức Sau đây là một vài hình ảnh minh .