Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 - TS. Nguyễn Thị Kim Thoa

Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 4: Cấu trúc cây, cung cấp cho người học những kiến thức như Định nghĩa cây nhị phân; Biểu diễn máy của cây nhị phân; duyệt cây nhị phân; áp dụng cấu trúc cây;... 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: Chương 4 - TS. Nguyễn Thị Kim Thoa Chương 4: CẤU TRÚC CÂY (TREES) Data structures and Algorithms2/18/2021 Cấu trúc dữ liệu và giải thuật 1 Cây nhị phân• Định nghĩa• Biểu diễn máy của cây nhị phân – Lưu trữ tuần tự (kế tiếp) – Lưu trữ móc nối• Duyệt cây nhị phân• Áp dụng cấu trúc cây – Sắp xếp – Tìm kiếm2/18/2021 Cấu trúc dữ liệu và giải thuật 2 Định nghĩa• Cây là một cấu trúc phi tuyến, thiết lập trên một tập hữu hạn các phần tử được gọi là “nút” – Nút đặc biệt gọi là gốc (root) – Liên kết phân cấp với các nút con gọi là quan hệ cha-con – Cây không có nút nào gọi là cây rỗng2/18/2021 Cấu trúc dữ liệu và giải thuật 3 Định nghĩa• Một nút là một cây, nút đó cũng là gốc của cây• Nếu T1, T2, …, Tk là các cây với n1, n2,…,nk lần lượt là các gốc, n là một nút và có quan hệ cha con với n1, n2,…,nk• Cây T được tạo lập khi n được gọi là cha của n1, n2,…,nk, các cây T1, T2, …, Tk gọi là cây con của n2/18/2021 Cấu trúc dữ liệu và giải thuật 4 Định nghĩa • Số các con của một nút được gọi là cấp • Nút có cấp bằng 0 được gọi là lá hay nút tận cùng • Nút không phải là lá gọi là nút nhánh (cành) • Cấp cao nhất của nút trên cây gọi là cấp của cây đó • Độ dài của đường đi: bằng số nút trên đường đi đó trừ 1 Gốc A A Cành B, D, G Lá C, E, F, H B C D Cấp 3 Chiều cao 4 Mức 1 A E F G Mức 2 B, C, D Mức 3 E, F, G H Mức 4 H2/18/2021 Cấu trúc dữ liệu và giải thuật 5 Cây nhị phân• Cây có thứ tự và là cây cấp hai, tức là mỗi nút có tối đa 2 con.• Hai con của một nút được phân biệt thứ tự • Nút trước gọi là nút con trái • Nút sau được gọi là nút con phải• Khi biểu diễn cây nhị phân, ta cũng cần có sự phân biệt rõ ràng giữa con trái và con phải, nhất là khi nút chỉ có một con A A B C D B E C E F G H F G D H2/18/2021 Cấu trúc dữ liệu và giải thuật 6 A Cây nhị phân • Là cây có thứ tự B A B Cây không thứ tự C D thì (a, b, c, d) là C D một cây duy nhất E (a) E A A A B B B D C D C D C E E (c) E (d)2/18/2021 (b) Cấu trúc dữ liệu và giải thuật 7 Cây nhị phân • Cây suy biến: có các nút nhánh chỉ có 1 nút con • Cây ...