tailieunhanh - Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 4 - Trịnh Anh Phúc, Nguyễn Đức Nghĩa

Bài giảng "Cấu trúc dữ liệu và thuật toán - Chương 4: Cây" cung cấp cho người học các kiến thức: Định nghĩa và các khái niệm, cây nhị phân, các ứng dụng của cây, tổng kết. nội dung chi tiết. | Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 4 - Trịnh Anh Phúc, Nguyễn Đức Nghĩa Chương 4 : Cây Trịnh Anh Phúc, Nguyễn Đức Nghĩa 1 1 Bộ 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 1 tháng 12 năm 2013 Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc&dữTT, liệu Trường và giải thuật Đại Học Bách Khoa NgàyHà1 Nội. tháng) 12 năm 2013 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ệnCấu CNTT trúc&dữTT, liệu Trường và giải thuật Đại Học Bách Khoa NgàyHà1 Nội. tháng) 12 năm 2013 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ệnCấu CNTT trúc&dữTT, liệu Trường và giải thuật Đại Học Bách Khoa NgàyHà1 Nội. tháng) 12 năm 2013 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ệnCấu CNTT trúc&dữTT, liệu Trường và giải thuật Đại Học Bách Khoa NgàyHà1 .