11/07/2020
1
Chương 3
CÂY
Khoa Công Nghệ Thông Tin
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 & 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++
Mở đầu
1
2
11/07/2020
2
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.
Nội dung chính
3.1 Các khái niệm
- Cây
- Cây nhị phân
3.2 Cây nhị phân tìm kiếm
3.3 Tổng kết chương
3.4 Bài tập chương 3
Tài liệu tham khảo
3
4
11/07/2020
3
3.1
CÁC KHÁI NIỆM
3.1 – CÁC KHÁI NIỆM
CÂY (TREE)
5
6
11/07/2020
4
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
3.1 – CÁC KHÁI NIỆM
CÂY (TREE)
Nút gốc
Nút lá
Nút trong
3.1 – CÁC KHÁI NIỆM
CÂY (TREE)
7
8
11/07/2020
5
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.
3.1 – CÁC KHÁI NIỆM
CÂY (TREE)
Bậc 2
Bậc 0
Bậc 3
Bậc 1
Cây có bậc 3
3.1 – CÁC KHÁI NIỆM
CÂY (TREE)
9
10