Chương 6: Cây
Cây
Khái niệm về cây và cây nhị phân
Biểu diễn cây nhị phân và cây tổng quát
Bài toán duyệt cây nhị phân
41 trang |
Chia sẻ: phuongt97 | Lượt xem: 356 | Lượt tải: 0
Bạn đang xem trước 20 trang nội dung tài liệu Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 6: Cây - Ngô Quang Thạch, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
CẤU TRÚC DỮ LIỆU VÀ
GIẢI THUẬT
NGÔ QUANG THẠCH
Email: thachnq@gmail.com
ĐT: 01273984123
Chương 6: Cây
Khái niệm về cây và cây nhị phân
Biểu diễn cây nhị phân và cây tổng quát
Cây
Bài toán duyệt cây nhị phân
Giới thiệu
Cây là một cấu trúc rất gần gũi và có nhiều ứng dụng
trong thực tế. Cây là một cấu trúc phân cấp trên một
tập hợp nào đó các đối tượng.
Một ví dụ quen thuộc về cây, đó là cây thư mục
Ví dụ xuất cây từ lện TREE trong CMD
├───Code Snippets
│ │ ├───SQL
│ │ │ └───My Code Snippets
│ │ ├───Visual Basic
│ │ │ └───My Code Snippets
│ │ ├───Visual C#
│ │ │ └───My Code Snippets
│ │ ├───Visual Web Developer
│ │ │ ├───My HTML Snippets
│ │ │ └───My JScript Snippets
│ │ └───XML
│ │ └───My Xml Snippets
│ ├───Projects
│ │ ├───VSMacros80
│ │ │ ├───MyMacros
│ │ │ └───Samples
│ │ └───Web
│ ├───Settings
│ ├───StartPages
│ └───Templates
Ví dụ cấu trúc của trang web
Khái niệm về cây
1. Định nghĩa
Cây là một tập hợp T các phần tử (gọi là nút của cây)
trong đó có một nút đặc biệt gọi là gốc, các nút còn lại
được chia thành những tập rời nhau T1, T2,, Tn theo
quan hệ phần cấp trong đó Ti cũng là cây.
Giữa các nút có một quan hệ phân cấp gọi là "quan hệ
cha con"
Một số khái niệm cơ bản
Bậc của một nút : là số con của nút đó.
Bậc của một cây : là bậc lớn nhất của các nút trong cây
( số cây con tối đa của một nút trong cây ). Cây có bậc
n thì gọi là cây n-phân.
Nút lá : là nút bậc 0.
Nút nhánh : là nút có bậc khác 0 và không phải là gốc.
Xét một cây
A là cha của B, C, D,
Còn G, H, I là con của D
Cấp của A là 3
Cấp của B là 2
Cấp của C là 0.
Các nút lá: E, F, C,
G, J, K và I
Một số khái niệm cơ bản
Mức của một nút :
. Mức (gốc(T))=1.
. Gọi T1,T2,T3,.,Tn là cây con của T0.
Mức (T1)=Mức(T2)=Mức(T3)==Mức(Tn)=Mức(T0)+1
- Ðộ 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.
Rừng cây: là tập hợp nhiều cây trong đó thứ tự các cây là
quan trọng.
Cây nhị phân
1. Ðịnh nghĩa
Cây nhị phân là cây mà mỗi nút có tối đa 2 cây con.
Cây nhị phân Cây nhị phân đầy đủ
Cây nhị phân
2. Biểu diễn cây nhị phân
Thông tin lưu tại nút :
Info.
Ðịa chỉ nút gốc của
cây con trái trong bộ nhớ
: L.
Ðịa chỉ nút gốc của
cây con phải trong bộ
nhớ : R.
Cài đặt định nghĩa cấu trúc
typedef struct tagNODE
{
DATA Info;
struct tagNODE *Left,*Right;
}NODE;
typedef NODE *TREE;
Cây nhị phân tìm kiếm
1. Ðịnh nghĩa
Cây nhị phân tìm kiếm (CNPTK) là cây nhị phân
trong đó tại mỗi nút, khoá của tất cả các nút thuộc cây
con trái đều nhỏ hơn khoá của nút đang xét và nhỏ
hơn khoá của tất cả các nút thuộc cây con phải.
2. Ví dụ
Các thao tác trên CNPTK
Duyệt cây
. Duyệt theo thứ tự trước ( Node-Left-Right)
. Duyệt theo thứ tự giữa ( Left-Node-Right)
. Duyệt theo thứ tự sau ( Left-Right-Node)
Tìm một phần tử x trong cây
Thêm một phần tử x vào cây
Huỷ một phần tử có khoá x
Duyệt theo thứ tự trước ( Node-Left-Right)
Kiểu duyệt này trước tiên thăm nút gốc sau đó thăm các
nút của cây con trái rồi phải. Thủ tục duyệt có thể trình bày đơn
giản như sau:
void NLR(TREE Root)
{
if (root!=NULL)
{
; // Xử lý tương ứng theo nhu cầu
NLR(RootLeft);
NLR(RootRight);
}
}
Ví dụ NLR
Duyệt theo thứ tự trước
A B D G H E C F I G
Duyệt theo thứ tự giữa ( Left-Node-Right)
Kiểu duyệt này trước tiên thăm các nút của cây con trái sau
đó tham nút gốc rồi đến cây con phải. Thủ tục duyệt có thể
trình bày đơn giản như sau:
void LNR(TREE Root)
{
if (root!=NULL)
{
LNR(RootLeft);
;//Xử lý tương ứng theo nhu cầu
LNR(RootRight);
}
}
Ví dụ LNR
Duyệt theo thứ giữa
G D H B E A F I C G
Duyệt theo thứ tự sau ( Left-Right-Node)
Kiểu duyệt này trước tiên thăm các nút của cây con trái sau đó
thăm đến cây con phải rồi cuối cùng mớithăm nút gốc. Thủ tục
duyệt có thể trình bày đơn giản như sau:
void LRN(TREE Root)
{
if (root!=NULL)
{
LRN(RootLeft);
LRN(RootRight);
; //Xửlý tương ứng theo nhu cầu
}
}
Ví dụ LRN
Duyệt theo thứ tự sau
G H D E B I F G C A
Tìm một phần tử x trong cây
Để tìm một phần tử x trong cây ta chỉ đơn thuần duyệt qua các
phần tử cho đến khi tìm thấy x.
NODE *SearchTree(TREE Root, DATA x)
{ NODE *p=Root;
while (p!=NULL)
{ if (x = =pInfo) return p;
else if (x<pInfo)
p=pLeft;
else p=pRight;
}
return NULL;
}
Thêm một phần tử x vào cây
void AddTree(TREE &Root, DATA x)
{ if (Root!=NULL)
{
if (x==RootInfo) //Báo X bị trùng";
else if (x<RootInfo)
AddTree(RootLeft,x);
else AddTree(RootRight,x);
}
else
{
Root = (NODE*)malloc(sizeof(NODE));
RootInfo = x;
RootLeft = NULL;
RootRight = NULL;
}
}
Huỷ một phần tử có khoá x
Bước 1 : Tìm phần tử p có khoá x.
Bước 2 : Có 3 trường hợp :
p là nút lá : huỷ p.
p có 1 con : tạo liên kết từ phần tử cha của p đến con của p rồi huỷ p.
p có 2 con : tìm phần tử thế mạng cho p theo nguyên tắc:
• "Phần tử thế mạng phải nhất của cây con trái của p (phần tử lớn nhất
trong các phần tử nhỏ hơn p)" hay :
• "Phần tử thế mạng trái nhất của cây con phải của p (phần tử nhỏ
nhất trong các phần tử lớn hơn p)."
• Sau đó chép thông tin của phần tử thế mạng vào p và huỷ phần tử thế
mạng (do phần tử thế mạng có tối đa một con).
Xóa nút lá
Xóa nút chỉ có một nhánh con
Xóa nút có 2 nhánh con
Chọn cực phải của bên trái thế làm gốc
Xóa nút có 2 nhánh con
Chọn cực trái của nhánh con bên phải làm thế gốc
Cài đặt
void DelNode(TREE &Root, DATA x) void SearchStandFor(tree
{ NODE *q; &p, tree &q)
If (Root==NULL) “Báo cây rỗng”; {
else if(q->right!=NULL)
{ if (xright);
else
else if (x>RootInfo) DelNode(RootRight,x);
{
else p->data=q->data;
{ q=Root; p=q;
if (qRight==NULL) q=q->left;
Root=qLeft; }
else if (qLeft==NULL) }
Root=qRight;
else SearchStandFor(RootLeft,q);
free(q);
}
}
}
IV. Cây cân bằng
Ðịnh nghĩa
Cây nhị phân tìm kiếm cân bằng là cây mà tại mỗi
nút của nó độ cao của cây con trái và của cây con phải
chênh lệch không quá một.
Phép duyệt cây
Duyệt qua từng node của cây (mỗi node 1 lần)
Cách duyệt:
. Chính thức: NLR, LNR, LRN, NRL, RNL, RLN
. Chuẩn: NLR (preorder), LNR (inorder), LRN (postorder)
Ví dụ về phép duyệt cây NLR
A
B C
D E F G
H I J K L M
N O P
Kết quả: A B D H I N E J O K C F L P G M
Ví dụ về phép duyệt cây LNR
A
B C
D E F G
H I J K L M
N O P
Kết quả: H D N I B J O E K A F P L C M G
Ví dụ về phép duyệt cây LRN
A
B C
D E F G
H I J K L M
N O P
Kết quả: H N I D O J K E B P L F M G C A
Cây nhị phân tìm kiếm – Binary search tree (BST)
Một cây nhị phân tìm kiếm (BST) là một cây nhị phân
rỗng hoặc mỗi node của cây này có các đặc tính sau:
. 1. Khóa của node gốc lớn (hay nhỏ) hơn khóa của tất cả các
node của cây con bên trái (hay bên phải)
. 2. Các cây con (bên trái, phải) là BST
Tính chất:
. Chỉ cần đặc tính 1 là đủ
. Duyệt inorder sẽ được danh sách có thứ tự
Ví dụ BST
25
10 37
3 18 29 50
1 6 12 20 35 41
5 13 32
Duyệt inorder: 1 3 5 6 10 12 13 18 20 25 29 32 35 37 41 50
Các tính chất khác của BST
Node cực trái (hay phải):
. Xuất phát từ node gốc
. Đi sang trái (hay phải) đến khi không đi được nữa
Khóa của node cực trái (hay phải) là nhỏ nhất (hay lớn
nhất) trong BST
BST là cây nhị phân có tính chất:
. Khóa của node gốc lớn (hay nhỏ) hơn khóa của node cực trái
(hay cực phải)
Tìm kiếm trên BST
Chọn hướng tìm theo tính chất của BST:
. So sánh với node gốc, nếu đúng thì tìm thấy
. Tìm bên nhánh trái (hay phải) nếu khóa cần tìm nhỏ hơn (hay
lớn hơn) khóa của node gốc
Giống phương pháp tìm kiếm nhị phân
Thời gian tìm kiếm
. Tốt nhất và trung bình: O(lg n)
. Tệ nhất: O(n)
Giải thuật tìm kiếm trên BST
Algorithm BST_search
Input: subroot là node gốc và target là khóa cần tìm
Output: node tìm thấy
1. if (cây rỗng)
1.1. return not_found
2. if (target trùng khóa với subroot)
2.1. return subroot
3. if (target có khóa nhỏ hơn khóa của subroot)
3.1. Tìm bên nhánh trái của subroot
4. else
4.1. Tìm bên nhánh phải của subroot
End BST_search
Ví dụ tìm kiếm trên BST
25
10 37
3 18 29 50
1 6 12 20 35 41
5 13 32
KhácGiốngNode nhau gốcnhau nhỏlớn hơnhơn
Số node duyệt: 5
Tìm kiếm 13 Tìm thấy Số lần so sánh: 9
Ví dụ tìm kiếm trên BST
25
10 37
3 18 29 50
1 6 12 20 35 41
5 13 32
NodeKhác nhaugốc nhỏlớn hơnhơn
Số node duyệt: 5
Tìm kiếm 14 Không tìm thấy Số lần so sánh: 10
Bài tập xây dựng cây nhị phân tìm kiếm
Xây dựng cây nhị phân tìm kiếm sau:
50, 40, 30, 20, 10, 15, 70, 60, 80, 90, 45, 35, 25, 55,
65, 75, 85
Thực hiện Xóa nút 80 trong cây
Các file đính kèm theo tài liệu này:
- bai_giang_cau_truc_du_lieu_va_giai_thuat_chuong_6_cay_ngo_qu.pdf