Bài giảng Cấu trúc dữ liệu và giải thuật (Data Structures and Algorithms): Chương 4 - GV. Ngô Công Thắng

Bài giảng Cấu trúc dữ liệu và giải thuật (Data Structures and Algorithms) - Chương 4: Cây. Nội dung chính của chương gồm có: Định nghĩa và khái niệm, cây nhị phân, cây tổng quát, ứng dụng. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật (Data Structures and Algorithms): Chương 4 - GV. Ngô Công Thắng Chương 4: Cây (Tree) 1. Định nghĩa và khái niệm 2. Cây nhị phân 3. Cây tổng quát 4. Ứng dụng Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04 4.1 1. Định nghĩa và khái niệm 1.1. Định nghĩa cây (tree) l Cây là một tập hợ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. l Một cây không có nút nào gọi là cây rỗng (null tree). l Các ví dụ về cây Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04 4.2 Ví dụ 1: Mục lục của một chương được biểu diễn dạng cây Chương 6 6.1 6.2 6.2.1 6.2.2 6.3 6.3.1 6.3.2 Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04 4.3 Ví dụ 2: Biểu thức số học được biểu diễn dạng cây x+y*(z-t)+u/v Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04 4.4 Ví dụ 3: Các tập bao nhau được biểu diễn dạng cây l Có các tập bao nhau A, B, C, D, E, F Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04 4.5 1.2. Các khái niệm l Gốc (Root): Gốc là nút đặc biệt không có nút cha. Ví dụ 3: A là gốc. A là cha của B, E, F. B, E, F là con của A. B, E, F cũng là gốc của các cây con của A l Cấp (Degree): Số con của một nút gọi là cấp của nút đó. Ví dụ 3: A có cấp là 3. E, F có cấp là 0. B có cấp là 2. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04 4.6 1.2. Các khái niệm (tiếp) l Lá (Leaf): Nút có cấp bằng không gọi là lá hay nút tận cùng. Ví dụ 3: C,D,E,F là lá. l Nút nhánh (Branch Node): Nút không là lá được gọi là nút nhánh hay nút trong. Ví dụ 3: B là nút nhánh. l Mức (Level): Gốc cây có mức là 1. Nếu nút cha có mức là i thì nút con có mức là i+1. Ví dụ 3: A có mức là 1. B, E, F có mức là 2. C, D có mức là 3. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04 4.7 1.2. Các khái niệm (tiếp) l Chiều cao của cây (Height) hay chiều sâu của cây (Depth): Là số mức lớn nhất của nút có trên cây. Ví dụ 1: Cây có chiều cao là 3 Ví dụ 2: Cây có chiều cao là 5 Ví dụ 3: Cây có chiều cao là 3 l Đường đi (Path): Nếu n1, n2, ..., nk là các dãy nút mà ni là cha của ni+1 (1≤i 1.2. Các khái niệm (tiếp) l Nếu thứ tự các cây con của một nút được coi trọng thì cây đang xét là cây có thứ tự, ngược lại là cây không có thứ tự. l Thường thì thứ tự các cây con của một nút được đặt từ trái sang phải. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04 4.9 1.2. Các khái niệm (tiếp) l Đối với cây, ngoài quan hệ cha con, người ta còn mở rộng phỏng theo quan hệ trong gia tộc. l Rừng (Forest): 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. l Nếu bỏ nút gốc của một cây thì ta sẽ có một rừng. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04 4.10 2. Cây nhị phân 2.1. Định nghĩa và tính chất 2.1.1. Định nghĩa cây nhị phân l Cây nhị phân là dạng đặc biệt của cấu trúc cây, mọi nút trên cây chỉ có tối đa là 2 con. l Đối với cây con của một nút người ta phân biệt cây con trái và cây con phải. Như vậy cây nhị phân là cây có thứ tự. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04 4.11 Ví dụ 1: Hai cây sau đây là khác nhau Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04 4.12 Ví dụ 2: Cây nhị phân suy biến có dạng một danh sách tuyến tính Cây lệch trái Cây lệch phải Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04 4.13 Ví dụ 2: Cây nhị phân suy biến có dạng một danh sách tuyến tính (tiếp) Cây zíc zắc Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04 4.14 2.1.1. Định nghĩa cây nhị phân (tiếp) l Cây nhị phân hoàn chỉnh: Là cây nhị phân mà các nút nhánh ở các mức đều có hai nút con. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04 4.15 2.1.1. Định nghĩa cây nhị phân (tiếp) l Cây nhị phân đầy đủ: Là cây nhị phân mà các nút ở mọi mức của nút nhánh đều có hai con. Cây nhị phân đầy đủ là trường hợp đặc biệt của cây nhị phân hoàn chỉnh. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04 4.16 2.1.2. Tính chất l Số lượng tối đa các nút ở mức i trên 1 cây nhị phân là 2(i-1) (i≥1). l Số lượng tối đa các nút trên 1 cây nhị phân có chiều cao h là 2h – 1. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04 4.17 2.2. Lưu trữ cây nhị phân 2.2.1. Lưu trữ kế tiếp l Với cây nhị phân đầy đủ, ta đánh số các nút từ 1 trở đi, từ trái qua phải, hết mức này đến mức khác. l Dùng vector lưu trữ V có n ô nhớ với chỉ số từ 1 đến n để lưu trữ các nút, nút thứ i của cây được lưu trữ ở ô nhớ V[i]. Ví dụ: Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04 4.18 2.2.1. Lưu trữ kế tiếp (tiếp) l Nếu cây không đầy đủ ta phải thêm các nút trống vào để đươc cây nhị phân đầy đủ, sau đó lưu trữ cây đầy đủ đã tạo ra. l Với cách lưu trữ kế tiếp này, khi biết chỉ số của nút cha sẽ tính được chỉ số của nút con và ngược lại. Nếu nút cha là i thì con trái là 2i và con phải là 2i+1. Nếu nút con là i thì nút cha là [i/2]. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04 4.19 Ví dụ Ngô Công Thắng Bài g ...