Trong khoa học máy tính, cây là một cấu trúc dữ liệu được sử dụng rộng rãi gồm một tập hợp các nút (tiếng Anh: node) được liên kết với nhau theo quan hệ cha-con. Cây trong cấu trúc dữ liệu đầu tiên là mô phỏng (hay nói cách khác là sự sao chép) của cây (có gốc) trong lý thuyết đồ thị. Hầu như mọi khái niệm trong cây của lý thuyết đồ thị đều được thể hiện trong cấu trúc dữ liệu. Tuy nhiên cây trong cấu trúc dữ liệu đã tìm được ứng dụng phong phú và hiệu quả trong nhiều giải thuật. Khi phân tích các giải thuật trên cấu trúc dữ liệu cây, người ta vẫn thường vẽ ra các cây tương ứng trong lý thuyết đồ thị.
10 trang |
Chia sẻ: tlsuongmuoi | Lượt xem: 3640 | Lượt tải: 1
Bạn đang xem nội dung tài liệu Cấu trúc cây nhị phân, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
CHƯƠNG 3 : CẤU TRÚC CÂY
I. ĐỊNH NGHĨA VÀ CÁC KHÁI NIỆM CƠ BẢN
1. Định nghĩa
2. Các khái niệm cơ bản
3. Các phép duyệt cây quan trọng
4. Cây có nhản và cây biểu thức
5. Quy tắc biểu diễn một biểu thức toán học trên cây
II. KIỂU DỮ LIỆU TRỪU TƯỢNG CÂY
1. Các phép toán trên cây
2. Cài đặt cây
III. CÂY NHỊ PHÂN
1. Định nghĩa
2. Tính chất
3. Cài đặt cây nhị phân
IV. GIẢI THUẬT MÃ HÓA HUFFMAN
1. Đặt vấn đề
2. Giải thuật mã hóa HuffMan
V. CÂY TÌM KIẾM NHỊ PHÂN
1. Định nghĩa
2. Cài đặt cây tìm kiếm nhị phân
Cây (Trees) là một tập hợp hữu hạn các phần tử gọi là nút cây (Node), trong
đó có một nút đặc biệt gọi là nút gốc (Root). Trên tập hợp các nút này có một quan hệ
phân cấp gọi là quan hệ "cha - con".
Một nút có thể có kiểu bất ký, ta thường biểu diễn nút bằng tên nút. Tên nút có
I. ÐỊNH NGHĨA VÀ CÁC KHÁI NIỆM CƠ BẢN
1. Ðịnh nghĩa : TOP
Page 1 of 10
4/6/2007file://C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\Q4QFQA9S.htm
thể là một ký tự, một số hay một chuỗi và có thể được ghi trong một vòng tròn. Ta quy
ước biểu diễn cây như sau: Ta viết nút cha ở dòng trên, các nút con ở dòng dưới và
quan hệ "cha-con" được biểu diễn bằng một đoạn thẳng nối liền 2 nút.
Ví dụ :
Ngoài ra ta có thể định nghĩa cây một cách đệ qui như sau :
Một nút (đơn độc) là một cây và nút đó cũng là nút gốc của cây.
Nếu ta có n là một nút và T1, T2, ..., Tk là các cây với n1, n2,..., nk lần
lượt là các nút gốc của các cây con thì ta có thể xây dựng một cây mới bằng cách cho
n trở thành cha của các nút n1, n2,..., nk; Nghĩa là trên cây mới này n là nút gốc còn
các cây T1, T2, ..., Tk là các cây con của nút n.
Ðể tiện việc quản lý, người ta cho phép tồn tại một cây không có nút nào,
mà ta gọi là cây rỗng (Null tree).
Một nút đơn độc cũng là một cây.
A
B
C
D
E
F
G
2. Các khái niệm cơ bản : TOP
Page 2 of 10
4/6/2007file://C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\Q4QFQA9S.htm
Tập hợp rỗng cũng là một cây mà ta gọi là cây rỗng.
Mức của một nút :
+ Nút gốc : Mức 0.
+ Các nút cách nút gốc i cạnh được gọi là nút ở mức i.
Ví
dụ:
Cha - con: Nút A là nút cha của nút B khi nút A ở mức i và nút B ở mức
i+1. Ðồng thời có một cạnh nối giữa cặp nút A và B (ta còn gọi B là con của A).
Cha - ông (con - cháu)/ tiền bối - hậu duệ: Nếu có một đường nối từ nút A
đến nút B và mức của nút A < mức của nút B thì ta nói A là cha ông (tiền bối) của B
và B gọi là con cháu (hậu duệ) của A.
Anh em ruột: Các nút con của cùng một nút cha được gọi là các nút anh
Saïch
C1
C2
C3
§1.1
§1.2
§3.1
§3.3
§3.2
§3.2.1
§3.2.2
Mæïc 0
Mæïc 1
Mæïc 2
Mæïc 3
Page 3 of 10
4/6/2007file://C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\Q4QFQA9S.htm
em ruột.
Ðường đi: Cho một dãy các nút n1, n2,..., nk sao cho ni là nút cha của
ni+1 thì ta nói n1 ( n2 ( ...( nk là một đường đi từ nút n1 ( nk. Ðộ dài của đường đi
bằng số nút trên đường đi trừ 1 hay bằng số cạnh trên đường đi.
Nút gốc (Root): Là nút không có nút cha.
Nút lá (leaf): Là nút không có nút con.
Chiều cao của một nút: Là độ dài đường đi từ nút đó đến nút lá xa nhất.
Ðộ sâu của một nút (mức của một nút): Là chiều dài đường đi từ nút gốc
đến nút đó.
Chiều cao của một cây: Là chiều cao của nút gốc.
Bậc của một nút: Là số nút con của nút đó.
Bậc của một cây: Là bậc cao nhất của các nút trong cây.
+ Cây có bậc n được gọi là cây n - phân.
+ Rừng là một tập hợp hữu hạn các cây phân biệt.
Nếu ta phân biệt thứ tự các nút con của một cây thì ta gọi cây đó là cây có thứ
tự. Ngược lại là cây không có thứ tự.
Thứ tự của các nút trong một cây có thứ tự được quy ước từ trái sang phải
và từ trên xuống dưới.
Nếu A và B là 2 nút anh em ruột và A ở bên trái của B thì các nút con
cháu của A là nút bên trái tất cả các nút con cháu của B.
Ðể xác định nút trái (phải) của một nút n, ta vẽ một đường đi từ nút gốc
đến nút n. Nút nào nằm bên trái của đường đi thì sẽ là nút trái của nút đó, nút nào nằm
bên phải của đường đi thì sẽ là nút phải của nút đó.
1
2
3
4
5
6
8
7
9
10
Page 4 of 10
4/6/2007file://C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\Q4QFQA9S.htm
Ví dụ:
Thứ tự duyệt cây:
Duyệt cây là một quy tắc xử lý lần lượt tất cả các nút của một cây mà ở đó
mỗi nút chỉ được xử lý một lần.
Danh sách liệt kê các nút theo thứ tự xử lý được gọi là danh sách duyệt
cây.
Duyệt tiền tự (PreOrder).
Duyệt trung tự (InOrder).
Duyệt hậu tự (PostOder).
Ðịnh nghĩa các phép duyệt cây: Ta có thể định nghĩa phép duyệt cây tổng quát
bằng đệ quy như sau :
Cây rỗng : Danh sách duyệt tiền tự, trung tự, hậu tự là danh sách rỗng.
Cây có một nút : Danh sách duyệt tiền tự, trung tự, hậu tự chính là nút đó.
11
12
3. Các phép duyệt cây quan trọng : TOP
Page 5 of 10
4/6/2007file://C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\Q4QFQA9S.htm
Ví dụ : Cho một cây như hình sau :
Ta thường lưu trữ kết hợp một nhản (Label) hoặc một giá trị (value) với một nút của
cây. Như vậy, nhản của một nút không phải là tên của nút mà là giá trị được lưu tại nút
đó. Nhản của một nút còn được gọi là khóa của nút.
Ví dụ : Cây sau đây sẽ biểu diễn cho biểu thức (a + b) * (a - c)
Trong cây trên thì n1, n2,..., n7 là các tên nút còn *, +, -, a, b, c là các nhản của
nút.
4. Cây có nhản và cây biểu thức : TOP
5. Quy tắc biểu diễn một biểu thức toán học trên cây TOP
Page 6 of 10
4/6/2007file://C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\Q4QFQA9S.htm
Mỗi nút lá sẽ biểu diễn cho một toán hạng đơn độc.
Mỗi nút trung gian sẽ biểu diễn cho một toán tử. Giả sử nút n biểu diễn cho toán
tử 2 ngôi, nút con bên trái biểu diễn cho biểu thức E1, nút con bên phải biểu diễn cho
biểu thức E2 thì nút n sẽ biểu diễn cho biểu thức Eı E2
Thông thường khi chúng ta duyệt cây thì danh sách duyệt cây là một danh sách
các nhản nút. Trong trường hợp cây biểu diễn cho biểu thức toán học thì biểu thức
duyệt tiền tự cho chúng ta biểu thức tiền tố (Prefix), duyệt trung tự cho chúng ta biểu
thức trung tố (Infix) và duyệt hậu tự cho chúng ta biểu thức hậu tố (Postfix) của biểu
thức toán học ban đầu.
Ví dụ: Ðối với cây biểu thức được cho ở ví dụ trên, ta có:
+ Biểu thức tiền tố : * + a b - a c.
+ Biểu thức trung tố : a + b * a - c.
+ Biểu thức hậu tố : a b + a c - *.
Hàm Parent (n : Node; T : Tree) : Cho kết quả nút cha của nút n trên
cây T. Nếu n là nút gốc thì hàm cho kết quả là Null.
Hàm RightSibling (n : Node; T : Tree) : Cho kết quả là nút anh ruột phải
của nút n trên cây T. Nếu n không có anh ruột phải thì hàm cho kết quả là Null.
Hàm LeftMostChild (n : Node; T : Tree) : Cho kết quả là nút con trái
nhất của nút n trên cây T. Nếu n không có con trái nhất thì hàm cho kết quả là Null.
Hàm Root (T : Tree) : Cho kết quả là nút gốc của cây T. Nếu cây rỗng thì
hàm cho kết quả là Null.
Thủ tục Createi (V, T1, T2,..., Ti) : Là thủ tục tạo cây mới có nhản gốc là
V và i cây con T1, T2,..., Ti. Nếu i = 0 thì cây mới tạo chỉ có một nút đơn độc.
Hàm LabelNode(n : Node; T : Tree) : Cho nhản của nút n của cây T.
Ví dụ : Dùng các phép toán trên để viết các thủ tục duyệt cây :
Procedure PreOrder (T : Tree);
Var n, c : Node;
Begin
II. KIỂU DỮ LIỆU TRỪU TƯỢNG CÂY
1. Các phép toán trên cây TOP
Page 7 of 10
4/6/2007file://C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\Q4QFQA9S.htm
n := Root (T);
Write (LabelNode (n, T);
c := LeftMostChild (n, T);
While c Null do
Begin
PreOrder (c, T);
c := RightSibling (c, T );
End;
End;
Procedure InOrder (T : Tree);
Var n, c : Node;
Begin
n := Root (T);
c := LeftMostChild (n, T);
While c Null do
Begin
PreOrder (c, T);
Write (LabelNode (n, T);
c := RightSibling (c, T );
End;
End;
Procedure PostOrder (T : Tree);
Var n, c : Node;
Begin
n := Root (T);
Page 8 of 10
4/6/2007file://C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\Q4QFQA9S.htm
c := LeftMostChild (n, T);
While c Null do
Begin
PostOrder (c, T);
c := RightSibling (c, T );
Write (LabelNode (n, T);
End;
End;
a. Cài đặt cây bằng mảng
Cho một cây T có các nút 1, 2, 3, ... , n. Ta có thể dùng mảng A 1 chiều để 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 thì ta cho
A[i] = Null. (Cụ thể là Null = 0).
Ví dụ : Cây : Ðược biểu diễn trong mảng A như sau :
2. Cài đặt cây TOP
1
2
3
7
8
4
5
6
9
10
Page 9 of 10
4/6/2007file://C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\Q4QFQA9S.htm
Nếu cây T có nhản ta có thể dùng thêm một mảng 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 mảng A là mảng
của các Record gồm có 2 trường : Trường Parent giữ chỉ số của nút cha; trường Labels
giữ nhản của nút.
Khai báo :
Const Maxlenght = ... ;
Type ElementType = ... {Kiểu nhản} ;
Tree = Record
Parent: Array [1.. Maxlenght] of Integer;
Labels: Array [1.. Maxlenght] of ElementType;
End;
Var T:Tree;
NumNode: Integer; { Số nút tối đa trên cây }
Với cách cài đặt này hàm Parent chỉ tốn một hằng thời gian nhưng các hàm khác
thì rất khó cài đặt, để khắc phục tình trạng này người ta quy ước việc đặt tên nút
như sau :
+ Ðánh số theo thứ tự tăng dần bắt đầu từ nút gốc.
+ Tại mỗi nút thì nút cha được đánh số trước rồi lần lượt đến các nút con
từ trái sang phải.
b. Biểu diễn cây bằng danh sách các con
Một cách biểu diễn khác cũng thường được dùng là biểu diễn cây dưới
dạng mỗi nút có một danh sách các nút con. Danh sách có thể được cài đặt bằng bất
kỳ cách nào mà ta đã biết. Tuy nhiên, vì số lượng các nút con của một nút là không
biết trước nên cài đặt bằng danh sách liên kết sẽ thích hợp hơn.<span style="mso-spa
Page 10 of 10
4/6/2007file://C:\DOCUME~1\ADMINI~1\LOCALS~1\Temp\Q4QFQA9S.htm
Các file đính kèm theo tài liệu này:
- Cấu trúc cây nhị phân.pdf