Tổng quan về các thuật ngữ và kiểu dữ liệu trừu tượng cây

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.

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

Tài liệu tham khảo

[1] Aho, A. V. , J. E. Hopcroft, J. D. Ullman. "Data Structure and Algorihtms", 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)

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.
• 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

Định nghĩa

• Một nút đơn độc là một cây. Nút này cũng chính là nút gốc của cây.
• Giả sử ta có n là một nút đơn độc và k cây T1,.., Tk với các nút gốc tương ứng là n1,.., nk thì có thể xây dựng một cây mới bằng cách cho nút n là cha của các nút n1,.., nk. Cây mới này có nút gốc là nút n và các cây T1,.., Tk được gọi là các cây con. Tập rỗng cũng được coi là một cây và gọi là cây rỗng kí hiệu .

Ví dụ: xét mục lục của một quyển sách.