Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Trần Minh Thái (Trường Đại học Hồng Bàng )

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 5: Cây nhị phân tìm kiếm" trình bày các khái niệm về cây nhị phân tìm kiếm, đặc điểm, định nghĩa kiểu dữ liệu, các lưu ý khi cài đặt, các thao tác. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Trần Minh Thái (Trường Đại học Hồng Bàng )Chương 4. Cây nhị phân tìm kiếmTrầnMinhTháiEmail:minhthai@huflit.edu.vnWebsite:www.minhthai.edu.vn 1Nội dung1. Khái niệm2. Đặc điểm3. Định nghĩa kiểu dữ liệu4. Các lưu ý khi cài đặt5. Các thao tác 2Khái niệm • Bậc của một nút: là số cây con của nútđó 2 • Nútgốc:lànútkhôngcónútcha • Nútlá:lànútcóbậcbằng0 2 2 • Nút nhánh: là nút có bậc khác 0 và khôngphảilàgốc0 1 1 0 0 0 3 Khái niệm • Chiều dài đường đi đến nút x: là số nhánh cần điMức1 qua kể từ gốc đến x • Độ cao của cây: Độ sâuMức2 (mức) của nút lá thấp nhấtMức3Mức4 x 4 Đặc điểm cây nhị phân tìm kiếm • Là cây nhị phân • Giá trị của một node bất kỳ luôn lớn hơn giá trị của tất cả các node 7 bên trái và nhỏ hơn giá trị tất cả các node bên phải 3 36 Nút có giá trị nhỏ nhất nằm ở trái nhất của cây1 6 15 40 Nút có giá trị lớn nhất nằm ở phải nhất của cây 4 23 5Định nghĩa kiểu dữ liệu Giátrị KeyNút TNODE Trỏtrái Trỏphải pLeft pRight typedef struct TNODE { Key; struct TNODE *pLeft, *pRight; } *TREE; 6Ví dụ khai báotypedef struct TNODE{ int Key; struct TNODE *pLeft, *pRight;} *TREE; 7Các lưu ý khi cài đặtBước1:KhaibáokiễudữliệubiểudiễncâyBước2:Xâydựnghàmđưadữliệu(nhập)vàocâyBước3:Xâydựngcácthaotácduyệt,tìmkiếm,huỷ,… 8Cấu trúc chương trình Khai báo cấu trúc cây Khởi tạo cây rỗng Xây dựng cây Các thao tác Hủy cây 9Các thao tác1. Tạo cây2. Duyệt cây3. Cho biết các thông tin của cây4. Tìm kiếm5. Xoá node trên cây 10Tạo cây 7 36 3 1 6 4 15 40 317466 40 15 Ø Nếu node cần thêm nhỏ hơn node đang xét thì thêm về bên trái Ø Ngược lại thì thêm về bên phải 11Hàm tạo câyint ThemNut (TREE & t, int x){ if(t!=NULL) { if(x==t->Key) return 0; else { if(xKey) ThemNut(t->pLeft, x); else ThemNut(t->pRight, x); } } else { t=new TNODE; if(t==NULL) return -1; t->Key=x; t->pLeft=t->pRight=NULL; return 1; } 12}Duyệt câyThứ tự trước (NLR)Thứ tự giữa (LNR)Thứ tự sau (LRN) 13 7Bước KếtquảduyệttheothứtựNLR 1 7 L7 R7 3 36 2 3 L3 R3 R7 1 6 15 40 3 1 R3 R7 4 6 L6 R7 4 23 5 4 R7 6 36 L36 R36 7 15 R15 R36 8 23 R36 9 40 KQ 7 3 1 6 4 36 15 23 40 14 Hàm duyệt NLRTại node t đang xét, nếu khác void NLR (TREE t)rỗng thì {• In giá trị của t if(t!=NULL)• Duyệt cây con bên trái của t { theo thứ tự NLR coutBài tậpVẽ cây nhị phân tìm kiếm theo th ...