Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5.2 - ThS. Nguyễn Hà Giang
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (10.04 MB, 46 trang )
Tree Structure
Nguyễn Hà Giang - 2008
ThS. Nguyễn Hà Giang
Hutech - FIT
1
Nội dung
Cấu trúc cây
Cây nhị phân
Cây nhị phân tìm kiếm
Cây nhị phân tìm kiếm cân bằng AVL
Nguyễn Hà Giang - 2008
2
Cấu trúc dữ liệu
Nguyễn Hà Giang - 2008
3
Cấu trúc cây
Tập hợp các nút và cạnh nối các nút đó
Có một nút gọi là gốc
Quan hệ one-to-many giữa các nút
Có duy nhất một đường đi từ gốc đến một nút
Các loại cây:
Nhị phân: mỗi nút có {0,1, 2} nút con
Tam phân: mỗi nút có {0,1,2,3} nút con
n-phân: mỗi nút có {0,1,..,n} nút con
Nguyễn Hà Giang - 2008
4
Cấu trúc cây
Sao trong máy
tính, cây lại
thể hiện
ngược?
Nguyễn Hà Giang - 2008
5
Khái niệm
gốc
J
Cạnh
nút
Z
B
Q
A
R
K
Nguyễn Hà Giang - 2008
D
A
F
L
Lá
6
Khái niệm
Thuật ngữ
Nút gốc: khơng có nút cha
Nút lá: khơng có nút con
Nút trong: khơng phải nút con và nút gốc
Chiều cao: khoảng cách từ gốc đến lá
Nút gốc
Nút trong
Chiều cao
Nút lá
Nguyễn Hà Giang - 2008
7
Khái niệm
Root
Node A
Node C
Node H
Node B
Node D
Node E
Node I
Node F
Node J
Node G
Node K
Node L
Cây con
Nguyễn Hà Giang - 2008
Nút anh em
8
Nội dung
Cấu trúc cây
Cây nhị phân
Cây nhị phân tìm kiếm
Cây nhị phân tìm kiếm cân bằng AVL
Nguyễn Hà Giang - 2008
9
Binary Tree
Cấu trúc cây đơn giản nhất
Tại mỗi nút gồm các 3 thành phần
Phần data: chứa giá trị, thông tin…
Liên kết đến nút con trái (nếu có)
Liên kết đến nút con phải (nếu có)
Cây nhị phân có thể rỗng (ko có nút nào)
Cây NP khác rỗng có 1 nút gốc
Có duy nhất 1 đường đi từ gốc đến 1 nút
Nút khơng có nút con bên trái và con bên phải là
nút lá
Nguyễn Hà Giang - 2008
10
Binary Tree
Kích thước = 9 (số nút)
Mức 0
A
Cây con phải
Cây con trái
Mức 1
Mức 2
B
D
Mức 3
Nguyễn Hà Giang - 2008
C
E
H
F
I
G
Độ sâu/chiều cao = 3
11
Binary Tree
Cây nhị phân đúng:
Nút gốc và nút trung gian có đúng 2 con
Cây nhị phân đúng có n nút lá thì số nút trên
cây 2n-1
A
B
D
E
H
Nguyễn Hà Giang - 2008
C
F
I
G
J
K
12
Binary Tree
Cây nhị phân đầy đủ với chiều sâu d
Phải là cây nhị phân đúng
Tất cả nút lá có chiều sâu d
A
(2d+1
Số nút =
-1)
Số nút trung gian = ?
Biết số nút tính d của cây NP đầy đủ
B
D
Nguyễn Hà Giang - 2008
C
E
F
G
13
Binary Tree
Duyệt cây:
Do cây là cấu trúc ko tuyến tính
3 cách duyệt cây NP
Duyệt theo thứ tự trước PreOrder: NLR
Duyệt theo thứ tự giữa InOrder: LNR
Duyệt theo thứ tự sau PostOrder: LRN
Nguyễn Hà Giang - 2008
14
Binary Tree
PreOrder:
InOrder:
PostOrder:
A
B
D
C
E
H
Nguyễn Hà Giang - 2008
F
I
G
J
K
15
Binary Tree
Cài đặt cây NP dùng liên kết
typedef struct node
{
DataType
info;
struct node * left;
struct node * right;
} NODE;
typedef NODE * NodePtr;
NodePtr
Nguyễn Hà Giang - 2008
pTree;
Chứa thông tin của nút
Cấu trúc của một nút
Trỏ đến nút con phải
Trỏ đến nút con trái
Trỏ nút gốc của cây NP
16
Binary Tree
pTree
Con trỏ pTree trỏ
đến nút gốc của cây
8
5
1
3
9
Nguyễn Hà Giang - 2008
10
4
20
7
17
Binary Tree
Các thao tác:
NewNode, CreateNode, FreeNode, Init, IsEmpty
InsertLeft, InsertRight
DeleteLeft, DeleteRight
PreOrder, InOrder, PostOrder
Phần minh
Search
hoạ dùng
ClearTree
DataType là
kiểu int
Nguyễn Hà Giang - 2008
18
Binary Tree
CreateNode: tạo một nút mới có giá trị là x
NodePtr CreateNode(int x)
{
NodePtr node;
node = NewNode();
node->info = x;
node->left = NULL;
node->right = NULL;
return node;
}
Nguyễn Hà Giang - 2008
node
new
X
19
Binary Tree
InsertLeft: thêm nút con bên trái nút p
int InsertLeft(NodePtr p, int x)
{
if (p == NULL) return FALSE;
if (p->left != NULL) return FALSE;
p->left = CreateNode(x);
return TRUE;
}
Nguyễn Hà Giang - 2008
20
Binary Tree
InsertRight: thêm một nút con bên phải p
int InsertRight(NodePtr p, int x)
{
if (p == NULL) return FALSE;
if (p->right != NULL) return FALSE;
p->right = CreateNode(x);
return TRUE;
}
Nguyễn Hà Giang - 2008
21
Binary Tree
DeleteLeft: xoá nút con bên trái của p, nút này
phải là nút lá
int DeleteLeft(NodePtr p)
{
NodePtr q;
int value;
if (p == NULL) return -1;
q = p->left;
if (q == NULL) return -1;
if (q->left != NULL || q->right !=NULL)
return -1;
value = q->info;
p->left = NULL;
FreeNode(q);
return value;
}
Nguyễn Hà Giang - 2008
22
Binary Tree
PreOrder: xuất theo thứ tự trước
void PreOrder(NodePtr pTree)
{
if (pTree != NULL)
{
printf(“%d ”, pTree->info);
PreOrder(pTree->left);
PreOrder(pTree->right);
}
}
Nguyễn Hà Giang - 2008
23
Binary Tree
InOrder
void InOrder(NodePtr pTree)
{
if (pTree != NULL)
{
InOrder(pTree->left);
printf(“%d ”, pTree->info);
InOrder(pTree->right);
}
}
Nguyễn Hà Giang - 2008
24
Binary Tree
PostOder
void PostOrder(NodePtr pTree)
{
if (pTree != NULL)
{
PostOrder(pTree->left);
PostOrder(pTree->right);
printf(“%d ”, pTree->info);
}
}
Nguyễn Hà Giang - 2008
25
