tailieunhanh - Bài giảng Cấu trúc dữ liệu: Phần 2 - ĐH Cần Thơ

Nối tiếp phần 1 cuốn "Bài giảng Cấu trúc dữ liệu" mời các bạn cùng tìm hiểu phần 2 để nắm bắt một số thông tin cơ bản về cấu trúc cây; tập hợp; đồ thị. Hy vọng tài liệu là nguồn thông tin hữu ích cho quá trình học tập và nghiên cứu của các bạn. | Cấu trúc dữ liệu Chương III Cấu trúc cây CHƯƠNG III CẤU TRÚC CÂY TREES TỔNG QUAN 1. Mục tiêu Sau khi học xong chương này sinh viên phải Nắm vững khái niệm về cây Cài đặt được cây trees và thực hiện các phép toán trên cây. 2. Kiến thức cơ bản cần thiết Để học tốt chương này sinh viên phải nắm vững kỹ năng lập trình căn bản như Kiểu mẩu tin record kiểu mảng array và kiểu con trỏ pointer Các cấu trúc điều khiển lệnh vòng lặp. Lập trình theo từng modul chương trình con và cách gọi chương trình con đó. Lập trình đệ qui và gọi đệ qui. Kiểu dữ liệu trừu tượng danh sách 3. Tài liệu tham khảo 1 Aho A. V. J. E. Hopcroft J. D. Ullman. Data Structure andAlgorihtms Addison-Wesley 1983 2 Đỗ Xuân Lôi . Cấu trúc dữ liệu và giải thuật . Nhà xuất bản khoa học và kỹ thuật. Hà nội 1995. chương 6- Trang 122 chương 10 trang 274 3 N. Wirth Cấu trúc dữ liệu giải thuật Chương trình 1983. 4 Nguyễn Trung Trực Cấu trúc dữ liệu . BK tp HCM 1990. chương 3 trang 112 chương 5 trang 299 5 Lê Minh Trung Lập trình nâng cao bằng Pascal với các cấu trúc dữ liệu 1997 chương 9 12 4. Nội dung cốt lõi Trong chương này chúng ta sẽ nghiên cứu các vấn đề sau Các thuật ngữ cơ bản. 73 Cấu trúc dữ liệu Ch ương III Cấu trúc cây Kiểu dữ liệu trừu tượng Cây Cài đặt cây Cây nhị phân Cây tìm kiếm nhị phân I. CÁC THUẬT NGỮ CƠ BẢN TRÊN CÂY Cây là một tập hợp các phần tử gọi là nút nodes trong đó có một nút được phân biệt gọi là nút gốc root . Trên tập hợp các nút này có một quan hệ gọi là mối quan hệ cha - con parenthood để xác định hệ thống cấu trúc trên các nút. Mỗi nút trừ nút gốc có duy nhất một nút cha. Một nút có thể có nhiều nút con hoặc không có nút con nào. Mỗi nút biểu diễn một phần tử trong tập hợp đang xét và nó có thể có một kiểu nào đó bất kỳ thường ta biểu diễn nút bằng một kí tự một chuỗi hoặc một số ghi trong vòng tròn. Mối quan hệ cha con được biểu diễn theo qui ước nút cha ở dòng trên nút con ở dòng dưới và được nối bởi một đoạn thẳng. Một cách hình thức ta có thể định nghĩa cây một cách đệ qui như