Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Cấu trúc dữ liệu: Chương 9 - Nguyễn Xuân Vinh

Bài giảng Cấu trúc dữ liệu - Chương 9: Tree trình bày về khái niệm, thuật ngữ của cấu trúc cây, cây nhị phân và cây nhị phân tìm kiếm. Đây là tài liệu tham khảo hữu ích cho bạn đọc nghiên cứu và tìm hiểu về Cấu trúc dữ liệu. | TREE Nguyễn Xuân Vinh nguyenxuanvinh@hcmuaf.edu.vn CẤU TRÚC DỮ LIỆU DATA STRUCTURES [214331] - 2 Cấu trúc dữ liệu Linear Hierarchical structures 2 Mảng Danh sách Mỗi phần tử có 1 phần tử trước và một phần tử tiếp sau Cấu trúc phân cấp: Mỗi nút có nhiều hơn một nút con, và các nút con cũng vậy - 3 Nội dung Cấu trúc cây Cây nhị phân Cây nhị phân tìm kiếm - 4 Cấu trúc cây Tập hợp các nút và cạnh nối các nút đó Có một nút gọi là gốc Quan hệ one-to-many giữa các nút Có duy nhất một đường đi từ gốc đến một nút Các loại cây: Nhị phân: mỗi nút có {0,1, 2} nút con Tam phân: mỗi nút có {0,1,2,3} nút con n-phân: mỗi nút có {0,1,,n} nút con - 5 Cấu trúc cây - 6 Khái niệm J Z A D R B L F A K Q Lá nút gốc Cạnh - 7 Thuật ngữ Root node: nút gốc: không có nút cha Leaf node: nút lá: không có nút con Internal node: nút trong: không phải nút con và nút gốc Height: chiều cao: khoảng cách từ gốc đến lá Parent node (or ancestor, or superior): nút cha Child nodes (successor): nút con 1 2 3 5 6 7 8 4 Chiều | TREE Nguyễn Xuân Vinh nguyenxuanvinh@hcmuaf.edu.vn CẤU TRÚC DỮ LIỆU DATA STRUCTURES [214331] - 2 Cấu trúc dữ liệu Linear Hierarchical structures 2 Mảng Danh sách Mỗi phần tử có 1 phần tử trước và một phần tử tiếp sau Cấu trúc phân cấp: Mỗi nút có nhiều hơn một nút con, và các nút con cũng vậy - 3 Nội dung Cấu trúc cây Cây nhị phân Cây nhị phân tìm kiếm - 4 Cấu trúc cây Tập hợp các nút và cạnh nối các nút đó Có một nút gọi là gốc Quan hệ one-to-many giữa các nút Có duy nhất một đường đi từ gốc đến một nút Các loại cây: Nhị phân: mỗi nút có {0,1, 2} nút con Tam phân: mỗi nút có {0,1,2,3} nút con n-phân: mỗi nút có {0,1,,n} nút con - 5 Cấu trúc cây - 6 Khái niệm J Z A D R B L F A K Q Lá nút gốc Cạnh - 7 Thuật ngữ Root node: nút gốc: không có nút cha Leaf node: nút lá: không có nút con Internal node: nút trong: không phải nút con và nút gốc Height: chiều cao: khoảng cách từ gốc đến lá Parent node (or ancestor, or superior): nút cha Child nodes (successor): nút con 1 2 3 5 6 7 8 4 Chiều cao Nút gốc Nút trong Nút lá - 8 Thuật ngữ Root Node A Node H Node B Node G Node F Node E Node D Node C Node K Node J Node L Node I Cây con Nút anh em Ví dụ cây Một số loại cây thường gặp: Cây nhị phân. Cây quyết định. Cây biểu thức. Cây đỏ đen. Nội dung Cấu trúc cây Cây nhị phân Cây nhị phân tìm kiếm Cây nhị phân tìm kiếm cân bằng AVL - 11 Cây nhị phân (Binary Tree) Cấu trúc cây đơn giản nhất Tại mỗi nút gồm các 3 thành phần Phần data: chứa giá trị, thông tin Liên kết đến nút con trái (nếu có) Liên kết đến nút con phải (nếu có) Cây nhị phân có thể rỗng (ko có nút nào) Cây NP khác rỗng có 1 nút gốc Có duy nhất 1 đường đi từ gốc đến 1 nút Nút không có nút con bên trái và con bên phải là nút lá - 12 Binary Tree A B C D E F I H G Độ sâu/chiều cao = 3 Kích thước = 9 (số nút) Cây con trái Cây con phải Mức 1 Mức 2 Mức 3 Mức 0 - 13 Binary Tree Cây nhị phân đúng: Nút gốc và nút trung gian có đúng 2 con Cây nhị phân đúng có n nút lá thì số nút trên cây 2n-1 A B C D E F G H I J K - 14 Binary .