Kỹ thuật lập trì nh
105
CHươNG 6 các thuật toán trên cấu trúc câY
(Tree)

Câ y là một cấ u trúc dữ liệ u rấ t thông dụng và quan trọng trong nhiề u phạ m
vi khá c nhau của kỹ thuậ t má y tí nh.
Ví dụ
: Tổ chức cá c quan hệ họ hà ng trong một gia phả , mục lục của một
cuốn sá ch, xâ y dựng cấ u trúc về cú phá p trong cá c trì nh biê n dịch.
Trong chương trì nh nà y, chúng ta khả o sá t cá c khá i niệ m cơ bả n về câ y, cá c
phép toá n trê n câ y nhị phâ n, cũng như cá c phép toá n trê n câ y nhị phâ n câ n bằ ng
( AVL tree) và ứng dụng của hai loạ i câ y nhị phâ n tì m kiế m (BST), câ y nhị phâ n
câ n bằ ng ( AVL tree).
I. Phân loại cây
:
I.1. Một số khái niệ m cơ bản
:
1. Cây
: Câ y là tậ p hợp cá c phầ n tử gọi là nút, một nút (tương tự như một
phầ n tử của d y) có thể có kiể u bấ t kỳ. Cá c nút đ ược biể u diễ n bởi 1 ký tự chữ,
một chuỗi, một số ghi trong một vòng tròn.
Một số định nghĩ a theo đệ quy
( Một nút đơn cũng chí nh là một câ y.
( Cá c nút đ ược gọi là ở cùng một câ y khi có đ ường đi giữa cá c nút nà y.
( Một câ y sẽ bao gồm một nút gốc (Root) và m câ y con, trong mỗi câ y con
lạ i có một nút gốc và m1 câ y con nhỏ hơn v.v.
( Một câ y không có một nút nà o cả gọi là câ y rỗng.
Ví dụ 1
:
A

CHệễNG II
CHệễNG III
I.1 I.2 II.1 II.3II.2
II.1.1 II.1.2Hì nh 5.2

CHươNG I
I.1
I.2

CHươNG II
II.1
II.1.1
II.1.2
II.2
II.3

CHươNG III
2. Nút cha
(Ancestor)
: Nút đứng trê n của một nút đ ược gọi là nút cha
C là nút cha của G, H
Nút con

(descendent)
: Nút đứng sau một nút khá c đ ược gọi là nút con của
nút đó.
Nút I, J, K là nút con của nút E

: là mức lớn nhấ t của cá c nút lá trong câ y.
Ví dụ
: Câ y trong hì nh 5.1 có chiề u cao là 4
7. Thứ tự của các nút

(order of nodes)
: Nế u câ y đ ược gọi là có thứ tự thì
phả i đả m bả o vị trí của cá c nút con từ trái qua phả i, tức là nế u thay đổi vị trí của
một nút con bấ t kỳ thì ta đ có một câ y mới.
Ví dụ
:
A
B C
A
C B
caõy khaực

Hì nh 5.3: Sau khi đổi vị trí của 2 nút B, C ta đ có câ y mới.
8. Chiề u dài đường đi
(Path length):
- Chiề u dà i đ ường đi của nút x: là số cá c cạ nh đi từ nút gốc đế n nút x.
Ví dụ
: Trong hì nh 5.1:
Nút gốc A có chiề u dà i đ ường đi là 1
Nút B, C, D có chiề u dà i đ ường đi là 2
Tổng quá t
: một nút tạ i mức i có chiề u dà i đ ường đi là i
- Chiề u dà i đ ường đi của câ y: là tổng của cá c chiề u dà i đường đi của tấ t cả
cá c nút trong câ y.
Ví dụ

76 8
5
9ROOT
%1%2%3%4%5%6%7%8%9
Như vậ y khi duyệ t lạ i câ y theo mức
tă ng dầ n và từ trá i qua phả i ta sẽ lạ i
có đ ược thứ tự cá c nút như trê n.
Hì nh 5.4. Câ y có thứ tự tă ng dầ n theo mức từ trá i qua phả i
II. Cây nhị phân
(Binary tree)
II.1. Định nghĩ a
:
1. Cây nhị phân là câ y có bậ c bằ ng 2, tức là số nút con tối đa của một nút
bấ t kỳ trong câ y là 2.
Câ y nhị phâ n có thể là một câ y rỗng (không có nút nà o) hoặ c câ y chỉ có
một nút, hoặ c câ y chỉ có cá c nút con bê n trá i (Left Child) hoặ c nút con bê n phả i
(Right Child) hoặ c cả hai.
Ví dụ
: Hì nh 5.4 là câ y nhị phâ n.
2. Các cây nhị phân đặc biệ t:
- Câ y nhị phâ n đúng
: Một câ y nhị phâ n đ ược gọi là câ y nhị phâ n đúng nế u
nút gốc và tấ t cả cá c nút trung gian đề u có 2 nút con.
A
B
D E
G Y

- Câ y nhị phâ n tì m kiế m
(Binary Search Tree): Một câ y nhị phâ n gọi là câ y
nhị phâ n tì m kiế m nế u và chỉ nế u đối với mọi nút của câ y thì khóa của một nút
bấ t kỳ phả i lớn hơn khóa của tấ t cả cá c nút trong câ y con bê n trá i của nó và phả i
nhỏ hơn khóa của tấ t cả cá c nút trong câ y con bê n phả i của nó.
Ví dụ
:
8
7 9
3
12
11
102
1
5
4 6
k
1
<k
1
<k
1Hì nh 5.7. Câ y nhị phâ n tì m kiế m (BST)
Kỹ thuật lập trì nh
110
- Câ y nhị phâ n câ n bằ ng (AVL): Một câ y nhị phâ n đ ược gọi là câ y nhị phâ n
câ n bằ ng nế u và chỉ nế u đối với mọi nút của câ y thì chiề u cao của câ y con bê n
trá i và chiề u cao của câ y con bê n phả i hơn kém nhau nhiề u nhấ t là 1. (Theo

: là quá trì nh đi qua cá c nút
đúng một lầ n. Khi duyệ t câ y, ta thường dùng 3 cá ch duyệ t cơ bả n sau :
' Preorder - Tiề n tự (NLR) duyệ t qua nút gốc trước, sau đó đi qua câ y con
bê n trá i lạ i á p dụng Preorder cho câ y con bê n trá i. Cuối cùng qua câ y con bê n
phả i, á p dụng Preorder cho câ y con bê n phả i.
Ví dụ
: Theo câ y nhị phâ n 5.4, ta có:
ROOT % 1 % 2 % 3 % 4 % 6 % 7 % 5 % 8 % 9
'Inorder - Trung tự (LNR) : qua câ y con bê n trá i duyệ t trước (theo thứ tự
LNR), sau đó thă m nút gốc. Cuối cùng qua câ y con bê n phả i (theo thứ tự LNR)
Ví dụ
: Theo câ y nhị phâ n 5.4, ta có:
ROOT % 2 % 1 % 6 % 4 % 7 % 3 % 8 % 5 % 9
'Postorder - Hậ u tự (LRN) : qua câ y con bê n trá i duyệ t trước (theo thứ tự
LRN), sau đó qua câ y con bê n phả i (theo thứ tự LRN). Cuối cùng thă m nút gốc.
Ví dụ
: Theo câ y nhị phâ n 5.4, ta có:
ROOT % 2 % 6 % 7 % 4 % 8 % 9 % 5 % 3 % 1
Kỹ thuật lập trì nh
111
Ghi chú : Đối với câ y ta có thể tổ chức thứ tự theo khóa là một nội dung
của nút hoặ c ta đặ t thê m 1 field gọi là khóa của nút .
II.2. Các phép toán trê n cây nhị phân
:
- Khai báo
: Để tổ chức dữ liệ u theo câ y nhị phâ n, ta có thể dùng một nội
dung của dữ liệ u để là m khóa sắ p xế p và tổ chức câ y theo nhiề u cá ch khá c nhau.
Nhưng thông thường để thuậ n tiệ n cho việ c tì m kiế m và thực hiệ n cá c phép toá n
khá c trê n câ y, người ta tạ o thê m một khóa riê ng trong cá c phầ n tử và tạ o ra câ y
nhị phâ n tì m kiế m.

}
Lời gọi hà m
: p= New_Node();
Kỹ thuật lập trì nh
112
c. Tạ o câ y BST (Create_Tree): Trong giả i thuậ t tạ o câ y BST, ta có dùng
hà m Insert.
Hà m Insert
: dùng phương phá p đệ qui thê m nút có khóa x, nội dung a và o
câ y có nút gốc root . Câ y nhị phâ n tạ o đ ược qua giả i thuậ t Create_Tree là câ y
nhị phâ n tì m kiế m (BST).
void Insert(NODEPTR root, int x, int a)
{ NODEPTR p;
if(x == root->key) // khóa bị trùng, dừng chương trì nh
{
printf("bi trung khoa, khong them nut nay duoc");
return;
}
if(x < root->info && root->left == NULL) // điề u kiệ n dừng giả i thuậ t đệ qui
{
p = New_Node(); // cấ p phá t vùng nhớ
p->key =x;
p->info = a;
p->left = NULL;
p->right = NULL;
root->left=p;
return;
}
if(x > root->info && root->right == NULL) //điề u kiệ n dừng giả i thuậ t đệ qui
{

p->key = khoa;
p->info = noidung;
p->left = NULL;
p->right = NULL;
root =p;
}
else Insert(root,khoa,noidung);
}
} while (khoa!=0); // khóa =0 thì dừng nhậ p
}
Ghi chú
: Để tạ o câ y nhị phâ n do biế n tree quả n lý, ta gọi:
Create_Tree(tree);
2. Cập nhật cây:
a. Giả i phóng vùng nhớ
(Free_Node): giả i phóng vùng nhớ mà p đang trỏ đế n.
void Free_Node(NODEPTR p)
{
free(p);
}
Lời gọi hà m
: Free_Node (p);
b. Kiể m tra câ y nhị phâ n rỗng hay không
(Empty): hà m Empty trả về
TRUE nế u câ y nhị phâ n rỗng, và ngược lạ i.
int Empty(NODEPTR root)
return(root == NULL ? TRUE : FALSE);
}
Kỹ thuật lập trì nh
114

xoựa nuựt p
10
3 15
12
20
2
4
rp

Hì nh 5.10. Xóa nút p trong trường hợp nút nà y có 1 câ y con bê n trá i.
2
10
5
3
15
4
20
18 25
rp
p
xoựa nuựt p
10
5
3
20
18 25
2 4

Hì nh 5.11. Xóa nút p trong trường hợp nút nà y có 1 câ y con bê n phả i.
-