Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 - ThS. Nguyễn Thị Khiêm Hòa (ĐH Ngân hàng TP.HCM)

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 Cây nhằm trình bày về định nghĩa và các khái niệm Cây nhị phân, Cây nhị phân tìm kiếm và cây tổng quát từ đó giúp sinh viên hiểu rõ khái niệm và ứng dụng trên Cây Cài đặt các thuật toán trên cây, đặc biệt là cây nhị phân tìm kiếm.

Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 - ThS. Nguyễn Thị Khiêm Hòa (ĐH Ngân hàng TP.HCM) Chương 4: Cây Giảng viên: Ths. Nguyễn Thị Khiêm Hòa Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM Nội dung  Định nghĩa và các khái niệm  Cây nhị phân  Cây nhị phân tìm kiếm  Cây tổng quát Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 2 Mục tiêu  Trang bị khái niệm và ứng dụng trên Cây  Cài đặt các thuật toán trên cây, đặc biệt là cây nhị phân tìm kiếm. Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 3 Khái niệm  Cây là tập hữu hạn các nút (Tree node):  Có một nút gốc (root)  Các nút còn lại phân hoạch thành n tập riêng biệt T1, T2, …, Tn, với Ti là một cây  Giữa các nút có quan hệ phân cấp (hierarchical relationship) “cha con”.  Cây không có nút là cây rỗng (null tree). Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 4 Biểu diễn cây  Bằng đồ thị  Bằng giản đồ  Bằng danh sách (các dấu ngoặc lồng nhau)  Bằng phương pháp Identatio Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 5 Biểu diễn cây  Bằng đồ thị A / B C D A B C D E E F G H F G H I I J K J Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 6 Biểu diễn cây  Bằng giản đồ D B A J G H I E C F Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 7 Biểu diễn cây  Bằng danh sách (các dấu ngoặc lồng nhau) (/( A (C (F), D (G ( J ) ) ) ), (B (E ( H, I ) ) ) ) A / A B B C D C D E E F G H F G H I J I J K ( A ( B ( E, F( I, J, K) ), C ( G,H ), D ) ) Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 8 Biểu diễn cây  Bằng phương pháp Indentatio / A C / F A B D G C D E J B F G H I E H J I Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 9 Các thuật ngữ  Bậc của nút và bậc của cây  Nút gốc, Nút lá và nút nhánh  Nút cha (Parent), nút con (children) A B C D E F G H I J K L M Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 10 Các thuật ngữ  Đường đi (path) / A B C D E F G H I J Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 11 Các thuật ngữ  Mức của nút và chiều cao của cây Root 1 2 Chiều cao 3 của cây: 5 4 5 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 12 Các thuật ngữ  Tổ tiên (ancestors) của một nút  Con cháu (Descendant) của một nút:  Các con của cùng một cha gọi là anh em ruột (siblings) / A B C D ...