Giáo trình Cấu trúc dữ liệu và giải thuật: Phần 2 - ĐH Sư phạm kỹ thuật Nam Định

Tiếp nội dung phần 1, Giáo trình Cấu trúc dữ liệu và giải thuật: Phần 2 cung cấp cho người học những kiến thức như: Định nghĩa và khái niệm Cây; Một số phương pháp sắp xếp; Phân tích đánh giá các thuật toán; Bài toán tìm kiếm; Tìm kiếm tuần tự. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Giáo trình Cấu trúc dữ liệu và giải thuật: Phần 2 - ĐH Sư phạm kỹ thuật Nam Định CHƢƠNG 6 : CÂY 6.1. ĐỊNH NGHĨA VÀ KHÁI NIỆM a. Định nghĩa Một cây là một tập hữu hạn các nút 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 con . Có thể định nghĩa cây là một cách đệ quy như sau : 1. Một nút là một cây. Nút đó cũng là gốc của cây ấy 5. Nút n là một nút và T1 , T2 , .., Tk là các cây với n1, n2, .., nk lần lượt là các gốc, thì một cây mới T sẽ được tạo lập bằng cách cho nút n trở thành cha của nút n1 , n2 , .., nk; nghĩa là trên gốc lúc đó n1 , n2, .., nk là con của nút n. Để tiện , người ta cho phép tồn tại một cây không có nút nào, mà ta gọi là cây rỗng (null tree) Ví dụ: Mục lục của một cuốn sách của một chương trong sách có cấu trúc của một cây. Chẳng hạn, mục lục của chương 6 này: Chương 6 : Cây 6.1 Định nghĩa và các khái niệm 6.2 Cây nhị phân 6.2.1 Định nghĩa và tính chất 6.2.2 Biểu diễn cây nhị phân 6.2.3 Phép duyệt cây nhị phân 6.2.4 Cây nhị phân nối vòng 6.3 Cây tổng quát 6.3.1 Biểu diễn cây tổng quát 6.3.2 Phép duyệt cây tổng quát 6.4 áp dụng 6.4.1 Cây biểu diễn biểu thức 6.4.2 Cây biểu diễn các tập 6.4.3 Các quyết định Ta có thể biểu diễn bởi một cây có dạng như sau : 6 6.1 6.2 6.3 6.4 6.2.1 6.2.2 6.2.3 6.2.4 6.3.1 6.3.2 6.4.1 6.4.2 6.4.3 Hình 6.1 * Biểu thức số học x + y * (z- t ) + u/v có thể biểu diễn dưới dạng cây như hình 6.2 + * Các tập bao nhau có thể biểu diễn như hình 6.4 + / Đối với cây, chẳng hạn xét cây ở hình 6.1 x * u v Nút A được gọi là gốc của cây y - B, C, D là gốc của cây con của A z t A là cha của B, C, D; Hình 6.2 B, C, D là con của A b. Các khái niệm * Số các con của nút gọi là cấp (degree) của nút đó. Ví dụ cấp của A là 3, cấp của H là 2 a b d f g e i c Hình 6.3 * Nút có cấp bằng không gọi là lá (deaf) hay nút tận cùng (dermimal noder ). Ví dụ nút E, C, K, L v v … Nút không là lá được gọi là nút nhánh ( branch node) Cấp cao nhất của nút trên cây gọi là cấp của cây đó. Cây ở hình 6.4 là cây cấp 3 A B C D E F G H I M K Hình 6.4 * Gốc của cây có số mức (level ) là 1. Nếu nút cha có số mức là i thì nút con có số mức là i + 1. Ví dụ: nút A có số mức là 1 D có số mức là 2 G có số mức là 3 J có số mức là 4 * Chiều cao (height) hay chiều sâu (depth) của một cây là số mức lớn nhất của nút có trên cây đó. Cây chiều hình 6.2 có chiều cao là 5 Cây chiều hình 6.4 có chiều cao là 4 Nếu n1 , n2, ….nk là dãy các nút mà ni là cha của ni + 1 với 1  i < k, thì dãy đó gọi là đường đi (path) từ n1 tới nk . Độ dài của đường đi (path length) bằng các nút trên đường đi trừ đi 1 . Ví dụ trên cây hình 6.4 độ dài đường đi từ A tới G là 2, từ A tới K là 3 * Nếu thứ tự các cây con của một nút được trọng thì cây đang xét là cây có thứ tự (ordered tree), ngược lại là cây không có thứ tự (unordered tree). Thường thứ tự các cây con của một nút được đặt từ trái sang phải Hình 6.5 cho ta hai cây có thứ tự khác nhau: A A B C C B Hình 6.5 Đối với cây, từ quan hệ cha con người ta có thể mở rộng thêm các quan hệ khác phỏng theo các quan hệ như trong gia tộc. * Nếu có một tập hữu hạn các cây phân biệt thì ta gọi tập đó là rừng (forest) Khái niệm về rừng ở đây phải hiểu theo cách riêng vì : có một cây, nếu ta bỏ nút gốc đi ta sẽ có một rừng! Như ở hình 6.4 nếu bỏ nút gốc A đi, ta sẽ có một rừng gồm 3 cây 6.2. CÂY NHỊ PHÂN 6.2.1. Định nghĩa và tính chất a. Định nghĩa Cây nhị phân là một dạng quan trọng của cấu trúc cây. Nó có đặc điểm là : mọi nút trên cây chỉ có tối đa là hai con. Đối với cây con của một nút người ta cũng phân biệt cây con trái (left subtree) và cây con phải (right subtree). Như vậy cây nhị phân là cây có thứ tự Ví dụ : cây ở hình 6.2 là cây nhị phân. Các cây nhị phân sau đây là khác nhau. Nhưng nếu coi là cây thì chúng chỉ là một ( hình 6.6) A A A A B B B B C Đ C D C E C D E ...