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

Chia sẻ: Tằng Túy | Ngày: | Loại File: PDF | Số trang:41

Thêm vào BST

Báo xấu

26
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

Chương 5. Cây nhị phân tìm kiếm Võ Quang Hoàng Khang Email: vqhkhang@gmail.com 1
Nội dung 1. Khái niệm 2. Đặc điểm 3. Hình dạng 4. Định nghĩa kiểu dữ liệu 5. Các lưu ý khi cài đặt 6. Các thao tác 2
Khá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ậc 0 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 đi Mức 0 từ gốc đến nút x: là số nhánh cần đi Mức 1 qua kể từ gốc đến x Mứ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ất 1 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ị Key Nút TNODE Trỏ trái Trỏ phải pLeft pRight typedef struct TNODE { Key; struct TNODE *pLeft, *pRight; } *TREE; 6
Ví dụ khai báo typedef struct TNODE { int Key; struct TNODE *pLeft, *pRight; } *TREE; 7
Các lưu ý khi cài đặt Bước 1: Khai báo kiểu dữ liệu biểu diễn cây Bước 2: Xây dựng hàm đưa dữ liệu (nhập) vào cây Bước 3: Xây dựng các thao tác duyệt, tìm kiếm, huỷ, … 8
Cấ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 9
Các thao tác 1. Tạo cây 2. Duyệt cây 3. Cho biết các thông tin của cây 4. Tìm kiếm 5. Xoá node trên cây 10
Tạ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 11
Hàm tạo cây int 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ây Thứ tự trước (NLR) Thứ tự giữa (LNR) Thứ tự sau (LRN) 13
7 Bướ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 14
Hàm duyệt NLR Tạ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 { cout
Bài tập Vẽ 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; 7 b. H; B; C; A; E; D; Z; M; P; T c. 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ền Giang; Bình Dương; Hải Dương 16
Bước Kết quả duyệt theo thứ tự LNR 7 1 L7 7 R7 2 L3 3 R3 7 R7 3 36 3 1 3 R3 7 R7 4 3 R3 7 R7 1 6 15 40 5 L6 6 7 R7 6 4 6 7 R7 4 23 7 6 7 R7 8 7 R7 9 L36 36 R36 10 15 R15 36 R36 11 23 36 R36 12 36 R36 13 40 17 KQ 1 3 4 6 7 15 23 36 40
Hàm duyệt LNR void LNR (TREE t) Tại node t đang xét, nếu { khác rỗng thì if(t!=NULL) Duyệt cây con bên trái { của t theo thứ tự LNR LNR(t->pLeft); In giá trị của t cout
Bước Kết quả duyệt theo thứ tự LRN 7 1 L7 R7 7 2 L3 R3 3 R7 7 3 36 3 1 R3 3 R7 7 4 L6 6 3 R7 7 1 6 15 40 5 4 6 3 R7 7 6 6 3 R7 7 4 23 7 3 R7 7 8 L36 R36 36 7 9 R15 15 R36 36 7 10 23 15 R36 36 7 11 15 R36 36 7 12 40 36 7 13 36 7 14 7 19 KQ 1 4 6 3 23 15 40 36 7
Hàm duyệt LRN Tại node t đang xét, nếu void LRN (TREE t) khác rỗng thì { if(t!=NULL) Duyệt cây con bên trái của t theo thứ tự LRN { LRN(t->pLeft); Duyệt cây con bên phải của t theo thứ tự LRN LRN(t->pRight); cout