BÀI TẬP LỚN KSTN-CNTT
dn
Nguyễn Văn Thiện – Lê Anh Vũ – Vũ Văn Tú – Nguyễn Hoàng Hải Đỗ Quốc Đạt Page 1
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
BÀI TẬP NHÓM MÔN HỌC
IT3040 – KỸ THUẬT LẬP TRÌNH 2012-2013
Giảng viên hướng dẫn : PGS. TS. Huỳnh Quyết Thắng
Nhóm học viên : Nguyễn Hoàng Hải
Nguyễn Văn Thiện
Vũ Văn Tú
Lê Anh Vũ
Đỗ Quốc Đạt
Lớp: KSTN_CNTT_K56
HÀ NỘI 2013
Hà Nội, 05/2013
BÀI TẬP LỚN
BÀI TẬP LỚN KSTN-CNTT

MỤC LỤC
Nguyễn Văn Thiện – Lê Anh Vũ – Vũ Văn Tú – Nguyễn Hoàng Hải Đỗ Quốc Đạt Page 2
BÀI TẬP LỚN KSTN-CNTT
I.
GIỚI THIỆU VÀ ỨNG DỤNG CỦA CÂY NHỊ PHÂN
1.
Định nghĩa:
1.1.
Cây
Là đồ thị có hướng, lien thông và không có chu trình. Cây bao gồm các nút, có một nút đặc biệt
gọi là gốc (root) và các cạnh nối các nút.
1.2.

•
Biểu diễn bằng mảng:
Với cây nhị phân đầy đủ, ta đánh số các nút từ 1 trở đi, hết mức này đến mức khác, từ trái qua
phải. Dùng mảng V lưu trữ cây nhị phân , nút thứ i của cây được lưu trữ ở phần tử V(i).
•
Ví dụ với cây đày đủ ở trên được lưu trữ như sau:

•
Biểu diễn bằng con trỏ:
Trong cách lưu trữ này , mỗi nút ứng với một phần tử nhớ có quy cách như sau:

LPTR INFO RPTR
Nguyễn Văn Thiện – Lê Anh Vũ – Vũ Văn Tú – Nguyễn Hoàng Hải Đỗ Quốc Đạt Page 4
BÀI TẬP LỚN KSTN-CNTT
LPTR : Con trỏ trỏ tới cây con trái của nút đó
RPTR : Con trỏ trỏ tới cây con phải của nút đó
INFO : Trường thông tin.
•
Ví dụ cây nhị phân sau đây:
4.
Các thao tác trên cây nhị phân:
4.1.
Cấu trúc:
typedef struct TreeNode {
char key[20];
struct TreeNode *lChild;
struct TreeNode *rChild;
}TreeNode;
4.2.
Tạo nút:

Duyệt cây theo thứ tự giữa LNR (inoder Traversal)
Void printInoder(TreeNode *root){
if(root!=NULL){
printInoder(root->lChild);
printf(“%s\n”,root->key);
printInoder(root->rChild);
}
}
4.6.
Duyệt cây theo thứ tự sau LRN (postoder Traversal)
void printPostoder(TreeNode *root){
if(root!=NULL){
printPostoder(root->lChild);
printPostoder(root->rChild);
printf(“%s\n”,root->key);
}
}
Nguyễn Văn Thiện – Lê Anh Vũ – Vũ Văn Tú – Nguyễn Hoàng Hải Đỗ Quốc Đạt Page 6
BÀI TẬP LỚN KSTN-CNTT
II.
Bài toán đặt ra
1. Giới thiệu:
Nếu một nút trong một cây nhị phân hoặc không có con trái hoặc không có con phải hoặc là nút
lá thì con trỏ trái hoặc phải của nút đó có giá trị NULL. Một cách tránh con trỏ NULL đó là sử
dụng con trỏ này thay vì chứa giá trị NULL nó sẽ trỏ đến nút cao hơn trong cây đó là nút tổ
tiên. Một ví dụ cho thao tác này là việc cài đặt threaded binary tree, đây là cây nhị phân mà
trong đó các nút chứa con trỏ NULL sẽ được trỏ đến inorder predecessor(nút ngay trước nút
đang xét trong thứ tự giữa hoặc trỏ đến inorder sucecssor(nút ngay sau trong thứ tự giữa).
Bằng cách này, chúng ta có thể duyệt cây mà không cần dùng đệ quy.
Cấu trúc của cây này khác một chút so với cây nhị phân:

Bước 4: Tại nút vừa in ra, kiểm tra rChild là con thật sự hay thread. Nếu là thread,
gán
currentNode=currentNode->rChild và in ra nút đó. Nếu là con thực sự,
gán currentNode=currentNode->rChild
Xét ví dụ trên:
Nguyễn Văn Thiện – Lê Anh Vũ – Vũ Văn Tú – Nguyễn Hoàng Hải Đỗ Quốc Đạt Page 9
BÀI TẬP LỚN KSTN-CNTT
Bước 1
Tại nút A, ta tìm được B là nút ngay sau A trong thứ tự giữa, ta sửa lại con trỏ phải của B đến A
Bước 2
Rẽ trái qua B, sửa lại con trỏ phải của D, rẽ trái tiếp đến D
Bước 3
D không có con trái, không rẽ tiếp được nữa,i
n raD
Bước 4 Kiểm tra con trỏ phải của D không là con thực sự nên ta gán lại nút hiện tại là B và in ra B
Bước 5 Kiểm tra con trỏ phải của B không là con thực sự nên ta gán lại nút hiện tại là A và in ra A
Bước 6 Kiểm tra con trỏ phải của A là con thực sự nên ta gán lại nút hiện tại là C và quay lại bước 1 với nút hiện tại là
C
Bước 7 Rẽ trái hết mức đến E. In ra E
Bước 8 Con trỏ phải của E chỉ đến NULL nên ta kết thúc
void inorder(TreeNode *root){
TreeNode *currentNode, *tempNode;
currentNode=root;
while(currentNode!=NULL){ /*Nut cuoi cung trong thu tu giua se
co *rChild bang NULL va sau
lastNode->rChild vong lap ket thuc*/
tempNode=findInorderPre(currentNode); /*Tim nut nhan
currentNode lam right
thread, gan lai
rChild cua nut do*/

Bước 1
Tại nút A, ta tìm được B là nút ngay sau A trong thứ tự giữa, ta sửa lại con trỏ phải của B đến A. In ra A
Bước 2
Rẽ trái qua B, sửa lại con trỏ phải của D, rẽ trái tiếp đến D. In ra B
Bước 3
D không có con trái, không rẽ tiếp được nữa. I
n raD
Bước 4 Kiểm tra con trỏ phải của D không là con thực sự nên ta gán lại nút hiện tại là B
Nguyễn Văn Thiện – Lê Anh Vũ – Vũ Văn Tú – Nguyễn Hoàng Hải Đỗ Quốc Đạt Page 11
BÀI TẬP LỚN KSTN-CNTT
Bước 5 Kiểm tra con trỏ phải của B không là con thực sự nên ta gán lại nút hiện tại là A
Bước 6 Kiểm tra con trỏ phải của A là con thực sự nên ta gán lại nút hiện tại là C và quay lại bước 1 với nút hiện tại là
C.
Bước 7 In ra C
Bước 8 Rẽ trái đến E. In ra E
Bước 9 Con trỏ phải của E chỉ đến NULL, ta kết thúc
void preorder(TreeNode *root){
TreeNode *currentNode, *tempNode;
currentNode=root;
while(currentNode!=NULL){ /*Nut cuoi cung trong thu tu giua se
co *rChild bang NULL va sau
lastNode->rChild vong lap ket thuc*/
tempNode=findInorderPre(currentNode); /*Tim nut nhan
currentNode lam right
thread,gan lai rChild
cua nut do*/
/*In ra nut hien tai, re trai het muc co the, di den dau in den do*/
printf("%c ",currentNode->key);
while(currentNode->lFlag==TRUE&&currentNode->lChild!=NULL){
currentNode=currentNode->lChild;

• TreeNode *lChild; con trỏ trỏ về con trái của nút cha.
• TreeNode *rChild; con trỏ trỏ về con phải của nút cha.
Nguyễn Văn Thiện – Lê Anh Vũ – Vũ Văn Tú – Nguyễn Hoàng Hải Đỗ Quốc Đạt Page 13
BÀI TẬP LỚN KSTN-CNTT
• Int lFlag; có giá trị bằng TRUE nếu có con trỏ lChild chỉ đến con, FALSE nếu
tới luồng;
• Int rFlag; có giá trị bằng TRUE nếu có con trỏ rChild chỉ đến con, FALSE nếu
tới luồng;

Các trường lFlag và rFlag dùng thay cho các việc xét con trái là null hay con
phải là null vì sau khi chuyển đổi cây thì không còn con trỏ nào trỏ đến nút null
nữa.
#define TRUE 1
#define FALSE 0
typedef struct TreeNode {
char key;
struct TreeNode *lChild;
struct TreeNode *rChild;
int lFlag;//TRUE neu lChild tro toi con, FALSE neu toi thread
int rFlag;//TRUE neu rChild tro toi con, FALSE neu toi thread
}TreeNode;
funtlist.h
Chứa các hàm được sử dụng trong project
TreeNode *getNode(char key);\\ Tạo nút từ 1 ký tự
TreeNode *findInorderPre(TreeNode *node);\\ Tìm nút đứng trước trong duyệt theo thứ
tự giữa
TreeNode *findInorderSuc(TreeNode *node);\\ Tìm nút đứng sau trong duyệt theo thứ
tự giữa
void inorder(TreeNode *root);\\ Duyệt cây theo thứ thự giữa
void preorder(TreeNode *root);\\ Duyệt cây theo thứ thự trước

Nguyễn Văn Thiện – Lê Anh Vũ – Vũ Văn Tú – Nguyễn Hoàng Hải Đỗ Quốc Đạt Page 15
BÀI TẬP LỚN KSTN-CNTT
2.2.3 Tạo luồng
Ý tưởng Cách tìm nút đứng ngay trước 1 nút P trong thứ tự giữa
TH1:Nếu nút P có con trái, ta đi đến con trái rồi từ đó rẽ phải chừng nào nút hiện tại
vẫn có con phải (rflag=TRUE), nút cần tìm là nút hiện tại. Tóm lại, nút cần tìm là nút
phải nhất của con trái. Ta gán lại currentNode->right=P
TreeNode *findInorderPre(TreeNode *node){
TreeNode *tempNode;
if(node->lFlag==FALSE) return node->lChild;
else{
tempNode=node->lChild;
while(tempNode->rFlag==TRUE){
tempNode=tempNode->rChild;
}
tempNode->rChild=node;
return tempNode;
}
Nguyễn Văn Thiện – Lê Anh Vũ – Vũ Văn Tú – Nguyễn Hoàng Hải Đỗ Quốc Đạt Page 16
BÀI TẬP LỚN KSTN-CNTT
}
TH2: Nếu nút P không có con trái (lflag=FALSE), con trỏ left sẽ phải trỏ đến nút ngay
trước nút P trong thứ tự giữa. Trong quá trình duyệt các nút tổ tiên của P, đã tồn tại 1
nút làm thao tác gán lại con trỏ left của P.Vì vậy kết quả là P->left:
TreeNode *findInorderSuc(TreeNode *node){
TreeNode *tempNode;
if(node->rFlag==FALSE) return node->rChild;
else{
tempNode=node->rChild;
while(tempNode->lFlag==TRUE){

currentNode=currentNode->rChild;
}
halt();
}
void preorder(TreeNode *root){
TreeNode *currentNode, *tempNode;
currentNode=root;
while(currentNode!=NULL){/*Nut cuoi cung trong thu tu giua se
co *rChild bang NULL va sau currentNode->rChild
vong lap ket thuc*/
tempNode=findInorderPre(currentNode);/*Tim nut nhan currentNode lam right
thread, gan lai rChild cua nut do*/
/*In ra nut hien tai roi re trai het muc co the, di den dau in den do*/
printf("%c ",currentNode->key);
while(currentNode->lFlag==TRUE&&currentNode->lChild!=NULL){
currentNode=currentNode->lChild;
tempNode=findInorderPre(currentNode);
printf("%c ",currentNode->key);
}
/*Chung nao rChild con la thread thi nhay theo thread nhung khong in*/
while(currentNode->rFlag==FALSE&&currentNode->rChild!=NULL){
currentNode=currentNode->rChild;
}
/*Neu rChild chi den con thuc su thi re phai*/
currentNode=currentNode->rChild;
}
halt();
}
void postorder(TreeNode *root){
if(root->lFlag==TRUE&&root->lChild!=NULL) postorder(root->lChild);

GetConsoleScreenBufferInfo(GetStdHandle(STD_OUTPUT_HANDLE), &csbi);
return csbi.dwCursorPosition.Y;
}
Nguyễn Văn Thiện – Lê Anh Vũ – Vũ Văn Tú – Nguyễn Hoàng Hải Đỗ Quốc Đạt Page 19
BÀI TẬP LỚN KSTN-CNTT
Để tiến hành vẽ cây, từ ý tưởng xây dựng, ta viết hàm vẽ nút drawNode và hàm
printTree để in cây.
// Vẽ nút.
int drawNode(char value,int &x,int &y,int &l,int type,int position){
switch(position){
case LEFT:{
y=y+4;
x=x-2-l;
break;
}
case RIGHT:{
x=x+2+l;
y=y+4;
break;
}
default: break;
}
l=l/2;
gotoxy(x,y);printf("|");
gotoxy(x,y+1);printf("|");
gotoxy(x-1,y+2);printf(" ");
gotoxy(x-2,y+3);printf("|%3c|",value);
gotoxy(x-1,y+4);printf(" ");
if (type==LEFT||type==FULL){
gotoxy(x-2-l,y+3);

2.2.6 In giao diện chương trình:
Giao diện chương trình là một menu có các thao tác lựa chọn để người dùng thao tác
với cây như thêm nút, duyệt cây, in cây.
1. In theo thứ tự trước
2. In theo thứ tự giữa
3. In theo thứ tự sau
4. Thêm nút
5. In cây
6. Thoát
Khi người dùng yêu cầu thao tác nào thì hệ thống tương ứng sẽ gọi các hàm thực thi
chúng.
2.3 Hình ảnh chạy demo.
Khi bắt đầu, chương trình sẽ yêu cầu bạn nhập cây:
Nguyễn Văn Thiện – Lê Anh Vũ – Vũ Văn Tú – Nguyễn Hoàng Hải Đỗ Quốc Đạt Page 22
BÀI TẬP LỚN KSTN-CNTT
Nguyễn Văn Thiện – Lê Anh Vũ – Vũ Văn Tú – Nguyễn Hoàng Hải Đỗ Quốc Đạt Page 23
BÀI TẬP LỚN KSTN-CNTT
Sau khi nhập xong, sẽ hiện Menu
III. TÀI LIỆU THAM KHẢO
[1] Bài giảng Cấu trúc dữ liệu và giải thuật – Thầy Nguyễn Đức Nghĩa
[2] Data Structures and Algorithm Analysis - Clifford A. Shaffer
Nguyễn Văn Thiện – Lê Anh Vũ – Vũ Văn Tú – Nguyễn Hoàng Hải Đỗ Quốc Đạt Page 24
BÀI TẬP LỚN KSTN-CNTT
[3] />Nguyễn Văn Thiện – Lê Anh Vũ – Vũ Văn Tú – Nguyễn Hoàng Hải Đỗ Quốc Đạt Page 25