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,...
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 4Chương 4 : CâyTrịnh Anh Phúc, Nguyễn Đức Nghĩa1 Bộ1mô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 2014Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuậtCấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 11 năm 2014Ngày 5 tháng1 / 70Giới thiệu1Định nghĩa và các khái niệmĐịnh nghĩa câyCác thuật ngữ chínhCây có thứ tựCây có nhãnCấu trúc dữ liệu trừu tượng cây2Cây nhị phânĐịnh nghĩa và tính chất3Các ứng dụng của câyCây nhị phân biểu thứcCây quyết địnhMã HuffmanCây gọi đệ qui4Tổng kếtTrịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuậtCấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 11 năm 2014Ngày 5 tháng2 / 70Định nghĩa và các khái niệmĐịnh nghĩa câyCâ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ư sauBướ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útcha (parent) của các nút r1 , r2 , · · · , rk . Trong cây mới tạo ra r là gốcvà 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ậtCấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 11 năm 2014Ngày 5 tháng3 / 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âyrr1r2...rkT1T2...TkTrịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuậtCấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 11 năm 2014Ngày 5 tháng4 / 70Định nghĩa và các khái niệmCác ứng dụng của dữ liệu trừu tượng câyCây trong ứng dụng thực tếBiểu đồ lịch thi đấuCây gia phảBiều đồ phân cấp quản lýCây thư mục quản lý fileCây biểu thức....Sau đây là một vài hình ảnh minh họa các ứng dụng nàyTrịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuậtCấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 11 năm 2014Ngày 5 tháng5 / 70