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

Bài giảng Cấu trúc dữ liệu & thuật toán - Chương 4: Cây trình bày với người học định nghĩa và các khái niệm cơ bản về cây, cây nhị phân và các ứng dụng. Hy vọng đây là tài liệu tham khảo hữu ích cho bạn. | Chương 4 CÂY Nội dung . Định nghĩa và các khái niệm . Cây nhị phân . Các ứng dụng CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYÊN ĐƯC NgHĩA - Bộ môn KHMT 1 28 2013 2 . Định nghĩa và khái niệm . Định nghĩa . Các thuật ngữ . Cây có thứ tự . Cây có nhãn . ADT cây 1 28 2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYÊN ĐƯC NgHĩA - Bộ môn KHMT 3 . Định nghĩa cây Cây bao gồm các nút có một nút đặc biệt được gọi là gốc root và các cạnh nối các nút. Cây được định nghĩa đệ qui như sau Định nghĩa cây Basic Step Một nút r là cây và r được gọi là gốc của cây này. Recursive Step Giả sử T1 T2 . Tk là các cây với gốc là rvr2 . rk. Ta có thể xây dựng cây mới bằng cách đặt r làm cha parent của các nút rvr2 . rk. Trong cây này r là gốc và T1 T2 . Tk là các cây con của gốc r Các nút r1f r2 . . . rk được gọi là con children của nút r. Chú ý Nhiều khi để phù hợp ta cần định nghĩa cây rỗng null tree là cây không có nút nào cả. CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYÊN ĐƯC NgHĩA - Bộ môn KHMT 4 1 28 2013 Cấu trúc đệ qui của cây 1 28 2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYÊN ĐƯC NgHĩA - Bộ môn KHMT 5 Cây trong thực tế ứng dụng Biểu đồ lịch thi đấu Cây gia phả Biểu đồ phân cấp quản lý hành chính. Cây thư mục Cấu trúc của một quyển sách Cây biểu thức Cây phân hoạch tập hợp CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYÊN ĐƯC NgHĩA - Bộ môn KHMT 1 28 2013