Giáo trình Autocad 2D - Chương 3: Cấu trúc cây - Nguyễn Công Danh

ush(stdin);
scanf("%c",&(*T).Data[0]);
(*T).Parent[0]=NIL; // nut goc khong co cha 
for (i=1;i<=(*T).MaxNode-1;i++){
printf("Nhap cha cua nut %d ",i); 
scanf("%d",&(*T).Parent[i]);
printf("Nhap nhan cua nut %d ",i);
fflush(stdin);
scanf("%c",&(*T).Data[i]);
}
BÀI TẬP (3)
void main(){
printf("Nhap du lieu cho cay tong quat\n");
ReadTree(&T);
printf("Danh sach duyet tien tu cua cay la\n");
PreOrder(Root(T),T); 
printf("\nDanh sach duyet trung tu la\n");
InOrder(Root(T),T);
printf("\nDanh sach duyet hau tu cua cay la\n");
PostOrder(Root(T),T);
getch();
}
CÀI ĐẶT CÂY BẰNG DS CÁC NÚT CON (1)
• Minh họa A
D
F
B
0
1 4
5
C E2 3
IH
G
J
7
6
8 9
CÀI ĐẶT CÂY BẰNG DS CÁC NÚT CON (2)
• Mỗi nút có một danh sách các nút con
• Thường sử dụng cấu trúc danh sách liên kết 
để cài đặt các nút con do số lượng các nút 
con này biến động
• Khai báo:
typedef int node;
typedef .. . LabelType
typedef .. . LIST;
typedef struct 
{ LIST header[maxlength];
LabelType labels[maxlength];
node root;
}TREE;
CÀI ĐẶT CÂY THEO PHƯƠNG PHÁP CON 
TRÁI NHẤT VÀ ANH EM RUỘT PHẢI
• Ví dụ
CÂY NHỊ PHÂN (1)
• Định nghĩa
– Là cây rỗng hoặc có tối đa hai nút con
– Hai nút con có thứ tự phân biệt rõ ràng
• Con trái (left child): nằm bên trái nút cha
• Con phải (right child): nằm bên phải nút cha
• Ví dụ 1
AlexAlex
AngelaAngelaAbnerAbner
AbigailAbigail AdelaAdela
AdamAdam AgnesAgnes
AliceAlice
AllenAllen
AudreyAudrey
ArthurArthur
CÂY NHỊ PHÂN (2)
• Ví dụ 2
=>Là 2 cây nhị phân khác nhau
1
2
43
5
1
2
43
5
DUYỆT CÂY NHỊ PHÂN
• Các biểu thức duyệt: (N:Node, R:Right, L:Left)
– Tiền tự (NLR): duyệt nút gốc, duyệt tiền tự
con trái, duyệt tiền tự con phải. 
– Trung tự (LNR): duyệt trung tự con trái, duyệt 
nút gốc, duyệt trung tự con phải. 
– Hậu tự (LRN): duyệt hậu tự con trái, duyệt 
hậu tự con phải, duyệt nút gốc.
CÀI ĐẶT CÂY NHỊ PHÂN (1)
• Khai báo
typedef  TData;
typedef struct Tnode
{ TData Data;
TNode* left,right;
};
typedef TNode* TTree;
• Tạo cây rỗng
void MakeNullTree(TTree *T)
{ (*T)=NULL; }
• Kiểm tra cây rỗng
int EmptyTree(TTree T)
{return T==NULL;}
Data
left right
CÀI ĐẶT CÂY NHỊ PHÂN (1)
• Xác định con trái nhất
TTree LeftChild(TTree n)
{ if (n!=NULL) return n->left;
else return NULL; 
} 
• Xác định con phải
TTree RightChild(TTree n)
{if (n!=NULL) return n->right;
else return NULL;}
• Kiểm tra xem một nút có phải là lá không?
int IsLeaf(TTree n)
{if(n!=NULL)
return(LeftChild(n)==NULL)&&(RightChild(n)==NULL);
else return 0;}
CÀI ĐẶT CÂY NHỊ PHÂN (1)
• Duyệt tiền tự
void PreOrder(TTree T)
{ printf("%c ",T->Data);
if (LeftChild(T)!=NULL) 
PreOrder(LeftChild(T));
if(RightChild(T)!=NULL)
PreOrder(RightChild(T));
}
• Duyệt trung tự
void InOrder(TTree T){
if (LeftChild(T)=!NULL)InOrder(LeftChild(T));
printf("%c ",T->data);
if(RightChild(T)!=NULL) InOrder(RightChild(T));
}
CÀI ĐẶT CÂY NHỊ PHÂN (1)
• Duyệt hậu tự
void PosOrder(TTree T){
if(LeftChild(T)!=NULL) PosOrder(LeftChild(T));
if(RightChild(T)!=NULL)PosOrder(RightChild(T));
printf("%c ",T->data);
}
• Xác định số nút trong cây
int nb_nodes(TTree T){
if(EmptyTree(T)) return 0;
else return 1 + nb_nodes(LeftChild(T))+
nb_nodes(RightChild(T));
}
CÀI ĐẶT CÂY NHỊ PHÂN (1)
• Tạo cây mới từ hai cây có sẵn
TTree Create2(Tdata v,TTree l,TTree r)
{ TTree N;
N=(TNode*)malloc(sizeof(TNode));
N->Data=v;
N->left=l;
N->right=r;
return N; 
}
CÂY TÌM KIẾM NHỊ PHÂN
(Binary search tree-BST)
• Định nghĩa
Cây BST là cây nhị phân mà nhãn tại mỗi nút lớn hơn 
nhãn của tất cả các nút thuộc cây con bên trái và
nhỏ hơn nhãn của tất cả các nút thuộc cây con bên 
phải.
• Mô hình a
Các phần tử a
CÂY TÌM KIẾM NHỊ PHÂN
• Ví dụ
• Nhận xét
– Trên cây BST không có 2 nút trùng khóa.
– Cây con của 1 cây BST là 1 cây tìm kiếm nhị phân.
– Duyệt trung tự tạo thành dãy nhãn có giá trị tăng: 
4, 12, 20, 27, 30, 34, 40, 50
40
27
5034
30
12
204
CÀI ĐẶT CÂY BST
• Khai báo
typedef ... KeyType;
typedef struct Node
{ KeyType Key;
Node* Left,Right;
}
typedef Node* Tree;
CÀI ĐẶT CÂY BST
• Tìm kiếm một nút có khoá x
– Bắt đầu từ nút gốc ta tiến hành các bước 
sau:
• Nếu nút gốc bằng NULL thì khóa X không có
trên cây.
• Nếu X bằng khóa nút gốc thì giải thuật dừng vì 
đã tìm gặp X trên cây.
• Nếu X nhỏ hơn nhãn của nút hiện hành: tìm X 
trên cây con bên trái
• Nếu X lớn hơn nhãn của nút hiện hành: tìm X 
trên cây con bên phải
CÀI ĐẶT CÂY BST
Tree Search(KeyType x,Tree Root){
if (Root == NULL) return NULL;//không tìm thấy x
else if (Root->Key == x) // tìm thấy khoá x 
return Root;
else if (Root->Key < x)
//tìm tiếp trên cây bên phải 
return Search(x,Root->right);
else //tìm tiếp trên cây bên trái
return Search(x,Root->left);
}
CÀI ĐẶT CÂY BST
• Thêm một nút có khoá x vào cây
Muốn thêm 1 nút có khóa X vào cây BST, trước tiên 
ta phải tìm kiếm xem đã có X trên cây chưa. 
Nếu có thì giải thuật kết thúc, nếu chưa thì ta mới 
thêm vào. Việc thêm vào không làm phá vỡ tính 
chất cây BST.
– Giải thuật thêm vào như sau: bắt đầu từ nút gốc ta tiến 
hành các bước sau:
– Nếu nút gốc bằng NULL thì khóa X chưa có trên cây, do đó
ta thêm 1 nút mới.
– Nếu X bằng khóa nút gốc thì giải thuật dừng vì X đã có trên 
cây.
– Nếu X nhỏ hơn nhãn của nút hiện hành: xen X vào cây con 
bên trái
– Nếu X lớn hơn nhãn của nút hiện hành: xen X vào cây con 
bên phải
CÀI ĐẶT CÂY BST
• Ví dụ: Xen nút có khóa 32
40
27
5034
30
12
204
40
27
5034
30
12
204
32
Các thao tác xen
CÀI ĐẶT CÂY BST
void InsertNode(KeyType X, TTree *T)
{
if((*T) == NULL)
{
(*T) = (Node*)malloc(sizeof(Node));
(*T)->Key = X;
(*T)->left = NULL;
(*T)->right = NULL;
}
else
if((*T)->Key == X)
printf("Da ton tai khoa X");
else
if((*T)->Key > X)
InsertNode(X,&(*T)->left);
else
InsertNode(X,&(*T)->right);
}
CÀI ĐẶT CÂY BST
• Xóa một nút khóa X khỏi cây
– Muốn xóa 1 nút có khóa X trên cây BST. 
Trước tiên ta phải tìm xem có X trên cây 
không. 
– Nếu không thì giải thuật kết thúc
– Nếu gặp nút N chứa khóa X, có 3 trường 
hợp xảy ra
CÀI ĐẶT CÂY BST
• Trường hợp 1:
– N là nút lá: thay nút này bởi NULL
– Ví dụ: Xóa nút nhãn 20
40
27
5034
30
12
420
40
27
5034
30
12
4
Nút 
cần 
xóa
CÀI ĐẶT CÂY BST
• Trường hợp 2
– N có một cây con: thay nút này bởi cây 
con của nó
– Ví dụ: xóa nút có nhãn 34
40
27
5030
12
4
40
27
50
30
12
4 34
nút cần 
xóacây con
CÀI ĐẶT CÂY BST
• Trường hợp 3
–N có hai cây con: thay nút này bởi 
• Nút có nhãn lớn nhất của cây con bên 
trái, hoặc
• Nút có nhãn nhỏ nhất của cây con bên 
phải
CÀI ĐẶT CÂY BST
• Ví dụ: Xoá nút có nhãn 27
30
40
50
12
4
27
40
5030
12
4
nút cần 
xóa
nhãn nhỏ nhất 
ở bên phải
nhãn lớn nhất 
ở bên trái12
40
5030
4
CÀI ĐẶT CÂY BST
KeyType DeleteMin(TTree *T)
{
KeyType k;
if((*T)->left == NULL)
{
k = (*T)->Key;
(*T) = (*T)->right;
return k;
}
else return DeleteMin(&(*T)->left);
}
void DeleteNode(KeyType X, TTree *T)
{
if((*T)!=NULL) //Kiem tra cay khac rong
if(X Key) //Hy vong X nam ben trai cua nut
DeleteNode(X,&(*T)->left);
else
if(X > (*T)->Key) //Hy vong X nam ben phai cua nut
DeleteNode(X,&(*T)->right);
else // Tim thay khoa X tren cay
if(((*T)->left==NULL)&&((*T)->right==NULL))//X la nut la
(*T)=NULL; // Xoa nut X
else // X co it nhat mot con
if((*T)->left==NULL) //Chac chan co con phai
(*T) = (*T)->right;
else
if((*T)->right==NULL) //Chac chan co con trai
(*T) = (*T)->left;
else // X co hai con
(*T)->Key = DeleteMin(&(*T)->right);
}
KIẾN THỨC BỔ SUNG (1)
• Thời gian tìm kiếm một giá trị trên một 
cây TKNP có N nút là:
– O(log N) nếu cây “cân bằng” (balanced)
– O(N) nếu cây “không cân bằng” (unbalanced)
KIẾN THỨC BỔ SUNG (2)
• Bên dưới là một cây TKNP phân “không 
cân bằng”
CÂY NHỊ PHÂN ĐẦY ĐỦ (1)
(full binary tree)
• Một cây nhị phân là “cây nhị phân 
đầy đủ” nếu và chỉ nếu
– Mỗi nút không phải lá có chính xác 2 nút 
con
– Tất cả các nút lá có chiều cao bằng nhau
CÂY NHỊ PHÂN ĐẦY ĐỦ (2)
• Ví dụ -Một cây nhị phân đầy đủ
CÂY NHỊ PHÂN ĐẦY ĐỦ (3)
• Câu hỏi về cây nhị phân đầy đủ:
–Một cây nhị phân đầy đủ chiều cao h 
sẽ có bao nhiêu nút lá?
–Một cây nhị phân đầy đủ chiều cao h 
sẽ có tất cả bao nhiêu nút?
CÂY NHỊ PHÂN HOÀN CHỈNH (1)
(complete binary tree)
• Một cây nhị phân hoàn chỉnh (về chiều 
cao) thỏa mãn các điều kiện sau:
– Mức 0 đến h-1 là trình bày một cây nhị 
phân đầy đủ chiều cao h-1
– Một hoặc nhiều nút ở mức h-1 có thể có 0, 
hoặc 1 nút con
– Nếu j, k là các nút ở mức h-1, khi đó j có
nhiều nút con hơn k nếu và chỉ nếu j ở bên 
trái của k
CÂY NHỊ PHÂN HOÀN CHỈNH (2)
• Ví dụ
BB
AA
CC
DD EE
HH II JJ KK
FF GG
Figure 13.8 A complete b inary tree
CÂY NHỊ PHÂN HOÀN CHỈNH (3)
• Được cho một tập hợp N nút, một cây 
nhị phân hoàn chỉnh của những nút này 
cung cấp số nút lá nhiều nhất - với 
chiều cao trung bình của mỗi nút là nhỏ
nhất
• Cây hoàn chỉnh n nút phải chứa ít nhất 
một nút có chiều cao là ⎣log n⎦
CÂY NHỊ PHÂN CÂN BẰNG VỀ CHIỀU 
CAO (Height-balanced Binary Tree )
• Một cây nhị phân cân bằng về chiều 
cao là một cây nhị phân như sau:
– Chiều cao của cây con trái và phải của bất kỳ nút 
nào khác nhau không quá một đơn vị
– Chú ý: mỗi cây nhị phân hoàn chỉnh là một cây 
cân bằng về chiều cao 
CÂY CÂN BẰNG VỀ CHIỀU 
CAO – VÍ DỤ
N M N-M<=1
Cân bằng về chiều cao là một thuộc tính cục bộ
ƯU ĐIỂM CỦA CÂY CÂN BẰNG
• Cây nhị phân cân bằng về chiều cao là
cây “cân bằng”
• Thời gian tìm kiếm một nút trên cây N 
nút là O(logN)
KiỂM TRA 4
Vẽ cây nhị phân cho bởi 2 
danh sách duyệt như sau:
NLR: A,B,C,D,E,F,H,G,J,K,I
LNR: B,D,C,E,A,H,K,J,F,G,I
KiỂM TRA 5 (1 điểm)
a.Vẽ cây tìm kiếm nhị phân cân 
bằng cho bởi danh sách sau:
90, 30, 50, 10, 25, 35, 20, 30, 15, 
80, 75, 45, 65, 5, 55, 100.
b. Vẽ lại cây sau khi xóa 35, xóa 
65, thêm 43, xóa 20.