Bài giảng Cấu trúc dữ liệu: Chương 3 Cây nhị phân tìm kiếm, cung cấp các khái niệm về cây, kiến thức cấu trúc cây nhi phân, các thuật toán trên cây nhị phân tìm kiếm. Rèn luyện và nâng cao kỹ năng lập rình, ứng dụng cấu trúc dữ liệu cây nhị phân và các thuật toán trên cây nhị phân tìm kiếm giải quyết các bài toán ứng dụng. | 11 07 2020 Khoa Công Nghệ Thông Tin Chương 3 CÂY 1 Mở đầu Kiến thức cần thiết khi tìm hiểu về CÂY NHỊ PHÂN TÌM KIẾM - Các CTDL cơ bản các phương pháp cơ bản về xếp thứ tự và tìm kiếm trên LIST. - Kiểu dữ liệu cơ bản dữ liệu lưu trữ trong máy tính. - Các kiến thức về cơ sở lập trình amp kỹ thuật lập trình. Kỹ năng cần có - Có thể sử dụng Visual Studio 2010 - Có thể lập trình C 2 1 11 07 2020 Mục tiêu dạy học Cung cấp các khái niệm về cây kiến thức cấu trúc cây nhi phân các thuật toán trên cây nhị phân tìm kiếm. Rèn luyện và nâng cao kỹ năng lập rình ứng dụng cấu trúc dữ liệu cây nhị phân và các thuật toán trên cây nhị phân tìm kiếm giải quyết các bài toán ứng dụng. 3 Nội dung chính Các khái niệm - Cây - Cây nhị phân Cây nhị phân tìm kiếm Tổng kết chương Bài tập chương 3 Tài liệu tham khảo 4 2 11 07 2020 CÁC KHÁI NIỆM 5 CÁC KHÁI NIỆM CÂY TREE 6 3 11 07 2020 CÁC KHÁI NIỆM CÂY TREE Cây là một tập hợp các phần tử hay còn gọi là các node nút có quan hệ cha con phần tử cha sẽ lưu trữ quản lý địa chỉ bộ nhớ của phần tử con. Node gốc root là node duy nhất trong cây không có nút cha. Biến root sẽ lưu địa chỉ của node gốc. Mỗi node trong cây trừ node gốc có duy nhất một node cha. Một node cha có thể có nhiều con. Node là node không có phần tử con 7 CÁC KHÁI NIỆM CÂY TREE Nút gốc Nút trong Nút lá 8 4 11 07 2020 CÁC KHÁI NIỆM CÂY TREE Bậc của node là số node con của node đó. Node lá có bậc 0 Bậc của cây là bậc cao nhất của node trong cây. Một cây có bâc là n được gọi là cây bậc n. 9 CÁC KHÁI NIỆM CÂY TREE Cây có bậc 3 Bậc 1 Bậc 2 Bậc 3 Bậc 0 10 5 11 07 2020 CÁC KHÁI NIỆM CÂY TREE Mức 0 Mức 1 Mức 2 Mức 3 Cây có mức là 3 11 CÁC KHÁI NIỆM CÂY NHỊ PHÂN BINARY TREE Cây nhị phân là một cây trong đó mỗi phần tử trong cây chỉ có tối đa 2 phần tử con phần tử con bên trái phần tử con bên phải 12 6 11 07 2020 CÁC KHÁI NIỆM CÂY NHỊ PHÂN BINARY TREE Mỗi phần tử trong cây nhị phân chứa 3 thành phần thành phần - info để lưu trữ giá trị phần
