Giáo trình Cấu trúc dữ liệu và Giải thuật - Chương 5: Cấu trúc cây - Đỗ Tuấn Anh

2
Các nút hoặc là nút lá
hoặc có cấp = 2.
Tất cả nút lá đều có cùng
độ sâu và tất cả nút giữa có
cấp = 2.
Cây nhị phân hoàn chỉnh:
Một số dạng cây nhị phân
Một số tính chất
zSố nút tối đa có độ sâu i : 2i
zSố nút tối đa (với cây nhị phân độ cao H) 
là: 2H+1 - 1
zĐộ cao (với cây nhị phân gồm N nút): H
{Tối đa = N 
{Tối thiểu = [log2(N+1)] - 1
2.2 Lưu trữ cây nhị phân
zLưu trữ kế tiếp:
{Sử dụng mảng
Lưu trữ móc nối
a
b
fe
c
a rightleft
rightleft b
g
NULL
left right
left right
right
g
e
c
left
left right
f
Xây dựng cấu trúc cây nhị phân
zMỗi nút chứa :
{Dữ liệu
{2 con trỏ trỏ đến 2 nút con của nó
Data
Nút con 
trái
Nút con 
phải
Cấu trúc cây nhị phân
typedef struct tree_node
{
int data ;
struct tree_node *left ;
struct tree_node *right ;
} TREE_NODE;
Tạo cây nhị phân
TREE_NODE *root, *leftChild, *rightChild;
// Tạo nút con trái
leftChild = (TREE_NODE*)malloc(sizeof(TREE_NODE)); 
leftChild->data = 20;
leftChild->left = leftChild->right = NULL;
// Tạo nút con phải
rightChild = (TREE_NODE*)malloc(sizeof(TREE_NODE)); 
rightChild->data = 30;
rightChild->left = rightChild->right = NULL;
// Tạo nút gốc
root = (TREE_NODE*)malloc(sizeof(TREE_NODE)); 
root->data = 10;
root->left = leftChild;
root->right = rightChild;
10
20 30
root -> data = 50; // gán 50 cho root
5
2.3. Duyệt cây nhị phân
z Duyệt cây: lần lượt duyệt toàn bộ nút trên cây
z Có 3 cách duyệt cây :
{ Duyệt theo thứ tự trước
{ Duyệt theo thứ tự giữa
{ Duyệt theo thứ tự sau
z Định nghĩa duyệt cây nhị phân là những định
nghĩa đệ quy.
Duyệt theo thứ tự trước
1. Thăm nút.
2. Duyệt cây con trái theo thứ tự trước.
3. Duyệt cây con phải theo thứ tự trước.
a
b c
d e
Traversal order: abdce
Duyệt theo thứ tự sau
1. Duyệt cây con trái theo thứ tự sau.
2. Duyệt cây con phải theo thứ tự sau.
3. Thăm nút.
a
b c
d e
Thứ tự duyệt: dbeca
Duyệt theo thứ tự giữa
1. Duyệt cây con trái theo thứ tự giữa
2. Thăm nút.
3. Duyệt cây con phải theo thứ tự giữa.
a
b c
d e
Thứ tự duyệt: bdaec
Ví dụ
15
3
6
2 4
13
7
9
20
18
17
Thứ tự trước:
Thứ tự giữa:
Thứ tự sau:
15, 6, 3, 2, 4, 7, 13, 9, 18, 17, 20
2, 3, 4, 6, 7, 9, 13, 15, 17, 18, 20
2, 4, 3, 9, 13, 7, 6, 17, 20, 18, 15
Duyệt theo thứ tự trước – Đệ quy
void Preorder(TREE_NODE* root)
{
if (root!=NULL)
{
// tham aNode
printf("%d ", root->data);
// duyet cay con trai
Preorder(root->left);
// duyet cay con phai
Preorder(root->right);
}
}
zBài tập: Viết giải thuật đệ quy của
{Duyệt theo thứ tự giữa 
{Duyệt theo thứ tự sau
Duyệt theo thứ tự trước – Vòng lặp
void Preorder_iter(TREE_NODE* treeRoot)
{
TREE_NODE* curr = treeRoot;
STACK* stack = createStack(MAX); // khởi tạo stack
while (curr!=NULL || !IsEmpty(stack))
{
printf("%d ", curr->data); // thăm curr
// nếu có cây con phải, đẩy cây con phải vào stack
if (curr->right!=NULL)
pushStack(stack, curr->right);
if (curr->left!=NULL)
curr = curr->left; // duyệt cây con trái
else
popStack(stack, &curr);// duyệt cây con phải
}
destroyStack(&stack); // giải phóng stack
}
Duyệt theo thứ tự giữa
void Inorder_iter(TREE_NODE* root){
TREE_NODE* curr = root;
STACK* stack = createStack(MAX);// ktạo stack
while (curr!=NULL || !IsEmpty(stack))
{
if (curr==NULL){
popStack(stack, &curr);
printf(“%d”, curr->data);
curr = curr->right;
}
else
{
pushStack(stack, curr);
curr = curr->left; // duyệt cây con trái
}
}
destroyStack(stack);// giải phóng stack
}
Duyệt theo thứ tự cuối
void Postorder_iter(TREE_NODE* treeRoot)
{
TREE_NODE* curr = treeRoot;
STACK* stack = createStack(MAX);// ktạo một stack
while(curr != NULL || !IsEmpty(stack)) {if (curr == NULL) {
while(!IsEmpty(stack) && curr==Top(stack)->right){PopStack(stack, &curr);
printf(“%d”, curr->data);
}
curr = isEmpty(stack)? NULL: Top(stack)->right;} 
else {
PushStack(stack, curr);curr = curr->left;}} 
destroyStack(&stack); // giải phóng stack
}
Một vài ứng dụng của phương pháp 
duyệt cây
1. Tính độ cao của cây
2. Đếm số nút lá trong cây
3. Tính kích thước của cây (số nút)
4. Sao chép cây
5. Xóa cây
6. 
Tính độ cao của cây
int Height(TREE_NODE *tree)
{
int heightLeft, heightRight, heightval; 
if ( tree == NULL )
heightval = -1; 
else
{ // Sử dụng phương pháp duyệt theo thứ tự sau
heightLeft = Height (tree->left); 
heightRight = Height (tree->right); 
heightval = 1 + max(heightLeft, heightRight);
}
return heightval; 
}
0
1 0
2
-1-1
Đếm số nút lá
int CountLeaf(TREE_NODE *tree)
{
if (tree == NULL)
return 0;
int count = 0;
// Đếm theo thứ tự sau
count += CountLeaf(tree->left); // Đếm trái
count += CountLeaf(tree->right); // Đếm phải
// nếu nút tree là nút lá, tăng count
if (tree->left == NULL && tree->right == NULL) 
count++;
return count;
}
thứ tự đếm
1
2
3
Kích thước của cây
int TreeSize(TREE_NODE *tree)
{
if (tree == NULL) 
return 0; 
else
return ( TreeSize(tree->left) + 
TreeSize(tree->right) + 1 );
}
t
Sao chép cây
A
B C
ED
D
B
ED
C
D
B
(1)
(2)
C
A
B
ED
(3) (4)
Sao chép cây
TREE_NODE* CopyTree(TREE_NODE *tree)
{
// Dừng đệ quy khi cây rỗng
if (tree == NULL) return NULL; 
TREE_NODE *leftsub, *rightsub, *newnode;
leftsub = CopyTree(tree->left); 
rightsub = CopyTree(tree->right); 
// tạo cây mới
newnode = malloc(sizeof(TREE_NODE));
newnode->data = tree->data;
newnode->left = leftsub;
newnode->right = rightsub;
return newnode; 
}
Xóa cây
void DeleteTree(TREE_NODE *tree)
{
// xóa theo thứ tự sau
if (tree != NULL)
{
DeleteTree(tree -> left); 
DeleteTree(tree -> right); 
free (tree);
}
}
3. Cây tổng quát
3.1. Biểu diễn cây tổng quát
zBiểu diễn giống như cây nhị phân?
{Mỗi nút sẽ chứa giá trị và các con trỏ trỏ đến
các nút con của nó?
{Bao nhiêu con trỏ cho một nút? – Không hợp lý
zMỗi nút sẽ chứa giá trị và một con trỏ trỏ
đến một “tập” các nút con
{Xây dựng “tập” như thế nào? 
Biểu diễn cây tổng quát
zSử dụng con trỏ nhưng mở rộng hơn:
{Mỗi nút sẽ có 2 con trỏ: một con trỏ trỏ đến nút
con đầu tiên của nó, con trỏ kia trỏ đến nút anh
em kề với nó
{Cách này cho phép quản lý số lượng tùy ý của
các nút con
Data
Nút con 
trái nhất
Nút anh
em kề
Ví dụ
3.2. Duyệt cây tổng quát
1. Thứ tự trước:
1. Thăm gốc
2. Duyệt cây con thứ nhất theo thứ tự trước
3. Duyệt các cây con còn lại theo thứ tự trước
2. Thứ tự giữa
1. Duyệt cây con thứ nhất theo thứ tự giữa
2. Thăm gốc
3. Duyệt các cây con còn lại theo thứ tự giữa
3. Thứ tự sau:
1. Duyệt cây con thứ nhất theo thứ tự sau
2. Duyệt các cây con còn lại theo thứ tự sau
3. Thăm gốc
4. Ứng dụng của cây nhị phân
zCây biểu diễn biểu thức
{Tính giá trị biểu thức
{Tính đạo hàm 
zCây quyết định
45
Một loại cây nhị phân đặc biệt, trong đó:
1. Mỗi nút lá chứa một toán hạng
2. Mỗi nút giữa chứa một toán tử
3. Cây con trái và phải của một nút toán 
tử thể hiện các biểu thức con cần 
được đánh giá trước khi thực hiện 
toán tử tại nút gốc
Cây biểu diễn biểu thức là . . .
46
Biểu thức nhị phân
‘*’
‘-’
‘8’ ‘5’
‘/’
‘+’
‘4’
‘3’
‘2’
47
Các mức chỉ ra thứ tự ưu tiên
Các mức(độ sâu) của các nút chỉ ra thứ tự 
ưu tiên tương đối của chúng trong biểu 
thức (không cần dùng ngoặc để thể hiện thứ tự ưu tiên).
Các phép toán tại mức cao hơn sẽ được tính 
sau các các phép toán có mức thấp.
Phép toán tại gốc luôn được thực hiện cuối 
cùng.
48
Cây biểu diễn biểu thức
Giá trị kết quả?
( 4 + 2 ) * 3 = 18
‘*’
‘+’
‘4’
‘3’
‘2’
49
Dễ dàng để tạo ra các biểu thức tiền tố, trung tố, 
hậu tố
Trung tố: ( ( 8 - 5 ) * ( ( 4 + 2 ) / 3 ) )
Tiền tố: * - 8 5 / + 4 2 3
Hậu tố: 8 5 - 4 2 + 3 / *
‘*’
‘-’
‘8’ ‘5’
‘/’
‘+’
‘4’
‘3’
‘2’
50
Duyệt theo thứ tự giữa
(A + H) / (M - Y)
‘/’
‘+’
‘A’ ‘H’
‘-’
‘M’ ‘Y’
cây
51
Duyệt theo thứ tự trước
/ + A H - M Y
‘/’
‘+’
‘A’ ‘H’
‘-’
‘M’ ‘Y’
cây
52
‘/’
‘+’
‘A’ ‘H’
‘-’
‘M’ ‘Y’
tree
Duyệt theo thứ tự sau
A H + M Y - /
53
Mỗi nút có 2 con trỏ
struct TreeNode 
{
InfoNode info ; // Dữ liệu
TreeNode* left ; // Trỏ tới nút con trái
TreeNode* right ; // Trỏ tới nút con phải
};
. left . info . right
NULL 6000
. whichType . operand
OPERAND 7 
54
InfoNode có 2 dạng
enum OpType { OPERATOR, OPERAND } ;
struct InfoNode 
{
OpType whichType;
union // ANONYMOUS union
{
char operator ;
int operand ;
}
};
. whichType . operation
OPERATOR ‘+’
. whichType . operand
OPERAND 7
55
int Eval (TreeNode* ptr)
{ 
switch ( ptr->info.whichType ) 
{ 
case OPERAND : return ptr->info.operand ;
case OPERATOR :
switch ( tree->info.operation )
{
case ‘+’ : return ( Eval ( ptr->left ) + Eval ( ptr->right ) ) ; 
case ‘-’ : return ( Eval ( ptr->left ) - Eval ( ptr->right ) ) ;
case ‘*’ : return ( Eval ( ptr->left ) * Eval ( ptr->right ) ) ; 
case ‘/’ : return ( Eval ( ptr->left ) / Eval ( ptr->right ) ) ;
}
}
}
Cây quyết định
zDùng để biểu diễn lời giải của bài toán cần 
quyết định lựa chọn
zBài toán 8 đồng tiền vàng:
{Có 8 đồng tiền vàng a, b, c, d, e, f, g, h
{Có một đồng có trọng lượng không chuẩn
{Sử dụng một cân Roberval (2 đĩa)
{Output: 
zĐồng tiền k chuẩn là nặng hơn hay nhẹ hơn
zSố phép cân là ít nhất
a+b+c ? d+e+f
a+d ? b+e g ? h a+d ? b+e
a ? b a ? c b ? aa ? bh ? ag ? ab ? ac ? d
a e c f b d g h h g b d c f a e
> <
> = > =
> > > > >= = = = = = = =
=
<
> > >
void EightCoins(a, b, c, d, e, f, g, h) {
if (a+b+c == d+e+f) {
if (g > h) Compare(g, h, a);
else Compare(h, g, a);
}
else if (a+b+c > d+e+f){
if (a+d == b+e) Compare(c, f, a);
else if (a+d > b+e) Compare(a, e, b);
else Compare(b, d, a);
}
else{
if (a+d == b+e) Compare(f,c,a);
else if (a+d > b+e) Compare(d, b, a);
else Compare(e, a, b);
}
}
// so sánh x với đồng tiền chuẩn z
void Compare(x,y,z){ 
if(x>y) printf(“x nặng”);
else printf(“y nhẹ”);
}