Xem mẫu
- 8/4/2020
2.2.4 Cài đặt bởi mảng
❖Ưu điểm:
▪ Truy cập nhanh, ngẫu nhiên và như nhau đối với mọi phần tử
nhờ vào chỉ số
▪ Thao tác tìm kiếm dễ dàng
❖Nhược điểm
▪ Kích thước mảng trong mọi ngôn ngữ lập trình đều cố định→
Hạn chế độ dài của danh sách, trong khi danh sách thường
xuyên thêm bớt không cố định độ dài
▪ Việc thêm bớt khó khăn do phải dịch chuyển nhiều phần tử
(thời gian chạy là O(n))
Cấu trúc dữ liệu và giải thuật 79
CHƯƠNG 3: CÂY (9t)
3.1 ĐỊnh nghĩa và khái niệm cơ bản
3.2 Một số phép toán trên cây
3.3 Cài đặt cây
3.4 Cây nhị phân
3.5 Cây tìm kiếm nhị phân
3.6 Cây cân bằng
Chương 3. Cây 80
40
- 8/4/2020
3.1 Định nghĩa và khái niệm cơ bản
3.1.1 Định nghĩa
3.1.2 Các khái niệm cơ bản về cây
Chương 3. Cây 81
3.1.1 Định nghĩa
Cây: (Tree)
❖ Cây T là một bộ , trong
đó:
V: Tập hữu hạn các phần tử (nút)
E: Tập hữu hạn(cung) thể hiện mối
quan hệ phân cấp là quan hệ “
cha – con”.
Kí hiệu: T=
❖ Nút gốc (root): là nút không
phải là con của bất cứ nút nào
❖ Cây rỗng (null tree): là cây
không có nút nào
Chương 3. Cây 82
41
- 8/4/2020
3.1.1 Định nghĩa
Các ví dụ về cấu trúc cây
❖Mục lục của một cuốn sách
❖Cấu trúc thư mục trên đĩa máy tính.
❖Sơ đồ nhân sự của tổ chức
❖Cây phả hệ
❖Dùng cây để biểu diễn biểu thức số học, chẳng
hạn: ( a+b) x (c-d/e)
Chương 3. Cây 83
3.1.1 Định nghĩa
x
-
+
c /
a b
d e
Chương 3. Cây 84
42
- 8/4/2020
3.1.2 Các khái niệm cơ bản về cây
❖Số các con của một nút gọi là cấp/bậc (degree) của nút
đó
▪ Nút có bậc bằng 0 gọi là nút lá (leaf)
▪ Các nút không phải nút lá gọi là nút nhánh ( branch)
▪ Bậc cao nhất có trong các nút của một cây gọi là bậc của cây
đó.
❖Mức-Level: Gốc của cây có mức 1, nếu một nút có mức i
thì các nút con của nút đó có mức i+1.
▪ Chiều cao (height) của cây là số mức lớn nhất của các nút có
trên cây đó
Chương 3. Cây 85
3.1.2 Các khái niệm cơ bản về cây
❖Cây có thứ tự: là cây mà có xét đến thứ tự giữa các con
của một nút
▪ Con trưởng/con cực trái của một nút: là con thứ nhất trong
quan hệ thứ tự giữa các nút cùng cha
▪ Em liền kề của một nút: là nút đứng ngay sau trong quan hệ thứ
tự giữa các nút cùng cha
❖Cây có nhãn: mỗi nút của cây được gán một nhãn. Nhãn
có thể là kiểu số nguyên, kiểu ký tự hay một kiểu dữ liệu
khác khác tạp hơn
❖Rừng:Tập hợp hữu hạn các cây phân biệt gọi là một rừng
(forest).
Chương 3. Cây 86
43
- 8/4/2020
3.1.2 Các khái niệm cơ bản về cây
A 1
B C D 2
E F G H I 3
J K 4
Chương 3. Cây 87
3.2 Một số phép toán trên cây
❖Khởi tạo cây rỗng: void Initialize(TypeTree T);
❖Xác định nút gốc: Ref Root(TypeTree T);
❖Xác định nút cha của một nút:
Ref Parent(TypeTree T, TypeNode V);
❖Tìm con trưởng của một nút
Ref EldestChild(TypeTree T, TypeNode V);
❖Xác định em liền kề của một nút:
Ref NextSibling(TypeTree T,TypeNode V);
❖Duyệt cây: truy cập mọi nút để thực hiện một xử lý nào
đó →không sót, không lặp:
Void Traverse(TypeTree T);
Chương 3. Cây 88
44
- 8/4/2020
3.3 Cài đặt cây
3.3.1 Cài đặt cây bởi mảng
3.3.2 Cài đặt cây bởi danh sách các con
3.3.3 Cài đặt cây bằng con trỏ
3.3.4 Ứng dụng
Chương 3. Cây 89
3.3.1 Cài đặt cây bởi mảng
❖ Quy ước:
❖ Cho cây T có n nút
❖ Gán tên cho các nút lần lượt là 0, 1, 2, .., n-1.
❖ Dùng một mảng một chiều a để lưu trữ cây bằng cách cho a[i] = j
với j là nút cha của nút i. Nếu i là nút gốc ta cho a[i] = -1 vì nút
gốc không có cha
❖ Nếu cây T là cây có nhãn, ta có thể dùng thêm một mảng một
chiều L chứa các nhãn của cây bằng cách cho L[i] = x với x là
nhãn của nút i, hoặc khai báo a là một struct có ba trường: trường
Parent là một mảng giữ chỉ số nút cha; trường Data là một mảng
giữ nhãn của nút và một trường MaxNode giữ số nút hiện tại đang
có trên cây
Chương 3. Cây 90
45
- 8/4/2020
3.3.1 Cài đặt cây bởi mảng
❖Nhận xét
▪ Hàm PARENT(n,T) tốn chỉ một hằng thời gian
▪ Các hàm đòi hỏi thông tin về các con không làm việc tốt (vì phải tốn vòng lặp
để dò tìm), vd: tìm nút con trái nhất của nút i là không thể xác định được.
❖Khắc phục bằng qui ước:
▪ Đánh số theo thứ tự tăng dần bắt đầu tại nút gốc.
▪ Nút cha được đánh số trước các nút con.
▪ Các nút con cùng một nút cha được đánh số lần lượt từ trái sang phải
→Cách lưu trữ này chỉ phù hợp với cây mà các nút của cây khác nhau từng đôi một
Chương 3. Cây 91
3.3.1 Cài đặt cây bởi mảng
❖Ví dụ 0
A
1
B 2 C
3
D 4 E 5 I 6 J
F G H
7
8 9
A B C D E I J F G H … Nhãn của các nút trên cây
-1 0 0 1 1 2 2 4 4 4 … Cha của nút trên cây
0 1 2 3 4 5 6 7 8 9 … Chỉ số của mảng
Chương 3. Cây 92
46
- 8/4/2020
3.3.1 Cài đặt cây bởi mảng
❖ Khai báo cấu trúc dữ liệu
#define MAXSIZE ... /* chỉ số tối đa của mảng */
typedef ... DataType;
typedef int Node;
typedef struct
{
DataType Data[MAXSIZE];/* Nhãn của nút trong cây */
Node Parent[MAXSIZE]; /* Cha của các nút trong cây */
int MaxNode; /* Số nút thực sự trong cây */
} Tree;
Chương 3. Cây 93
3.3.1 Cài đặt cây bởi mảng
❖Cài đặt các phép toán
(yêu cầu sv viết chương trình)
Chương 3. Cây 94
47
- 8/4/2020
3.3.2 Cài đặt cây bởi danh sách các con
❖Quy ước:
▪ Mỗi nút có một danh sách các nút con.
▪ Vì số nút con của một nút là không biết trước nên dùng danh
sách liên kết.
❖Khai báo cấu trúc dữ liệu
typedef struct node
{
DataType Item;
node *next;
}
typedef node *childlist;
childlist tree[maxsize];
❖Ví dụ:
Chương 3. Cây 95
3.3.2 Cài đặt cây bởi danh sách các con
Chương 3. Cây 96
48
- 8/4/2020
3.3.2 Cài đặt cây bởi danh sách các con
❖Nhận xét
❖Các hàm đòi hỏi thông tin về các con làm việc rất
thuận lợi, nhưng hàm PARENT lại không làm
việc tốt.
❖Ví dụ: tìm nút cha của nút G đòi hỏi ta phải duyệt
tất cả các danh sách chứa các nút con.
Chương 3. Cây 97
3.4 Cây nhị phân (Binary Tree)
3.4.1 Khái niệm
3.4.2 Biểu diễn và các thao tác trên cây
3.4.3 Ứng dụng
Chương 3. Cây 98
49
- 8/4/2020
3.4.1 Khái niệm
❖Cây nhị phân là cây mà mỗi đỉnh có tối đa 2 cây con
❖Cây nhị phân suy biến: cây lệch trái, cây lệch phải,
cây dích dắc
1 1
1
2 2
2
3 3
3
4 4
4
5 5 5
Chương 3. Cây 99
3.4.1 Khái niệm
❖Cây nhị phân hoàn chỉnh(Perfect/Full binary
tree): Là cây nhị phân mà mọi nút đều có đủ hai
con, trừ những nút ở mức cao nhất đều là nút lá
(không có con)
Chương 3. Cây 100
50
- 8/4/2020
3.4.1 Khái niệm
❖Cây nhị phân đầy đủ ( Complete Binary tree): là cây nhị
phân mà nếu liệt kê các nút theo trình tự từ mức thấp đến
mức cao, ở mỗi mức thì theo trình tự từ trái sang phải ta
sẽ được một dãy liên tục không khuyết nút nào. (cây đầy
đủ trái)
Chương 3. Cây 101
3.4.2 Biểu diễn và các phép toán trên cây
❖Biểu diễn bằng mảng
▪ Đánh số thứ tự các nút theo thứ tự “ trên –
dưới” và “trái – phải”.
▪ Với nút i thì
• nút con trái của nó 2i và nút con phải là 2i+1.
• Nút cha là [i/2].
Chương 3. Cây 102
51
- 8/4/2020
3.4.2 Biểu diễn và các phép toán trên cây
❖Ví dụ
A 1 1 2 3 4 5 6 7
A B E C D F G
2 B E 3
C D F G
4 5 6 7
Chương 3. Cây 103
3.4.2 Biểu diễn và các phép toán trên cây
❖Ưu điểm:
▪ Cấu trúc mảng tạo thuận lợi khi triển khai các phép
toán.
▪ Truy cập nhanh chóng vào bất cứ nút nào, chi phí truy
cập là đồng đều cho mọi nút. (từ con→cha và ngược
lại đều dễ dàng)
❖Nhược điểm:
▪ Lãng phí bộ nhớ nếu cây gầy, khuyết nhiều nút
Chương 3. Cây 104
52
- 8/4/2020
3.4.2 Biểu diễn và các phép toán trên cây
❖Biểu diễn bằng danh sách liên kết
❖Quy ước: Mỗi nút là một bản ghi bao gồm:
▪ Trường Data lưu giá trị
▪ Trường Left chứa liên kết trỏ tới nút con trái hoặc Null.
▪ Trường Right chứa liên kết trỏ tới nút con phải hoặc
Null.
→ Nút gốc sẽ là nút đầu tiên của danh sách móc nối, các
nút lá có trường Left và Right đều chứa giá trị Null.
Chương 3. Cây 105
3.4.2 Biểu diễn và các phép toán trên cây
Chương 3. Cây 106
53
- 8/4/2020
3.4.2 Biểu diễn và các phép toán trên cây
❖Khai báo cấu trúc dữ liệu
typedef struct node
{
int data;
struct node *left;
struct node *right;
}node;
typdef struct node *btree;
Chương 3. Cây 107
3.4.2 Biểu diễn và các phép toán trên cây
❖Duyệt cây nhị phân: là thực hiện một thao tác xử lý
phần dữ liệu trong mọi nút đúng một lần.
❖Quy tắc duyệt: nút nào cũng được ‘thăm’ và mỗi nút
được ‘thăm’ đúng một lần.
❖Cách duyệt: dựa theo thứ tự duyệt của nút gốc, cây con
trái và cây con phải. Phép duyệt được thực hiện một cách
đệ quy.
▪ Duyệt theo thứ tự trước (preorder traversal)
▪ Duyệt theo thứ tự giữa (inorder traversal)
▪ Duyệt theo thứ tự sau (postorder traversal)
Chương 3. Cây 108
54
- 8/4/2020
3.4.2 Biểu diễn và các phép toán trên cây
❖Duyệt theo thứ tự trước
▪ Thăm nút → xử lý dữ liệu
▪ Duyệt cây con trái theo thứ tự trước
▪ Duyệt cây con phải theo thứ tự trước
Thứ tự duyệt: abdce
Chương 3. Cây 109
3.4.2 Biểu diễn và các phép toán trên cây
❖Duyệt theo thứ tự sau:
▪ Duyệt cây con trái theo thứ tự
▪ Duyệt cây con phải theo thứ tự trước
▪ Thăm nút
Thứ tự duyệt: dbeca
Chương 3. Cây 110
55
- 8/4/2020
3.4.2 Biểu diễn và các phép toán trên cây
❖Duyệt theo thứ tự giữa
▪ Duyệt cây con trái theo thứ tự giữa
▪ Thăm nút
▪ Duyệt cây con phải theo thứ tự giưa
Thứ tự duyệt: bdaec
Chương 3. Cây 111
3.4.2 Biểu diễn và các phép toán trên cây
❖Ví dụ:
Chương 3. Cây 112
56
- 8/4/2020
3.4.2 Biểu diễn và các phép toán trên cây
❖Cài đặt chương trình
void firstorder(btree t){ // duyệt thứ tự trước
if (t==NULL) exit(0);
else
{
coutleft);
cout
- 8/4/2020
3.4.3 Ứng dụng
❖Ứng dụng của phép duyệt cây
▪ Tính chiều cao của cây (yêu cầu viết hàm)
▪ Tính số nút/số nút lá của cây (yêu cầu viết hàm)
▪ Tính kích thước của cây
▪ Sao chép cây
▪ …
❖ứng dụng của cây nhị phân
▪ Biều diễn biểu thức: Tính giá trị biểu thức, tính đạo hàm
▪ Cây quyết định
Chương 3. Cây 115
3.5 Cây nhị phân tìm kiếm
3.5.1 Khái niệm
3.5.2 Biểu diễn và các thao tác
3.5.3 Ứng dụng
Chương 3. Cây 116
58
- 8/4/2020
3.5.1 Khái niệm
❖Cây nhị phân tìm kiếm là một cây nhị phân mà mỗi nút
của nó đều được gán một giá trị khóa và mọi nút trên cây
phải thỏa mãn:
❖Giá trị của các nút của cây con trái nhỏ hơn giá trị của
nút gốc;
❖Giá trị của các nút cây con phải lớn hơn giá trị của nút
gốc;
❖Cây con trái và cây con phải cũng là cây tìm kiếm nhị
phân.
❖Các giá trị khóa là khác nhau.
Chương 3. Cây 117
3.5.1 Khái niệm
❖Ví dụ
Chương 3. Cây 118
59
nguon tai.lieu . vn
