Cây nhị phân

CÂY NHỊ PHÂN TÌM KIẾM
TMT
1
Nội dung
Các khái niệm
Đặc điểm
Hình dạng
Các khái niệm
Định nghĩa kiểu dữ liệu
Các lưu ý khi cài đặt
Các thao tác
2
Các khái niệm
Bậc của một nút: là số cây con của nút đó.
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.
Nút nhánh: là nút có bậc khác 0 và không phải là gốc.
3
Các khái niệm (tt)
Độ dài đường đi từ gốc đến nút x: là số nhánh cần đi qua kể từ gốc đến x.
Độ cao của cây: Độ 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 kỳ luôn lớn hơn giá trị của tất cả các node bên trái và nhỏ hơn giá trị tất cả các node bên phải
Nút có giá trị nhỏ nhất 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
7
3
36
1
6
15
40
23
4
5
Nút
Định nghĩa kiểu dữ liệu
typedef struct TNODE
{
Key;
struct TNODE *pLeft, *pRight;
} *TREE;
Giá trị
Trỏ trái
Trỏ phải
TNODE
Key
pLeft
pRight
6
Ví dụ khai báo cây nhị phân biểu diễn các node là số nguyên
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ỷ, …

Các lưu ý khác:
1. Trước khi tạo node mới phải xin cấp phát vùng nhớ.
2. Trước khi tạo cây mới phải khởi tạo cây rỗng.
3. Trước khi kết thúc chương trình phải huỷ cây (giải phóng vùng nhớ).
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. Xây dựng 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
Các thao tác
1. Xây dựng 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
11
40
15
4
6
1
36
3
Xây dựng cây
7
Nếu node cần thêm < node đang xét thì thêm về bên trái.
Ngược lại thì thêm về bên phải.
12
Xây dựng cây (tt)
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;
}
}
13
Các thao tác
1. Xây dựng 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
14
Các thao tác
1. Xây dựng 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
15
Duyệt cây
Thứ tự trước (NLR)
Thứ tự giữa (LNR)
Thứ tự sau (LRN)
16
NLR
7 L7 R7
7 3 L3 R3 36 L36 R36
7 3 1 6 L6 36 15 R15 40
7 3 1 6 4 36 15 23 40
7
3
36
1
6
15
40
23
4
17
NLR
Tại node t đang xét, nếu khác rỗng thì
. In giá trị của t
. Duyệt cây con bên trái của t theo thứ tự NLR
. Duyệt cây con bên phải của t theo thứ tự NLR
void NLR (TREE t)
{
if(t!=NULL)
{
cout<Key<<“ ”;
NLR(t->pLeft);
NLR(t->pRight);
}
}
18
BÀI TẬP
Bài 1
Hãy xây dựng cây nhị phân tìm kiếm theo thứ tự nhập sau:
27 19 10 21 35 25 41 12 46 7
Hãy duyệt cây trên theo thứ tự trước
Bài 2
Hãy xây dựng cây nhị phân tìm kiếm theo thứ tự nhập sau:
H B C A E D Z M P T
Hãy duyệt cây trên theo thứ tự trước
Bài 3
Hãy xây dựng cây nhị phân tìm kiếm theo thứ tự nhập sau:
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
19
LNR
L7 7 R7
L3 3 R3 7 L36 36 R36
1 3 L6 6 7 15 R15 36 40
1 3 4 6 7 15 23 36 40
7
3
36
1
6
15
40
23
4
20
LNR
Tại node t đang xét, nếu khác rỗng thì
. Duyệt cây con bên trái của t theo thứ tự LNR
. In giá trị của t
. Duyệt cây con bên phải của t theo thứ tự LNR
void LNR (TREE t)
{
if(t!=NULL)
{
LNR(t->pLeft);
cout<Key<<“ “;
LNR(t->pRight);
}
}
21
LRN
L7 R7 7
L3 R3 3 L36 R36 36 7
1 L6 6 3 R15 15 40 36 7
1 4 6 3 23 15 40 36 7
7
3
36
1
6
15
40
23
4
22
LRN
Tại node t đang xét, nếu khác rỗng thì
. Duyệt cây con bên trái của t theo thứ tự LRN
. Duyệt cây con bên phải của t theo thứ tự LRN
. In giá trị của t
void LRN (TREE t)
{
if(t!=NULL)
{
LRN(t->pLeft);
LRN(t->pRight);
cout<Key<<“ “;
}
}
23
BÀI TẬP
Bài 4
Hãy xây dựng cây nhị phân tìm kiếm theo thứ tự nhập sau:
27 19 10 21 3 15 41 50 30 27
Hãy duyệt cây trên theo thứ tự giữa
Bài 5
Hãy xây dựng cây nhị phân tìm kiếm theo thứ tự nhập sau:
H B C A E D T M X O
Hãy duyệt cây trên theo thứ tự sau
24
Vấn đề cần quan tâm
Xây dựng cây từ kết quả duyệt theo thứ tự trước (NLR)
Chọn giá trị đầu tiên làm node gốc.
Lần lượt đưa các giá trị còn lại từ trái sang phải vào cây theo nguyên tắc xây dựng cây.
Xây dựng cây từ kết quả duyệt theo thứ tự sau (LRN)
Chọn giá trị cuối cùng làm node gốc.
Lần lượt đưa các giá trị còn lại từ phải sang trái vào cây theo nguyên tắc xây dựng cây.
25
Vấn đề cần quan tâm (tt)
Xây dựng cây từ kết quả duyệt theo thứ tự giữa (LNR)
Gọi r: Số lượng giá trị cho trước.
Gọi m = r div 2: Giá trị ở giữa.
Chọn giá trị thứ m làm node gốc.
Lần lượt đưa các giá trị bắt đầu từ vị trí m-1 lùi về trái vào cây theo nguyên tắc xây dựng cây.
Lần lượt đưa các giá trị bắt đầu từ vị trí m+1 đến cuối vào cây theo nguyên tắc xây dựng cây.
26
BÀI TẬP
Bài 6
Hãy vẽ cây nhị phân tìm kiếm T biết rằng khi duyệt cây T theo thứ tự Left-Right-Node thì được dãy sau: 1, 4, 7, 5, 3, 16, 18, 15, 29, 25, 30, 20, 8.
Hãy duyệt cây T trên theo thứ tự Node-Left-Right.
Cây T có chiều cao là bao nhiêu? Tìm các đường đi từ gốc có độ dài là 4 trên cây
27
BÀI TẬP
Bài 7
Hãy vẽ cây nhị phân tìm kiếm T biết rằng khi duyệt cây T theo thứ tự Node-Left-Right thì được dãy sau: 9, 4, 1, 3, 8, 6, 5, 7, 10, 14, 12, 13, 16, 19.
Hãy duyệt cây T trên theo thứ tự Left-Right-Node.
Liệt kê các nút lá của cây. Liệt kê các nút nhánh của cây.
28
CÀI ĐẶT
void Nhap(TREE &t)
{
int x;
do{
cout<<“Nhap gia tri: “;
cin>>x;
int kq=ThemNut(t, x);
if(kq==0||kq==-1)
break;
}while (true);
}
29
CÀI ĐẶT
void main()
{
TREE t;
t=NULL;
Nhap(t);
cout<<“Duyet cay theo thu tu giua: “;
LNR(t);

Huy(t);
}
30
Các thao tác
1. Xây dựng 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
31
Các thao tác
1. Xây dựng 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
32
Cho biết các thông tin của cây
Số node lá (node bậc 0)
Số node có 1 cây con (node bậc 1)
Số node chỉ có 1 cây con phải
Số node có 1 cây con trái
Số node 2 cây con (node bậc 2)
Độ cao của cây
Số node của cây
Các node trên từng mức của cây
Độ dài đường đi từ gốc đến node x
33
Số node lá
Nếu node t khác rỗng thì
. Nếu node t có bậc 0 thì
Trả về 1
. Ngược lại
Trả về Số node lá cây trái t
+ Số node lá cây phải t
Nếu node t rỗng thì
Trả về 0
34
Số node lá (tt)
int DemNutLa (TREE t)
{
if(t)
{
if(t->pLeft==NULL && t->pRight==NULL)
return 1;
else
return DemNutLa(t->pLeft)+DemNutLa(t->pRight);
}
else
return 0;
}
35
Số node có 1 cây con
Nếu node t khác rỗng thì
d=Số node bậc 1 của cây trái t
+ Số node bậc 1 của cây phải t
Nếu node t có bậc 1 thì trả về d+1
Ngược lại trả về d
Nếu node t rỗng thì
Trả về 0
36
Số node có 1 cây con
int DemNut1Con(TREE t)
{
if(t)
{
int d=DemNut1Con(t->pLeft)+DemNut1Con(t->pRight);
if((t->pLeft!=NULL&&t->pRight==NULL)
||(t->pLeft==NULL&&t->pRight!=NULL))
return d+1;
else
return d;
}
else
return 0;
}
37
Số node chỉ có 1 cây con phải
Nếu node t khác rỗng thì
d = Số node chỉ có 1 cây con phải của cây con trái t
+ Số node chỉ có 1 cây con phải của cây con phải t
Nếu node t chỉ có 1 cây con phải thì trả về d+1
Ngược lại trả về d
Nếu node t rỗng thì
Trả về 0
38
Số node có 1 cây con phải
int DemNut1ConPhai(TREE t)
{
if(t)
{
int d=DemNut1ConPhai(t->pLeft)
+DemNut1ConPhai(t->pRight);
if(t->pLeft==NULL && t->pRight!=NULL)
return d+1;
else
return d;
}
else
return 0;
}
39
Số node chỉ có 1 cây con trái
40
Số node có 2 cây con
41
Độ cao của cây
int DoCaoCay(TREE t)
{
if(t)
{
int t1=DoCaoCay(t->pLeft);
int t2=DoCaoCay(t->pRight);
return Max(t1, t2)+1;
}
else
return 0;
}
42
Số node của cây
43
Các node trên từng mức
Mức 2: 1 6 15 40
7
3
36
1
6
15
40
23
4
44
Các node trên từng mức
void InMuck(TREE t, int k, int m=0)
{
if(t)
{
if(m==k)
{
printf("%d ", t->Key);
return;
}
else
{
m++;
InMuck(t->pLeft, k,m);
InMuck(t->pRight, k, m);
}
}
}
45
In các node của tất cả mức
46
Độ dài đường đi từ gốc đến node x
47
Các thao tác
1. Xây dựng 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
48
Các thao tác
1. Xây dựng 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
49
Tìm kiếm
Tìm x
Tìm min
Tìm min của cây con bên phải
Tìm max
Tìm max của cây con bên trái
50
Ví dụ tìm x = 23
7
3
36
1
6
15
40
23
4
51
Tìm x
TNODE * TimKiem(TREE t,int x)
{
if(t!=NULL)
{
if(t->Key==x) return t;
if(xKey)
return TimKiem(t->pLeft,x);
else
return TimKiem (t->pRight,x);
}
return NULL;
}
52
Tìm min
TNODE* Min(TREE t)
{
while(t->pLeft!=NULL)
{
t=t->pLeft;
}
return t;
}
53
Min cây con bên phải
54
Tìm max
55
Tìm max cây con bên trái
56
Các thao tác
1. Xây dựng 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
57
Các thao tác
1. Xây dựng 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
58
Xóa node trên cây
Node lá
Node có 1 cây con
Node có 2 cây con
7
3
36
1
6
15
40
23
4
59
Xóa node lá
Xóa 1
Xóa 23
7
3
36
1
6
15
40
23
4
60
Xóa node 1 cây con
Xóa 6
Xóa 15
7
3
36
1
6
15
40
23
4
4
23
61
Xóa node 2 cây con
Tìm node thế mạng
Cách 1: Tìm node trái nhất của cây con phải
Cách 2: Tìm node phải nhất của cây con trái

Xóa 36 (Cách 2)
7
3
36
1
6
15
40
23
4
16
23
62
Tìm node thế mạng
void TimTheMang (TREE &pHuy,TREE & q)
{
if(q->pLeft)
TimTheMang(pHuy, q->pLeft);
else
{
pHuy->Key=q->Key;
pHuy=q;
q=q->pRight;
}
}
63
Xóa một node có giá trị x
void HuyNut (TREE & t, int x)
{
if(t!=NULL)
{ if(xKey) HuyNut(t->pLeft,x);
else{
if(x>t->Key) HuyNut(t->pRight,x);
else{
TNODE * pHuy=t;
if(t->pLeft==NULL) t=t->pRight;
else
if(t->pRight==NULL) t=t->pLeft;
else TimTheMang(pHuy,t->pRight);
delete pHuy;
}
}

}
}
64
Huỷ toàn bộ cây
Nếu node khác rỗng
Hủy cây bên trái t
Hủy cây bên phải t
Hủy node t
65
Cho dãy số theo thứ tự nhập từ trái sang phải như sau: 20 15 35 30 11 13 17 36 47 16 38 28 14
Hãy vẽ cây nhị phân tìm kiếm cho dãy số trên.
Hãy cho biết kết quả duyệt cây trên theo thứ tự trước, giữa và sau.
Cho biết độ cao của cây, các nút lá, các nút có bậc 2.
Vẽ lại cây sau khi thêm nút: 25 và 91
Trình bày từng bước và vẽ lại cây sau khi lần lượt xoá các nút: 11 và 35
66