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.
AMBIENT/
Chủ đề:
Nội dung Text: 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ếm
Trần Minh Thái
Email: minhthai@huflit.edu.vn
Website: www.minhthai.edu.vn
1
- Nội dung
1. Khái niệm
2. Đặc điểm
3. Định nghĩa kiểu dữ liệu
4. Các lưu ý khi cài đặt
5. 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ó nút cha
•
Nút lá: là nút có bậc bằng 0
2 2 •
Nút nhánh: là nút có bậc khác 0 và
không phải là gốc
0 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 đi
Mức 1 qua kể từ gốc đến x
•
Độ cao của cây: Độ sâu
Mức 2 (mức) của nút lá thấp
nhất
Mức 3
Mức 4 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ây
1 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ị 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;
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â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 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 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:
•
27; 19; 10; 21; 35; 25; 41; 12; 46; 7
•
H; B; C; A; E; D; Z; M; P; T
•
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
KQ 1 3 4 6 7 15 23 36
17 40
- Hàm duyệt LNR
Tại node t đang xét, nếu khác void LNR (TREE t)
rỗng thì {
•
Duyệt cây con bên trái của t if(t!=NULL)
theo thứ tự LNR {
•
In giá trị của t LNR(t->pLeft);
•
Duyệt cây con bên phải 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 19 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 LRN(t->pRight);
của t theo thứ tự LRN cout
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
