Bài giảng Cấu trúc dữ liệu: Chương 5 - ThS. Võ Quang Hoàng Khang

Chương 5 trình bày về cây nhị phân tìm kiếm. Thông qua chương này người học có thể nắm bắt được khái niệm về cây nhị phân tìm kiếm, đặc điểm cây nhị phân tìm kiếm, hình dạng cây nhị phân tìm kiế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: Chương 5 - ThS. Võ Quang Hoàng KhangChương 5. Cây nhị phân tìm kiếmVõ Quang Hoàng KhangEmail: vqhkhang@gmail.com 1Nội dung1. Khái niệm2. Đặc điểm3. Hình dạng4. Định nghĩa kiểu dữ liệu5. Các lưu ý khi cài đặt6. 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út gốc: là nút không có 2 2 nút cha Nút lá: là nút có bậc0 1 1 0 bằng 0 Nút nhánh: là nút có bậc 0 0 khác 0 và không phải là gốc 3 Khái niệm Độ dài đường điMức 0 từ gốc đến nút x: là số nhánh cần điMức 1 qua kể từ gốc đến xMức 2 Độ cao của cây:Mức 3 Độ dài đường đi từ gốc đến nút lá ở mức thấp nhất 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 7 kỳ luôn lớn hơn giá trị 3 36 của tất cả các node bên trái và nhỏ hơn giá trị tất1 6 15 40 cả các node bên phải Nút có giá trị nhỏ nhất 4 23 nằm ở trái nhất của cây Nút có giá trị lớn nhất nằm ở phải nhất của cây 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ước 1: Khai báo kiểu dữ liệu biểu diễn câyBước 2: Xây dựng hàm đưa dữ liệu (nhập) vào câyBước 3: Xây dựng các thao tác duyệt, tìm kiế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; // x đã có trong cây else { if(xKey) return ThemNut(t->pLeft, x); else return ThemNut(t->pRight, x); } } else { t=new TNODE; if(t==NULL) return -1; //không đủ bộ nhớ t->Key=x; t->pLeft=t->pRight=NULL; return 1; //thêm x thành công } 12}Duyệt câyThứ tự trước (NLR)Thứ tự giữa (LNR)Thứ tự sau (LRN) 13 7Bước Kết quả duyệt theo thứ 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 14Hàm duyệt NLRTại node t đang xét, nếu void NLR (TREE t)khác rỗng thì { if(t!=NULL)In giá trị của t { coutBài tậpVẽ cây nhị phân tìm kiếm theo thứ tự nhập từtrái sang phải và duyệt cây theo thứ tự trước:a. 27; 19; 10; 21; 35; 25; 41; 12; 46; 7b. H; B; C; A; E; D; Z; M; P; Tc. Huế; Đà Nẵng; Hà Nội; Vĩnh Long; Cần Thơ; Sóc Trăng; Nha Trang; Đồng Nai; Vũng Tàu; An Giang; Tiề ...