Giáo trình Cấu trúc dữ liệu và giải thuật (Phần 2)
CHƢƠNG 6 : CÂY
6.1. ĐỊNH NGHĨA VÀ KHÁI NIỆM
a. Định nghĩa
Một cây là một tập hữu hạn các nút trong đó có một nút đặc biệt gọi là gốc
(root). Giữa các nút có một quan hệ phân cấp gọi là "quan hệ cha con ".
Có thể định nghĩa cây là một cách đệ quy như sau :
1. Một nút là một cây. Nút đó cũng là gốc của cây ấy
5. Nút 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 gốc,
thì một cây mới T sẽ được tạo lập bằng cách cho nút n trở thành cha của nút
n1 , n2 , .., nk; nghĩa là trên gốc lúc đó n1 , n2, .., nk là con của nút n.
Để tiện , 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)
Ví dụ: Mục lục của một cuốn sách của một chương trong sách có cấu trúc của
một cây. Chẳng hạn, mục lục của chương 6 này:
Chương 6 : Cây
6.1 Định nghĩa và các khái niệm
6.2 Cây nhị phân
6.2.1
6.2.2
6.2.3
Định nghĩa và tính chất
Biểu diễn cây nhị phân
Phép duyệt cây nhị phân
Cây nhị phân nối vòng
6.2.4
6.3 Cây tổng quát
6.3.1
Biểu diễn cây tổng quát
Phép duyệt cây tổng quát
6.3.2
6.4 áp dụng
6.4.1
Cây biểu diễn biểu thức
Cây biểu diễn các tập
Các quyết định
6.4.2
6.4.3
Ta có thể biểu diễn bởi một cây có dạng như sau :
6.1
6.2
6.3
6.4
6.2.1 6.2.2 6.2.3 6.2.4 6.3.1 6.3.2 6.4.1 6.4.2
6.4.3
Hình 6.1
* Biểu thức số học x + y * (z- t ) + u/v có thể biểu diễn dưới dạng cây như hình
6.2
+
* Các tập bao nhau có thể biểu diễn như hình 6.4
Đối với cây, chẳng hạn xét cây ở hình 6.1
Nút A được gọi là gốc của cây
+
/
x
*
u
v
y
-
B, C, D là gốc của cây con của A
t
z
A là cha của B, C, D;
B, C, D là con của A
b. Các khái niệm
Hình 6.2
* Số các con của nút gọi là cấp (degree) của nút đó. Ví dụ cấp của A là 3, cấp
của H là 2
a
b
d
f
g
e
i
c
Hình 6.3
* Nút có cấp bằng không gọi là lá (deaf) hay nút tận cùng (dermimal noder ). Ví
dụ nút E, C, K, L v v … Nút không là lá được gọi là nút nhánh ( branch node)
Cấp cao nhất của nút trên cây gọi là cấp của cây đó. Cây ở hình 6.4 là cây cấp 3
A
C
B
D
H
I
E
F
G
M
K
Hình 6.4
* Gốc của cây có số mức (level ) là 1. Nếu nút cha có số mức là i thì nút con có
số mức là i + 1. Ví dụ: nút A có số mức là 1
D có số mức là 2
G có số mức là 3
J có số mức là 4
* Chiều cao (height) hay chiều sâu (depth) của một cây là số mức lớn nhất của
nút có trên cây đó.
Cây chiều hình 6.2 có chiều cao là 5
Cây chiều hình 6.4 có chiều cao là 4
Nếu n1 , n2, ….nk là dãy các nút mà ni là cha của ni + 1 với 1
i < k, thì dãy đó gọi
là đường đi (path) từ n1 tới nk . Độ dài của đường đi (path length) bằng các nút
trên đường đi trừ đi 1 . Ví dụ trên cây hình 6.4 độ dài đường đi từ A tới G là 2, từ
A tới K là 3
* Nếu thứ tự các cây con của một nút được trọng thì cây đang xét là cây có thứ
tự (ordered tree), ngược lại là cây không có thứ tự (unordered tree). Thường thứ
tự các cây con của một nút được đặt từ trái sang phải
Hình 6.5 cho ta hai "cây có thứ tự " khác nhau:
A
A
B
C
C
B
Hình 6.5
Đối với cây, từ quan hệ cha con người ta có thể mở rộng thêm các quan hệ
khác phỏng theo các quan hệ như trong gia tộc.
* Nếu có một tập hữu hạn các cây phân biệt thì ta gọi tập đó là rừng (forest)
Khái niệm về rừng ở đây phải hiểu theo cách riêng vì : có một cây, nếu ta bỏ
nút gốc đi ta sẽ có một rừng! Như ở hình 6.4 nếu bỏ nút gốc A đi, ta sẽ có một
rừng gồm 3 cây
6.2. CÂY NHỊ PHÂN
6.2.1. Định nghĩa và tính chất
a. Định nghĩa
Cây nhị phân là một dạng quan trọng của cấu trúc cây. Nó có đặc điểm là :
mọi nút trên cây chỉ có tối đa là hai con. Đối với cây con của một nút người ta
cũng phân biệt cây con trái (left subtree) và cây con phải (right subtree). Như vậy
cây nhị phân là cây có thứ tự
Ví dụ : cây ở hình 6.2 là cây nhị phân. Các cây nhị phân sau đây là khác nhau.
Nhưng nếu coi là cây thì chúng chỉ là một ( hình 6.6)
B
B
B
Hình 6.6
Cũng cần chú ý tới một số dạng đặc biệt của cây nhị phân, ví dụ:
a)
c)
d)
b)
A
A
C
B
C
B
D
E
G
F
E
D
G
F
H
K
Hình 6.7
Các cây a) b) c) được gọi là cây nhị phân suy biến (degenerate binary tree) vì
thực chất nó có dạng của một danh sách tuyến tính
Riêng cây a) được gọi là cây lệch trái
Riêng cây b) được gọi là cây lệch phải
Riêng cây c)được gọi là cây lệch zic – zắc
Cây c) và f) được gọi là cây nhị phân hoàn chỉnh (complete binary tree) . Ở đây
ta thấy : các nút ứng với các mức trừ mức cuối cùng đều đạt tối đa. Riêng f ) có
các nút tối đa ở cả mọi mức nên còn được gọi là cây nhị phân đầy đủ (full binary
tree). Cây nhị phân đầy đủ là một trường hợp đặc biệt của cây nhị phân hoàn
chỉnh
Ta thấy ngay: trong các cây nhị phân cùng có số lượng nút như nhau thì cây
nhị phân suy biến có chiều cao lớn nhất, còn cây nhị phân hoàn chỉnh thì có
chiều cao nhỏ nhất, loại cây này cũng là loại cây có dạng “cân đối” nhất
Tất cả các khái niệm đã nêu ở 6.1 đều có thể áp dụng vào cây nhị phân
b. Tính chất
1) Số lượng tối đa các nút ở mức i trên một cây nhị phân là
2i – 1 (i
1)
2) Số lượng tối đa các nút trên một cây nhị phân có chiều cao h là
2h – 1 (h
1)
* Chứng minh
Sẽ được chứng minh bằng qui nạp : Ta biết :
Ở mức 1 : i = 1, cây nhị phân có tối đa 1 = 20 nút
Ở mức 2 : i = 2, cây nhị phân có tối đa 2 = 21 nút
Giả sử kết quả đúng với mức i-1, nghĩa là mức này cây nhị phân có tối đa là 2i-2
nút. Mỗi nút i-1 sẽ có tối đa hai con vậy 2i – 2 nút ở mức i-1 sẽ cho :
2i – 2 x 2 = 2i-1 nút tối đa ở mức i
Bổ đề 1) đã được chứng minh
3) Ta biết rằng chiều cao cây là số mức lớn nhất có trên cây. Theo 1) ta suy ra số
nút tối đa có trên cây nhị phân với chiều cao h là :
20 + 21 +22 + ….+ 2h-1 = 2h – 1
* Từ kết quả này ta có thể suy ra:
Nếu cây nhị phân hoàn chỉnh có n nút thì chiều cao củat nó là :
h = [ log2 (n+1) ]
(Ta qui ước x là số nguyên trên của x
x là số nguyên dưới của x
nghĩa là x
x x )
6.2.2. Biểu diễn cây nhị phân
1) Lƣu trữ kế tiếp
Nếu có một cây nhị phân hoàn chỉnh đầy đủ, ta có thể dễ dàng đá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
và từ trái sang phải đối với các nút ở mỗi mức.
Ví dụ với hình 6.7 cây f) có thể đánh số như sau :
1
A
C
B
2
3
5
4
6
7
D
E
G
F
Hình 6.8
Ta thấy ngay :
Con của nút thứ i là các nút thứ 2i và 2i + 1 hoặc
Cha của nút thứ j là [ j/2 ]
Nếu như vậy thì ta có thể lưu trữ câ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[ i]. Đó chính là cách lưu trữ kế tiếp đối với cây
nhị phân. Với cách lưu trữ này nếu biết được địa chỉ nút cha sẽ tính được địa chỉ
nút con và ngược lại.
Như với cây đầy đủ nêu trên thì hình ảnh lưu trữ sẽ như sau:
A
B
C
D
E
F
G
V[1] V[2] V[3] V[4] V[5] V[6] V[7]
Tất nhiên nếu cây nhị phân không đầy đủ thì cách lưu trữ này không thích hợp
vì sẽ gây ra lãng phí do có nhiều phần tử nhớ bỏ trống (ứng với cây con rỗng ) .
Chẳng hạn, đối với cây lệch trái ở hình 6.7 a thì phải lưu trữ bằng một vectơ gồm
31 phần tử mà chỉ có 5 phần tử khác rỗng, hình ảnh miền nhớ lưu trữ nó như sau:
A B C D E
( chỉ chỗ trống )
...
Ngoài ra nếu cây luôn biến động nghĩa là có phép bổ sung, loại bỏ các nút
thường xuyên tác động, thì cách lưu trữ này tất không tránh được các nhược điểm
như đã nêu ở chương 4
Cách lưu trữ móc nối sau đây vừa khắc phục được nhược điểm này, vừa phản
ánh được dạng tự nhiên của cây
2) Lƣu trữ móc nối
Trong cách lưu trữ này, mỗi nút ứng với một phần tử nhớ có qui cách như sau:
LPTR
INFO
RPTR
- Trường INFO ứng với thông tin (dữ liệu) của nút
- Trường LPTR ứng với con trỏ, trỏ tới cây con trái của nút đó
- Trường RPTR ứng với con trỏ, trỏ tới cây con phải của nút đó
Ví dụ : cây nhị phân hình 6.9 có dạng lưu trữ móc nối như ở hình 6.10
A
B
C
D
E
F
G
H
I
Hình 6.9
A
B
C
D
E
F
G
H
I
Hình 6.10
Để có thể truy nhập vào các nút trên cây cần có một con trỏ T, trỏ tới nút gốc của
cây đó. Người ta qui ước: nếu cây nhị phân rỗng thì T = null
Với cách biểu diễn này từ nút cha có thể truy nhập vào nút con dễ dàng, nhưng
ngược lại thì không làm được
6.2.3. Phép duyệt cây nhị phân
1) Khái niệm
Thông thường ta hay phải thực hiện các phép xử lí trên mỗi nút của cây theo
một thứ tự nào đó.
Ví dụ: đối với cây biểu diễn biểu thức số học nêu ở hình 6.2, để xác định giá trị
của biểu thức ta sẽ phải xử lí ở mỗi nút trên cây như sau: nếu là nút biểu diễn
toán hạng ta sẽ xác định giá trị của toán hạng đó, nếu là nút biểu diễn dấu phép
toán ta sẽ áp đặt phép toán đó lên giá trị của các cây con của nút ấy. Nhưng ta
không thể thực hiện phép toán này, nếu như các cây con chưa được xử lí. Từ đó
ta thấy ngay: thứ tự xử lí nút trên cây là rất quan trọng
Phép xử lí các nút trên cây- mà ta sẽ gọi
1
3
chung là phép thăm (visit ) các nút một
cách hệ thống, sao cho mỗi nút chỉ được
thăm một lần, gọi là phép duyệt cây
Nếu hình dung một nút với hai con, ta
thấy khi đi qua nút ấy và các con nó theo
đường mũi tên như ở hình 6.11, ta sẽ gặp
nút ấy tới ba lần
2
Hình 6.11
Từ đấy cũng hình thành ba phép duyệt
khác nhau đối với cây nhị phân
2) Các phép duyệt cây đệ quy theo thứ tự trƣớc, giữa, sau
a) Duyệt theo thứ tự trƣớc (preorder traversal )
-
-
-
Thăm gốc
Duyệt cây con trái theo thứ tự trước
Duyệt cây con phải theo thứ tự trước
b) Duyệt theo thứ tự giữa ( inorder traversal )
-
-
-
Duyệt cây con trái theo thứ tự giữa
Thăm gốc
Duyệt cây con phải theo thứ tự giữa
c) Duyệt theo thứ tự sau (postorder traversal )
- Duyệt cây con trái theo thứ tự sau
- Duyệt cây con phải theo thứ tự sau
- Thăm gốc
Chú ý rằng: Khi gặp cây rỗng thì "thăm " nghĩa là " không làm gì "
Với cây nhị phân ở hình 6.8, dãy các tên ứng với nút được thăm trong các phép
duyệt sẽ là :
a) Theo thứ tự trước
b) Theo thứ tự giữa
c) Theo thứ tự sau
A B D C E G F H I
D B A E G C H F I
D B G E H I F C A
Với cây nhị phân ở hình 6.2, ta lại có:
a) Theo thứ tự trước
b) Theo thứ tự giữa
c) Theo thứ tự giữa
+ + x * y - z t / u v
x + y * z - t + u / v
x y z t - * + u v / +
Để ý ta thấy: a) chính là dạng biểu thức tiền tố (prefix)
c) là dạng hậu tố (posfix)
còn b) là dạng trung tố (infix)
Như vậy các phép duyệt nêu trên đối với cây nhị phân biểu diễn biểu thức số
học sẽ cho ta các dạng kí pháp Ba Lan của biểu thức số học.
Nếu viết dưới dạng thủ tục đệ quy thì các giải thuật của các phép duyệt cây nhị
phân sẽ như sau :
Procedure PREORDER (T)
{ Thủ tục đệ quy duyệt cây nhị phân có nút gốc trỏ bởi T theo thứ tự trước}
Begin
if T
null then
Begin
write (INFO(T)) ;
PREORDER (LPTR(T)) ;
PREORDER (RPTR(T))
End ;
End;
Procedure INORDER (T)
{ Thủ tục đệ quy duyệt cây nhị phân có nút gốc trỏ bởi T theo thứ tự giữa}
Begin
if T
Begin
INORDER (LPTR(T)) ;
null then
write (INFO(T)) ;
INORDER (RPTR(T))
End ;
End;
Procedure POSTORDER (T)
{ Thủ tục đệ quy duyệt cây nhị phân có nút gốc trỏ bởi T theo thứ tự sau}
Begin
if T
Begin
POSTORDER (LPTR(T)) ;
null then
POSTORDER (RPTR(T)) ;
write (INFO(T)) ;
End ;
End;
3) Các phép duyệt cây không đệ quy theo thứ tự trƣớc, giữa, sau
Procedure PREORDER (T )
{ Thủ tục không đệ quy duyệt cây nhị phân có nút gốc trỏ bởi T theo thứ tự
trước
Sử dụng một Stack S để nạp vào đó địa chỉ con phải của các nút trên đường đi
xuống và lấy các địa chỉ ra để xác định đường đi lên. }
Begin
if T = null then
Begin
write ( ' cây rỗng ') ;
return;
End ;
else
Begin
TOP := 0;
PUSH (S, TOP, T );
While TOP > 0 do
Begin
P : = POP (S, TOP);
While P
Begin
null do
Write (INFO(P));
if RPTR (P) null then
PUSH (S, TOP, RPTR (P)) ;
P : = LPTR(P);
End;
End;
End;
End;
Procedure INORDER (T )
{ Thủ tục không đệ quy duyệt cây nhị phân có nút gốc trỏ bởi T theo thứ tự
giữa}
Begin
if T = null then
Begin
write ( ' cây rỗng ') ;
return;
End ;
else
Begin
TOP := 0;
P := T;
Repeat
While P
Begin
Push(S, TOP, P);
null do
P := LPTR(P);
End;
if TOP > 0 then
Begin
P : = POP (S, TOP);
write(INFO(P));
P := RPTR(P);
continue := true;
End
else continue := false;
Until not continue;
End;
End;
Procedure POSTORDER (T )
{ Thủ tục không đệ quy duyệt cây nhị phân có nút gốc trỏ bởi T theo thứ tự sau
Trong phép duyệt sau, nút gốc chỉ được thăm khi đã duyệt xong hai con của nó,
như vậy chỉ khi đi lên từ con phải, gốc mới được thăm chứ nó không được thăm
khi đi từ con trái lên. Để phân biệt việc vừa đi lên từ con nào, ta đưa dấu – vào
địa chỉ lưu trữ trong Stack để đánh dấu cho lần đi lên từ con phải}
Begin
if T = null then
Begin
write ( ' cây rỗng ') ;
return;
End ;
else Begin
TOP := 0;
P := T;
While True do
Begin
While P
Begin
null do
PUSH (S, TOP, P);
P : = LPTR(P);
End;
While S[TOP] < 0 do
Begin
P := POP(S, TOP);
Write(INFO(P));
If TOP = 0 then return
End;
P := RPTR(S[TOP]);
S[TOP] := - S[TOP];
End;
End;
6.3. CÂY NHỊ PHÂN NỐI VÕNG
6.3.1. Khái niệm và lƣu trữ
Nếu để ý đến dạng biểu diễn móc nối của cây nhị phân, ta thấy có khá nhiều
mối nối không. Cụ thể nếu cây có n nút thì có n + 1 mối nối không. Vì vậy, một
vấn đề đặt ra là làm thế nào để tận dụng các mối nối này. Một trong các cách tận
dụng các mối nối này đã được A. J. Perlis và C. Thomtor nêu ra:
“Thay mối nối không bằng mối nối trỏ đến một nút qui định để tạo điều kiện
thuận lợi cho phép duyệt cây”.
Loại mối nối này ta gọi là mối nối vòng và dạng biểu diễn cây nhị phân như
thế được gọi là cây nhị phân nối vòng.
Để nhằm mục đích giúp cho phép duyệt giữa được thuận lợi, Perlis đưa ra qui
ước: Đối với nút P nào đó trên cây, nếu LPTR(P) = null thì thay LPTR(P) bằng
+
+P, nếu RPTR(P) = null thì thay RPTR(P) bẳng P+. Với P là con trỏ trỏ tới nút
đứng trước P trong thứ tự giữa, còn P+ là con trỏ trỏ tới nút đứng sau P trong thứ
tự giữa.
Với cây 6.10 thì dạng biểu diễn nối vòng sẽ như sau:
T
A
B
C
D
E
F
G
H
I
Hình 6.12
Rõ ràng là trong máy thì không thể phân biệt được mối nối thẳng và nối mối
vòng giống như trên hình vẽ . Vì vậy trong qui cách của một nút phải thêm vào
hai trường bít : LBIT và RBIT đánh dấu hai loại mối nối đó. Nghĩa là qui cách
một nút sẽ có dạng:
LBIT
LPTR
INFO
RPTR
RBIT
Nếu LPTR(P)
null thì LBIT(P) = 0
LPTR (P) = null thì LBIT (P) = 1 (ứng với mối nối vòng )
Đối với RBIT cũng tương tự
Ta cũng thấy: với cây như ở hình 6.12 mối nối vòng trái của D ( ta gọi là nút
cực trái của cây T ) và nối vòng phải của nút I (nút cực phải của cây T ) còn chưa
được xác định vì trong thứ tự giữa không có nút trước nút D và nút sau nút I .
Tuy nhiên để cách biểu diễn được nhất quán đối với mọi nút, mà cũng không gây
ra điều gì phức tạp, người ta qui ước đưa thêm vào nút "đầu cây". Trong cách
biểu diễn này cây T được coi như con trái của nút "đầu cây " ấy và nối mối phải
của nút đầu cây thì luôn trỏ tới chính nó
Như vậy cây ở hình 6.12 sẽ có dạng như ở hình 6.13
HEAD
T
A
B
C
D
E
F
G
H
I
Hình 6.13
HEAD là con trỏ, trỏ tới nút đầu cây
Trường hợp cây rỗng thì nút đầu cây có dạng:
HEAD
nghĩa là :
RPTR(HEAD) = HEAD
RBIT(HEAD) = 0
LPTR(HEAD) = HEAD
LBIT (HEAD) = 1
Với cấu trúc cây nối vòng như thế này giải thuật tìm nút đứng trước một nút P,
hoặc sau một nút P, trong thứ tự giữa, trở nên khá đơn giản và việc đưa thêm nút
đầu cây với qui ước như trên là hoàn toàn phù hợp
Phép duyệt cây theo thứ tự giữa bây giờ chỉ là phép gọi liên tiếp thủ tục INS(P)
bắt đầu từ nút đầu cây, trỏ bởi HEAD
6.3.2. Các giải thuật
1) Tìm địa chỉ một nút đứng sau một nút trong thứ tự giữa
Function INS (P)
{Cho P là con trỏ trỏ tới một nút trong nối vòng. Giải thuật này cho ta địa chỉ
Q là con trỏ trỏ tới nút sau P trong thứ tự giữa}
1. { Nối phải là mối nối vòng }
Q : = RPTR(P) ;
if RBIT (P) = 1 then return (Q) ;
2. {Tìm đến nút cực trái của con phải }
while LBIT (Q)
1 do Q:= LPTR(Q)
3. return (Q);
2) Tìm địa chỉ một nút đứng trƣớc một nút trong thứ tự giữa
Function INP(P)
{Cho P là con trỏ trỏ tới một nút trong nối vòng. Giải thuật này cho ta địa chỉ
Q là con trỏ trỏ tới nút trước P trong thứ tự giữa}
1. Q:= LPTR(P)
if LBIT (P) = 1 then return (Q)
2. while RBIT(Q)
3. return (Q)
1 do Q := RPTR(Q) ;
3) Duyệt cây theo thứ tự giữa
Procedure TINORDER (HEAD)
{Giải thuật duyệt cây nhị phân nối vòng, nút đầu trỏ bởi HEAD theo thứ tự giữa}
1. P := HEAD ;
2. while true do begin
P := INS(P) ;
if P = HEAD then return
else write (INFO(P))
end;
3. Return
4) Bổ sung một nút trở thành con trái của một nút
Procedure LEFT (P, X )
{Cho P trỏ tới một nút trên cây nối vòng, giải thuật này thực hiện bổ sung một
nút mới vào bên trái nút P, thông tin liên quan tới nút mới này hiện đặt ở X }
1. {Tạo nút mới }
Q
AVAIL ;
INFO (Q) := X ;
2. {Chỉnh lí lại các con trỏ ở P và Q}
LPTR(Q) :=LPTR(P) ; LBIT (Q) := LBIT(P) ;
LPTR(P) := Q ; RBIT(Q) : = 1 ;
3. {Dựng lại mối nói vòng ở nút đứng trước Q nếu cần }
if LBIT (Q) = 0 then begin
W : = INP (Q) ;
RPTR(W) := Q ;
RBIT (W) := 1
end
4. return
a) Trường hợp P không có con trái
P
P
Q
Q
Trước khi bổ sung
Sau khi bổ sung
b) Trường hợp P đã có con trái
P
P
Q
Q
Trước khi bổ sung
Hình 6.14
Sau khi bổ sung
5) Bổ sung một nút trở thành con phải của một nút
Procedure RIGHT (P, X )
{Cho P trỏ tới một nút trên cây nối vòng, giải thuật này thực hiện bổ sung một
nút mới vào bên phải nút P, thông tin liên quan tới nút mới này hiện đặt ở X }
1. {Tạo nút mới }
Q
AVAIL ;
INFO (Q) := X ;
2. {Chỉnh lí lại các con trỏ ở P và Q}
RPTR(Q) :=RPTR(P) ; RBIT (Q) := RBIT(P) ;
RPTR(P) := Q ; LBIT(Q) : = 1 ;
3. {Dựng lại mối nói vòng ở nút đứng trước Q nếu cần }
if RBIT (Q) = 0 then begin
W : = INS (Q) ;
LPTR(W) := Q ;
LBIT (W) := 1
end
4. return
a) Trường hợp P không có con phải
P
P
Q
Q
Trước khi bổ sung
Sau khi bổ sung
b) Trường hợp P đã có con trái
P
P
Q
Q
Trước khi bổ sung
Hình 6.15
Sau khi bổ sung
6.4. CÂY TỔNG QUÁT
6.4.1. Biểu diễn cây tổng quát
Chúng ta có thể biểu diễn cây tổng quát cấp m nào đó sử dụng cách biểu diễn
móc nối tương tự như đối với cây nhị phân. Như vậy, ứng với mỗi nút ta phải
dành ra m trường mối nối để trỏ tới các con của nút đó và như vậy số "mối nối
không " sẽ rất nhiều: nếu cây có n nút sẽ có tới n(m-1) + 1 “mối nối không” trong
số m.n mối nối. Còn nếu tuỳ theo con số của từng nút mà định ra mối nối nghĩa
là dùng nút có kích thước biến đổi thì sự tiết kiệm không gian nhớ này sẽ phải trả
giá bằng những phức tạp của quá trình xử lí trên cây.
Một trong các phương pháp khác, khá hiện thực là biểu diễn cây tổng quát
bằng cây nhị phân. Như vậy quan hệ giữa các nút trên cây tổng quát chỉ được thể
hiện qua hai đặc điểm thôi.
Điều này rõ ràng có thể đáp ứng được nếu như ta để ý rằng với bất kì một nút
nào trên cây tổng quát, nếu có thì chỉ có:
- một nút con cực trái (con cả )
- một nút em kế cận phải
Lúc đó cây nhị phân biểu diễn cây tổng quát theo hai quan hệ này được gọi là
cây nhị phân tương đương (equivalent binary tree) và cấu trúc mỗi nút trên cây
nhị phân tương đương có dạng:
CHILD
INFO
SIBLING
CHILD: là con trỏ, trỏ tới nút con cực trái
SIBLING: là con trỏ, trỏ tới nút em kế cận phải
Ví dụ: Với cây tổng quát sau:
D
Hình 6.16
Với nút B: con cực trái là E, em kế cận phải là C
Với nút D: con cực trái là H, em kế cận phải không có
Cây nhị phân tương đương tương ứng với cây ở hình 6.16 là:
Hình 6.17
Đối với rừng có thể định nghĩa phép biến đổi tổng quát đối với rừng như sau :
Nếu T1, T2, .., Tn là một rừng thì cây nhị phân tương đương biểu diễn rừng đó,
kí hiệu bởi B(T1, T2, .., Tn ) sẽ là cây:
1) rỗng, nếu n = 0
2) có gốc là gốc của T1, có cây con trái là B(T11, T12, .., T1m ) với T11, T12, .., T1m
là cây con gốc T1, có cây con phải là B(T2, .., Tn)
Ví dụ: Với rừng ở hình 6.18 thì cây nhị phân tương đương biểu diễn nó sẽ như
hình 6.19.
Hình 6.18
A
B
G
H
I
J
Hình 6.19
6.4.2. Giải thuật duyệt cây tổng quát
Phép duyệt cây tổng quát cũng được đặt ra tương tự như đối với cây nhị phân.
Tuy nhiên, có một điều cần phải xem xét thêm, khi định nghĩa phép duyệt, đó là :
1) Sự nhất quán về thứ tự các nút được thăm giữa phép duyệt cây ấy (theo định
nghĩa của phép duyệt cây tổng quát) và phép duyệt cây nhị phân tương đương
của nó (theo định nghĩa của phép duyệt cây nhị phân )
2) Sự nhất quán giữa định nghĩa phép duyệt cây tổng quát với định nghĩa phép
duyệt cây nhị phân. Vì cây nhị phân vẫn có thể được coi là cây, để duyệt theo
phép duyệt cây tổng quát.
Với quan điểm như vậy, ta sẽ xây dựng định nghĩa của phép duyệt cây tổng
quát T như sau:
a) Duyệt theo thứ tự trƣớc
1. Nếu T rỗng thì không làm gì
2. Nếu T không rỗng thì :
- Thăm gốc của T
- Duyệt các cây con thứ nhất T1 của gốc T theo thứ tự trước
- Duyệt các cây con còn lại T2, T3, .., Tk của gốc T theo thứ tự trước
b) Duyệt theo thứ tự giữa
1. Nếu T rỗng thì không làm gì
2. Nếu T không rỗng thì :
- Duyệt các cây con thứ nhất T1 của gốc T theo thứ tự giữa
- Thăm gốc của T
- Duyệt các cây con còn lại T2, T3, .., Tk của gốc T theo thứ tự giữa
b) Duyệt theo thứ tự sau
1. Nếu T rỗng thì không làm gì
2. Nếu T không rỗng thì :
- Duyệt các cây con thứ nhất T1 của gốc T theo thứ tự sau
- Duyệt các cây con còn lại T2, T3, .., Tk của gốc T theo thứ tự sau
- Thăm gốc của T
Ví dụ với cây:
D
thì dãy tên các nút được thăm sẽ là:
Thứ tự trước: A B C E H I F J D G
Thứ tự giữa: B A H E I C J F G D
Thứ tự sau: B H I E J F C G D A
E
F
G
Hình 6.20
Tải về để xem bản đầy đủ
98 trang
13520
Free
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Cấu trúc dữ liệu và giải thuật (Phần 2)", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_cau_truc_du_lieu_va_giai_thuat_phan_2.pdf
