Cây nhị phân tìm kiếm

Gi¸o ¸n:
C©y nhÞ ph©n t×m kiÕm

Häc viªn thùc hiÖn: §ång ThÞ Thu
Cao häc: K15
Cao học K15
Môn: ứng dụng CNTT trong dạy học
? ? ?
Nội dung chính của bài
I. Định nghĩa cây nhị phân
II. Biểu diễn cây nhị phân
III. Các phép toán duyệt cây nhị phân
iV. Một số thao tác trên cây nhị phân
Bài tập

ĐỊNH NGHĨA
Cây nhị phân là cây có các nút đã được khoá hóa và được sắp xếp theo một thứ tự phản ánh vị trí của nút ở trong cây.
Đặc điểm của cây nhị phân:
Mọi nút trên cây chỉ có tối đa 2 con.
Với mỗi một nút:+ Toàn bộ những nút ở cây con bên trái của nó đều có khoá nhỏ hơn khoá của nó.
+ Toàn bộ những nút ở cây con bên phải của nó đều có khoá lớn hơn khoá của nó.

Ví dụ:











Đây là cây nhị phân với toán tử ứng với gốc, toán hạng 1 ứng với cây con trái, toán hạng 2 ứng với cây con phải
Một số dạng đặc biệt của cây nhị phân










Một số dạng đặc biệt của cây nhị phân (tiếp)










II. BIỂU DIỄN CÂY NHỊ PHÂN
1. Lưu trữ kế tiếp.
Cây nhị phân đầy đủ:
- Đánh số cho các nút trên cây theo thứ tự lần lượt từ mức 1 trở lên, hết mức này đến mức khác, từ trái sang phải đối với mỗi mức.
Ví dụ: Đánh số cây ở hình dưới như sau:

.


7
1. Lưu trữ kế tiếp (tiếp).
Qui luật:
- Con của nút thứ i là các nút 2i và 2i + 1
- Cha của nút thứ j là [j/2]
Ta lưu trữ cây nhị phân đầy đủ bằng một vectơ V theo nguyên tắc: nút thứ i của cây được lưu trữ ở V[1]. Đó là cách lưu trữ kế tiếp, biết được địa chỉ nút cha sẽ tính được địa chỉ nút con và ngược lại.
Vậy với cây trên ta sẽ có

1. Lưu trữ kế tiếp (tiếp).
Nhận xét:
- Với cây nhị phân hoàn chỉnh mà các nút ở mức cuối đều dạt về phía trái thì cách lưu trữ này vẫn phù hợp.
Các cây nhị phân khác thì cách lưu trữ này gây lãng phí do có nhiều phần tử bị bỏ trống.
Do cây luôn biến động ( thêm, bớt các nút) nên cách lưu trữ này rất khó khăn cho các thao tác đó.
2. Lưu trữ móc nối
Mỗi nút gồm:



Trong đó:
Left: Ứng với con trỏ, trỏ tới cây con trái của nút đó.
Right:Ứng với con trỏ, trỏ tới cây con phải của nút đó.
Infor: Thông tin của nút.
Key: Khoá của nút.
2. Lưu trữ móc nối(tiếp)
Ví dụ: Cây nhị phân


Được lưu trữ móc nối như sau:
Khai báo cây (Dùng danh sách móc nối)
Type
Item_Type=Record
Key: Key_Type;
Infor:Data;
End;
Search_Type = ^ Node;
Node= Record
Item:Item_Type;
Left,Right: Search_Type;
End;
III. CÁC PHÉP DUYỆT CÂY NHỊ PHÂN
Duyệt theo thứ tự trước.
(Gốc T  Cây con trái  Cây con phải)
Cụ thể:
- Nếu T rỗng  không làm gì.
- Nếu T  Nul Thì
+ Thăm gốc của T
+ Duyệt cây con trái của T (Theo thứ tự trước)
+ Duyệt các cây con còn lại (theo thứ tự trước)

Cài đặt

Procedure T_T_truoc(T:Search_type);
Begin
If T= Nil then write(‘Cay rong’)
Else
Begin
Duyetgoc(T^.Node);
T_T_truoc(T^.Left);
T_T_truoc(T^.Right);
End;
End;
Duyệt theo thứ tự sau.
(Cây con trái  Cây con phải  Gốc T )
Cụ thể:
- Nếu cây T rỗng thì không làm gì
- Nếu cây T  Nul thì:
+ Duyệt cây con trái của T (theo thứ tự sau)
+ Duyệt các cây phải của gốc T (theo thứ tự sau)
+ Thăm gốc T

Cài đặt
Procedure T_T_sau(T:Search_type);
Begin
If T= Nil then write(‘Cay rong’)
Else
Begin
T_T_sau(T^.Left);
T_T_sau(T^.Right);
Duyetgoc(T^.Node);
End;
End;
Duyệt theo thứ tự giữa.
(Cây con trái  Gốc T  Cây con phải)
Cụ thể:
Nếu T= Nul thì không làm gì.
Nếu T  Nul thì
+ Duyệt cây con trái của của T (theo thứ tự giữa)
+ Thăm gốc T
+ Duyệt cây con phải của T (theo thứ tự giữa)


Cài đặt
Procedure T_T_Giua(T:Search_type);
Begin
If T <> Nil then
Begin
T_T_Giua(T^.Left);
T_T_Giua(T^.Right);
Duyetgoc(T^.Node);
End;
End;

MỘT SỐ THAO TÁC TRÊN CÂY NHỊ PHÂN

Trả ra một phần tử có khoá đã biết.
Chèn một phần tử vào cây nhị phân
Xoá một phần tử khỏi cây nhị phân
1. Trả ra một phần tử có khoá đã biết.
Cách 1: Dùng vòng lặp

Function phantu(T:search_Type;k:key_Type):Search_type
Var temp = Search_Type;
Begin
Temp:= T;
While (temp <>Nil) and (Tem^.Item.key<>k) Do
If Tem^.Item.key > k then Temp:=Temp ^.Left
Else Temp:= Temp ^. Right
Phantu:= Temp;
End;
1. Trả ra một phần tử có khoá đã biết (tiếp)
Cách 2: Dùng đệ quy

Function phantu(T:search_Type;k:key_Type):Search_type;
Begin
If T = Nil then phantu:= Nil
Else
If Tem^.Item.key = k then phantu:= T
Else phantu:= phantu(T ^.left)
Else phantu:= phantu(T ^. Right);
End;
2. Chèn một phần tử vào cây nhị phân
Cách thực hiện:
- Tìm vị trí chèn.
- Thực hiện chèn
Thuật toán:
Nếu cây rỗng thì chèn vào gốc.
Nếu khoá của phần tử mới < khoá của gốc thì chèn vào cây con trái.
Nếu khoá của phần tử mới > khoá của gốc thì chèn vào cây con phải.
2. Chèn một phần tử vào cây nhị phân (tiếp)
Mã hoá
Procedure Insert(Var T:search_Type; new Item:Item_Type) ;
Begin
If T = Nil then
Begin
New(tg);
Tg^.Item:= NewwItem;
T ^.Tg;
T ^.Left:= Nil;
T ^.Right:= Nil;
End
Else
If Tem^.Item.key = T ^.Item.key then Insert(newItem,T ^.right)
Else Insert(NewItem. ^.Right);
End;
3. Xoá một phần tử khỏi cây nhị phân
Cách thực hiện:
- Tìm phần tử cần xóa.
- Xoá (có 3 khả năng)
+ Nút cần xoá là lá (1).
+ Nút cần xoá có một cây con (2).
+ Nút cần xoá có đủ hai cây con (3).
3. Xoá một phần tử khỏi cây nhị phân (tiếp)
Giải thuật: Ứng với từng khả năng ta làm như sau
(1) Cho nút cha chỉ vào Nil
(2) Cho nút cha của nút cần xoá chỉ vào nút con của nút cần xoá.
(3) + Tìm phần tử lớn nhất của cây con bên trái của nút đó hoặc phần tử nhỏ nhất của cây con bên phải.
+ Thay phần tử cần xoá bằng phần tử vừa tìm thấy.
+ Xoá phần tử đó ra khỏi cây
3. Xoá một phần tử khỏi cây nhị phân (tiếp)
Mã hoá
Procedure Delete(k:key_Type; Var T: search_Type);
Begin
If k < T ^.Item.key then Delete(x,T ^.Left)
Else If x > T ^.Item.key then Delete(x, T ^.Right)
Else If T ^.Left=Nil then T:= T ^.Right
Else
If T ^.Right = Nil then T:= T ^.Left
Else
Begin
Temp:= T ^.Left;
While Temp ^.Right <> Nil Do Temp:= Temp ^.Right;
T ^.Item:=Temp ^.Item;
Delete(Temp ^.Item.key,T ^.Left);
End;
End;
CÂU HỎI VÀ BÀI TẬP

Bài 1: Vẽ cây nhị phân biểu diễn các biểu thức sau đây và viết chúng dưới dạng tiền tố, hậu tố
(a * b + c)/(d – e * f)
A /(B + C) + D * E – A * C
Bài 2: Cho cây nhị phân







Hãy viết các nút được thăm khi duyệt cây này:
a. Theo thứ tự trước.
b. Theo thứ tự giữa.
c. Theo thứ tự sau.
Bài 3: Cho cây nhị phân







Hãy minh hoạ phần bộ nhớ khi thực hiện lưu trữ kế tiếp đối với cây trên
Bài 4: Tìm cây nhị phân mà các nút sẽ xuất hiện theo một dãy giống nhau khi duyệt:
a. Theo thứ tự trước và thứ tự giữa.
b. Theo thứ tự trước và thứ tự sau.
c. Theo thứ tự giữa và thứ tự sau.