Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 4 - ThS. Phạn Nguyệt Thuần

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