tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 10: Cây (Tree)

Bài giảng "Cấu trúc dữ liệu và giải thuật trong C++ - Bài 10: Cây (Tree)" cung cấp cho người cấp cho người học các kiến thức: Cấu trúc dữ liệu phi tuyến, cây biểu diễn các tổ chức, cây biểu diễn hệ thống files, cấu trúc của một cuốn sách, . | Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 10: Cây (Tree) Bài 10. Cây - Tree 1 Cây – Cấu trúc dữ liệu phi tuyến (Trees - Non-linear data structures) ĐHGTVT CNTT KTVT CT 2 Một số ví dụ sử dụng cấu trúc dữ liệu cây Data structures trees 3 Cây gia phả Data structures trees 4 Cây biểu diễn các tổ chức ĐHGTVT CNTT Đ-ĐT CK KT Mạng CNPM KHMT VT ĐKH TTBĐ KTVT Data structures trees 5 Cây biểu diễn hệ thống files Cây mô tả sự phân chia hệ thống files Data structures trees 6 Cấu trúc của cuốn sách Cây thể hiện cấu trúc thông tin Data structures trees 7 Cây quyết định Bạn đã có gia đình riêng chưa? rồi chưa Không chấp nhận Bạn có bằng đại học không? có Không Bạn có tốt nghiệp loại giỏi không? Không chấp nhận có không Chấp nhận Không chấp nhận Cây quyết định tuyển nhân viên Data structures trees 8 Cây nhị phân biểu diễn các biểu thức toán học Một cây nhị phân biểu diễn một biểu thức. Cây này biểu diễn biểu thức ((((3+1)*3/((9-5)+2))-((3*(7-4))+6)). Giá trị được kết hợp lại tại nút trong có nhãn “/” là 2. Data structures trees 9 Cây cú pháp S XY X XA | a | b Y AY | a A a Data structures trees 10 Tổng kết: Cây là cách tổ chức dữ liệu rất hữu dụng trong rất nhiều ứng dụng khác nhau ĐHGTVT CNTT KTVT CT Data structures trees 11 Cây tổng quát Cây là gì? Cây là một tập các nút với quan hệ cha-con (parent-child) giữa các nút. Trong đó có một nút được gọi là gốc và nó không có cha. Trong khoa học máy tính, một cây là một mô hình trừu tượng của cấu trúc phân cấp. Các ứng dụng: Tổ chức biểu đồ Hệ thống file Các môi trường lập trình Data structures trees 12 Một số khái niệm Gốc (root): là nút không có Cây con: Cây bao nút cha ( vd: A) gồm một số nút của Nút trong: Nút có ít nhất một cây ban đầu một nút con (Vd: A, B, C, F) Nút ngoài (lá): nút không A có nút con (Vd: E, I, J, K, G, H, D) Độ sâu của