Xem mẫu
CHƢƠNG 4
CẤU TRÚC CÂY - TREES
1
Tài Liệu Tham Khảo
Bài giảng CTDL, ĐH Công nghệ thông tin TPHCM
Bài giảng CTDL, Khoa Công nghệ thông tin, ĐH
KHTN TPHCM
Nhập môn CTDL, Dương Anh Đức, Trần Hạnh Nhi,
ĐH KHTN TPHCM
2
Nội dung
Các khái niệm và thuật ngữ cơ bản
Cây tổng quát
Cây nhị phân (Binary Tree)
Cây nhị phân tìm kiếm (BST- Binary
Search Tree)
Cây nhị phân tìm kiếm cân bằng
(AVLTree)
3
Định Nghĩa Cây
4
Định Nghĩa Cây
Cây
là một tập hợp T các phần tử (gọi là nút
của cây), trong đó có một nút đặc biệt gọi là
nút gốc, các nút còn lại đƣợc chia thành
những tập rời nhau T1, T2, …,Tn theo quan hệ
phân cấp, trong đó Ti cũng là 1 cây. Mỗi nút ở
cấp i sẽ quản lý một số nút ở cấp i+1. Quan
hệ này ngƣời ta gọi là quan hệ cha – con.
5
nguon tai.lieu . vn
CẤU TRÚC CÂY - TREES
1
Tài Liệu Tham Khảo
Bài giảng CTDL, ĐH Công nghệ thông tin TPHCM
Bài giảng CTDL, Khoa Công nghệ thông tin, ĐH
KHTN TPHCM
Nhập môn CTDL, Dương Anh Đức, Trần Hạnh Nhi,
ĐH KHTN TPHCM
2
Nội dung
Các khái niệm và thuật ngữ cơ bản
Cây tổng quát
Cây nhị phân (Binary Tree)
Cây nhị phân tìm kiếm (BST- Binary
Search Tree)
Cây nhị phân tìm kiếm cân bằng
(AVLTree)
3
Định Nghĩa Cây
4
Định Nghĩa Cây
Cây
là một tập hợp T các phần tử (gọi là nút
của cây), trong đó có một nút đặc biệt gọi là
nút gốc, các nút còn lại đƣợc chia thành
những tập rời nhau T1, T2, …,Tn theo quan hệ
phân cấp, trong đó Ti cũng là 1 cây. Mỗi nút ở
cấp i sẽ quản lý một số nút ở cấp i+1. Quan
hệ này ngƣời ta gọi là quan hệ cha – con.
5