Bài giảng giới thiệu khái niệm cấu trúc cây; cấu trúc dữ liệu cây nhị phân tìm kiếm như cách tổ chức, các thuật toán, ứng dụng; giới thiệu cấu trúc dữ liệu cây nhị phân tìm kiếm, . | 12/1/2016 Kỹ thuật lập trình Tuần 13 – Cây (Tree) Giáo viên: Hà Đại Dương duonghd@ 12/1/2016 1 Nội dung • Giới thiệu khái niệm cấu trúc cây. • Cấu trúc dữ liệu cây nhị phân tìm kiếm: tổ chức, các thuật toán, ứng dụng. • Giới thiệu cấu trúc dữ liệu cây nhị phân tìm kiếm 12/1/2016 2 Cấu trúc cây 12/1/2016 3 1 12/1/2016 Định nghĩa • Cây là một tập hợp T các phần tử (gọi là nút của cây) trong đó: – Có 1 nút đặc biệt được gọi là gốc, – Các nút còn lại được chia thành những tập rời nhau T1, T2 , . , Tn theo quan hệ phân cấp trong đó Ti cũng là một cây. – Mỗi nút ở cấp i sẽ quản lý một số nút ở cấp i+1. Quan hệ này người ta còn gọi là quan hệ cha-con. 12/1/2016 4 Một số khái niệm • Bậc của một nút : là số cây con của nút đó • Bậc của một cây : là bậc lớn nhất của các nút trong cây (số cây con tối đa của một nút thuộc cây ). Cây có bậc n thì gọi là cây n-phân. • Nút gốc : là nút không có nút cha. • Nút lá : là nút có bậc bằng 0 . • Nút nhánh : là nút có bậc khác 0 và không phải là gốc . 12/1/2016 5 Một số khái niệm • Mức của một nút : – Mức (gốc (T) ) = 0. – Gọi T1, T2, T3, . , Tn là các cây con của T0 – Mức (T1) = Mức (T2) = . = Mức (Tn) = Mức (T0) + 1. 12/1/2016 6 2 12/1/2016 Một số khái niệm • Độ dài đường đi từ gốc đến nút x : là số nhánh cần đi qua kể từ gốc đến x • Độ dài đường đi tổng của cây : P P T X X T trong đó Px là độ dài đường đi từ gốc đến X. • Độ dài đường đi trung bình : PI = PT/n (n là số nút trên cây T). • Rừng cây: là tập hợp nhiều cây trong đó thứ tự các cây là quan trọng. 12/1/2016 7 Ví dụ gốc J Cạnh nút Z B Q A R K D A F L Lá 12/1/2016 8 Cây nhị phân (Binary tree) 12/1/2016 9 3 12/1/2016 Định nghĩa • Cây nhị phân là cây mà mỗi nút có tối đa 2 cây con • Trong thực tế thường gặp các cấu trúc có dạng cây nhị phân. • Một cây tổng quát có thể biểu diễn thông qua cây nhị phân. 12/1/2016 10 Ví dụ Cây con trái Cây con phải Hình ảnh một cây nhị phân 12/1/2016 11 Một số tính .
