CẤU TRÚC DỮ LIỆU - CÂY

Tham khảo tài liệu cấu trúc dữ liệu - cây, công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
CẤU TRÚC DỮ LIỆU - CÂY Chương 3. CÂY Trong chương này chúng ta sẽ nghiên cứu mô hình dữ liệu cây. Cây là mộtcấu trúc phân cấp trên một tập hợp nào đó các đối tượng. Một ví dụ quen thuộc vềcây, đó là cây thư mục.Cây được sử dụng rộng rãi trong rất nhiều vấn đề khácnhau. Chẳng hạn, nó được áp dụng để tổ chức thông tin trong các hệ cơ sở dữ liệu,để mô tả cấu trúc cú pháp của các chương trình nguồn khi xây dựng các chươngtrình dịch. Rất nhiều các bài toán mà ta gặp trong các lĩnh vực khác nhau được quyvề việc thực hiện các phép toán trên cây. Trong chương này chúng ta sẽ trình bàyđịnh nghĩa và các khái niệm cơ bản về cây. Chúng ta cũng sẽ xét các phương phápbiểu diễn cây và sự thực hiện các phép toán cơ bản trên cây. Sau đó chúng ta sẽnghiên cứu kỹ một dạng cây đặc biệt, đó là cây tìm kiếm nhị phân. 3.1. Một số khái niệm 3.1.1. Các định nghĩa - Cây: là một tập hợp hữu hạn các phần tử, mỗi phần tử gọi là một nút(Node), trong đó có một nút đặc biệt gọi là gốc (Root), giữa các nút có một quan hệphân cấp gọi là quan hệ cha conVí dụ cho cây các ký tự g ốc A Mứ c 1 Mứ c 2 B C D Mứ c 3 E F G H I Mức 4 J K A: nút gốc A là nút cha của B, C, D B, C, D là các nút con của A - Cây rỗng: cây không có nút nào cả - Cấp của nút: số nút con của nó, vd nút B có cấp là 2 - Cấp của cây: cấp lớn nhất của các nút có trên cây. Cây có cấp n gọi là câyn phân, ví dụ cây trên là cây tam phân - Lá: nút có cấp là 0, ví dụ các là F, C, G, J - Mức: Nút gốc có mức là 1. Nút cha có mức i thì nút con có mức i+1 - Chiều cao của cây: mức lớn nhất trên cây, ví dụ cây trên có chiều cao 4 - Nút trước, nút sau: Nút x là nút trước của nút y nếu cây con gốc x có chứanút y, khi đó y là nút sau của nút x. ví dụ D là nút trước của nút J - Đường đi (path): Dãy nút u1, u2, . . . uk mà nút bất kỳ ui là cha của nút ui+1thì dãy đó là đường đi từ nút u1 đến nút uk - Độ dài đường đi: số cạnh có trên đường đi, ví dụ dãy DHJ là đường đi từnút D đến nút J với độ dài là 2 - Cây có thứ tự (ordered tree): là cây mà nếu ta thay đổi vị trí của các câycon thì ta có một cây mới. Như vậy nếu ta đổi các nút bên trái và bên phải thì tađược một cây mới, ví dụ sau đây là 2 cây khác nhau: A A B C C B - Rừng: là tập hợp hữu hạn các cây phân biệt 3.1.2. Các cách biểu diễn cây: - Biểu diễn cây bằng đồ thị - Biểu diễn cây bằng giản đồ - Biểu diễn cây bằng các cặp dấu ngoặc lồng nhau - Biểu diễn cây bằng phương pháp căn lề - Biểu diễn cây bằng phương pháp chỉ số 3.2. Cây nhị phân 3.2.1. Định nghĩa và tính chất 3.2.1.1. Định nghĩa Cây nhị phân là một tập hợp hữu hạn các đỉnh được xác định đệ qui như sau: 1.Một tập trống là cây nhị phân. 2.Giả sử T1 và T2 là hai cây nhị phân không cắt nhau (T1 ∩ T2 = φ) và r là mộtđỉnh mới không thuộc T1, T2. Khi đó ta có thể thành lập một cây nhị phân mới Tvới gốc r có T1 là cây con bên trái, T2 là cây con bên phải của gốc. Cây nhị phân Tđược biểu diễn bởi hình 4.9. r T1 T2 Cần lưu ý rằng, cây (cây có gốc) và cây nhị phân là hai khái niệm khác nhau.Cây không bao giờ trống, nó luôn luôn chứa ít nhất một đỉnh, mỗi đỉnh có thểkhông có, có thể có một hay nhiều cây con. Còn cây nhị phân có thể trống, mỗiđỉnh của nó luôn luôn có hai cây con được phân biệt là cây con bên trái và cây conbên phải. Chẳng hạn, hình sau minh họa hai cây nhị phân khác nhau. Cây nhị phântrong hình (a) có cây con trái của gốc gồm một đỉnh, còn cây con phải trống. Câynhị phân trong hình (b) có cây con trái của gốc trống, còn cây con phải gồm mộtđỉnh. (a) (b) Từ định nghĩa cây nhị phân, ta suy ra rằng, mỗi đỉnh của cây nhị phân chỉ cónhiều nhất là hai đỉnh con, một đỉnh con bên trái (đó là gốc của cây con trái) vàmột đỉnh con bên phải (đó là gốc của cây con phải). 1A 2 B 3 C 4 D 5 E 6 F 7 G 8 H 9 I 10 J 11 K 3.2.1.2. Các dạng đặc biệt của cây nhị phân Cây nhị phân suy biến là cây lệch trái hoặc cây lệch phải Cây zic-zắc Cây nhị phân hoàn chỉnh: các nút ứng với các mức trừ mức cuối cùng đều có2 con Cây nhị phân đầy đủ: có các nút tối đa ở cả mọi mức Cây nhị phân đầy đủ là một t ...