Bài giảng Cấu trúc dữ liệu và giải thuật chương 5: Cấu trúc cây

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Chương 5: CẤU TRÚC CÂY Đặt vấn đề Danh sách liên kết được tổ chức theo kiểu tuần tự có tính chất: Chèn, xoá  tốt Tìm kiếm rất chậm Vì nguyên nhân trên đó người ta đưa ra một cấu trúc dữ liệu mới khắc phục được nhược điểm trên  Đó là cây Định nghĩa cây Là tập hợp N các phần tử gọi là nút (hay đỉnh), trong đó có duy nhất một đỉnh đặc biệt gọi là gốc, một tập hợp các cạnh có hướng A nối các cặp nút với nhau gọi là cung hay nhánh. Mỗi nút trên cây được nối với gốc bằng duy nhất một dãy các căp cung liên tiếp. Các khái niệm Một cung ai =(ni, ni+1) nút trên ni gọi là nút cha, nút dưới ni+1 gọi là nút con Nút gốc (root) là nút (duy nhất) không có nút cha. Mọi nút khác có đúng một cha. Các khái niệm(2) Một đường đi p từ n1 đến nk là một dãy các đỉnh {n1, …, nk} sao cho: ai=(ni, ni+1) є A, với mọi i=1, …, k-1 Độ dài đường đi Lx,y từ x đến y là số cung trên đường đi từ x đến y. Ký hiệu Lx là độ dài đường đi từ gốc đến x. Độ dài đường đi trung bình của cây là: Trung bình tổng các đường đi của tất cả các đỉnh của cây. Các khái niệm(3) Bậc của nút là số cây con của nó. Bậc của cây là bậc lớn nhất của các nút của cây. Cây bậc n gọi là cây n-phân Bậc của nút 2 là 1; nút 1, 5 là 2; nút 3 là 3; các nút còn lại có bậc là 0 Cây trên là cây tam phân Các khái niệm(4) Nút trong là nút có bậc lớn hơn 0. Nút lá có bậc bằng 0. Mỗi nút trong cùng với các nút con của nó tạo thành cây con. Nút trong là các nút: 1, 2, 3 và 5. Nút lá là các nút: 4, 8, 9, 6 và 7. Các khái niệm(5) Mức của một nút là số đỉnh trên đường đi từ gốc đến nút đó. Mức của nút gốc bằng 1. Mức(gốc)=1; Mức(con)=Mức(cha)+1 Chiều cao của một cây là mức lớn nhất của các nút lá Một số ứng dụng của cây Có nhiều ứng dụng để biểu diễn dữ liệu thực tế Ví dụ: Biểu thức số học 1+3 *4 biểu diễn dưới dạng cây V.V.. Một số loại cây thông dụng Cây nhị phân Cây nhị phân tìm kiếm (BST)