tailieunhanh - 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! | 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 1. Định nghĩa và khái niệm . Đị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 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 Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04 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 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 . 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 . 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 . 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 .