Cộng đồng chia sẻ tri thức Lib24.vn

Chương 6: Cấu trúc cây - Cô Võ Thị Hường

4af38973cb696dd240cc8397ff5d113a
Gửi bởi: Võ Thị Hường 10 tháng 9 2020 lúc 9:57 | Được cập nhật: 24 tháng 2 lúc 17:50 Kiểu file: PDF | Lượt xem: 110 | Lượt Download: 0 | File size: 1.033343 Mb

Nội dung tài liệu

Tải xuống
Link tài liệu:
Tải xuống

Các tài liệu liên quan


Có thể bạn quan tâm


Thông tin tài liệu

Chương 6
CẤU TRÚC CÂY

NỘI DUNG


Các khái niệm cơ bản



Cây nhị phân



Cây tổng quát

2/51

4.1 CÁC KHÁI NIỆM CƠ BẢN


Định nghĩa cây



Cấp của cây



Mức của cây



Đường đi và độ dài đường đi trong cây



Độ cao, độ sâu của nút trong cây



Thứ tự các nút trong cây



Phép duyệt cây



Cây gán nhãn và cây biểu thức

3/51

4.1.1 Định nghĩa cây


Cây là tập hợp hữu hạn các nút trong đó có một nút đặc

biệt gọi là gốc của cây(root). Các nút có mối quan hệ
phân cấp gọi là quan hệ ‘’cha-con’’


Định nghĩa đệ qui về cây



Một nút là một cây gốc của cây chính là nút đó.
Giả sử T1, T2, …, Tn (n  1) là các cây có gốc tương

ứng r1, r2,…, rn. Khi đó cây T với gốc r được hình
thành bằng cách cho r trở thành nút cha của các nút
r1, r2,…, rn
4/51

4.1.1 Định nghĩa cây
T

T1

r1

T2

r

r2



rn

Tn

5/51

4.1.2 Cấp của cây


Cấp của nút trong cây là số con của nút



Cấp của cây: Là cấp cao nhất của nút có trong cây.



Cây có cấp n thì gọi là cây n - phân

6/51

4.1.3 Mức của cây


Gốc của cây có mức là 1



Cha có mức là i thì con có mức là i+1



Mức của cây là mức cao nhất của nút có trong cây

7/51

4.1.4 Đường đi và độ dài đường đi


Dãy các nút n1, n2, ..., nk được gọi là một đường đi
trong cây T nếu ni là cha của ni+1 (1  i < k) có độ dài là
k-1



Nếu có một đường đi từ A đến B trong cây T thì A được
gọi là tiền thân của B, B được gọi là hậu thế của A



Trong một cây, gốc là nút không có tiền thân, lá là nút
không có hậu thế
8/51

4.1.5 Độ cao và độ sâu của nút


Độ cao của một nút trong cây là số nút trong đường đi
dài nhất từ nút đó tới lá



Độ cao của cây là độ cao của nút gốc



Độ sâu của một nút trong cây là số nút trong đường đi
từ gốc tới nút đó

9/51

4.1.6 Thứ tự các nút trong cây


Trong cây nếu nút n có các con là n1, n2,..., nk thì


ni (1<=i<=k) là các nút anh em



n1 là con bên trái cùng hay con trưởng



nk là con bên phải cùng hay con út



ni (1<=i


ni (1
10/51

4.1.6 Thứ tự các nút trong cây



Trong cây nếu không tính tới thứ tự của các nút gọi là
cây không có thứ tự
T1

B

T2

A

C

A

C



Nếu là các cây có thứ tự thì T1<>T2



Nếu là các cây không có thứ tự thì T1=T2

B

11/51

4.1.7 Phép duyệt cây


Là phép thăm các nút trong cây một cách hệ thống sao
cho tất cả các nút đều được thăm và được thăm đúng
một lần



Có 3 cách duyệt cây cơ bản :


Duyệt cây theo thứ tự trước (preorder)



Duyệt cây theo thứ tự giữa (inorder)



Duyệt cây theo thứ tự sau (postorder )

12/51

4.1.7 Phép duyệt cây


Duyệt cây theo thứ tự trước (preorder)
Nếu cây khác rỗng


Thăm gốc



Duyệt cây con trái theo thứ tự trước



Duyệt cây con phải theo thứ tự trước

13/51

4.1.7 Phép duyệt cây
A

B

E

F

C

G

H

D

I

K

14/51

4.1.7 Phép duyệt cây


Duyệt cây theo thứ tự giữa (inorder)
Nếu cây khác rỗng


Duyệt cây con trái theo thứ tự giữa



Thăm gốc



Duyệt cây con phải theo thứ tự giữa

15/51

4.1.7 Phép duyệt cây
A

B

E

F

C

G

H

D

I

K

Giữa: EBFGAHCIDK
Sau: EFGBHCIKDA
Trước: ABEFGCHDIK
16/51

4.1.7 Phép duyệt cây


Duyệt cây theo thứ tự sau (postorder)
Nếu cây khác rỗng


Duyệt cây con trái theo thứ tự sau



Duyệt cây con phải theo thứ tự sau



Thăm gốc

17/51

4.1.7 Phép duyệt cây
A

B

E

F

C

G

H

D

I

K

Thứ tự trước : ABEFGCHDIK
Thứ tự giữa :

EBFGAHCIDK

Thứ tự sau :

EFGBHCIKDA
18/51

4.1.8 Cây gán nhãn và cây biểu thức


Cây gán nhãn : Mỗi nút trong cây được gán với một
nhãn



Cây biểu thức : Mỗi nút trong cây được gán với một

thành phần của biểu thức theo cách


Mỗi nút lá được gán với một toán hạng



Mỗi nút trong được gán với một toán tử

19/51

4.1.8 Cây gán nhãn và cây biểu thức


Ví dụ cây biểu thức P = a*(b - c) + d/e
+
/

*

a

-

b



d

e

c

Duyệt theo thứ tự trước :
Duyệt theo thứ sau :

+*a-bc/de
abc-*de/+
20/51

4.2 CÂY NHỊ PHÂN


Khái niệm, đặc điểm, tính chất



Biểu diễn cây nhị phân



Cây nhị phân tìm kiếm

21/51

4.2.1 Khái niệm, đặc điểm, tính chất





Là dạng đặc biệt của cây. Mỗi nút trong có tối đa 2 con,
phân biệt con bên trái và con bên phải của nút
Là cây có thứ tự
Các dạng cây nhị phân đặc biệt


Cây nhị phân suy biến

22/51

4.2.1 Khái niệm, đặc điểm, tính chất


Các dạng cây nhị phân đặc biệt
 Cây nhị phân hoàn chỉnh : Các mức đều đạt tối đa số
nút trừ mức cao nhất trong cây

23/51

4.2.1 Khái niệm, đặc điểm, tính chất


Các dạng cây nhị phân đặc biệt
 Cây nhị phân hoàn chỉnh đầy đủ : Các mức đều đạt tối
đa số nút

24/51

4.2.1 Khái niệm, đặc điểm, tính chất


Trong cây nhị phân


Số lượng nút tối đa ở mức i là 2i-1



Số lượng nút tối đa ở cây nhị phân mức i 2i – 1



Trong các cây nhị phân có cùng số nút thì cây nhị
phân suy biến có chiều cao lớn nhất, cây nhị phân
hoàn chỉnh, hoàn chỉnh đầy đủ có chiều cao nhỏ nhất

25/51

4.2.2 Biểu diễn cây nhị phân


Biểu diễn bằng mảng



Biểu diễn bằng con trỏ

26/51

4.2.2 Biểu diễn cây nhị phân


Biểu diễn bằng mảng : Dùng mảng một chiều
làm cấu trúc lưu trữ.


Cách 1 : Gốc lưu ở vị trí 0, cha lưu ở vị trí i thì con trái

lưu ở vị trí 2*i+1, con phải lưu ở vị trí 2*i+2


Các cách khác : (Giới thiệu trong biểu diễn cây tổng

quát
Ví dụ :
27/51

4.2.2 Biểu diễn cây nhị phân
A



Biểu diễn bằng mảng
B

C


D

A

B

0

1

C
2

3

4

5

6

D

E

...

7 …

15



28/51

4.2.2 Biểu diễn cây nhị phân



Biểu diễn bằng con trỏ
Mỗi nút trong cây là một bản ghi gồm có 3 trường

left

data

right

data chứa thông tin của nút
 left là một con trỏ trỏ vào con bên trái của nút
 right là một con trỏ trỏ vào con bên phải của nút
Cây là con trỏ trỏ vào nút gốc




29/51

4.2.2 Biểu diễn cây nhị phân


Ví dụ

A

B

NULL



D

NULL

NULL

C

E

NULL

NULL

F

NULL

NULL

G

NULL

Nhận xét : Cây nhị phân có n nút thì có 2*n con trỏ
Trong đó n-1 con trỏ khác NULL
n+1 con trỏ NULL
30/51

4.2.3 Cây nhị phân tìm kiếm


Định nghĩa, khai báo cấu trúc dữ liệu



Các phép toán cơ bản

31/51

Định nghĩa cây nhị phân tìm kiếm



Là cây nhị phân đặc biệt dùng để lưu trữ và tìm kiếm
thông tin



Khóa của nút cha không nhỏ hơn khóa của nút con bên
trái và không lớn hơn khóa của nút con bên phải

32/51

Khai báo cấu trúc dữ liệu

struct node
{

key ;
node *left, *right ;

} *t;

33/51

Các phép toán cơ bản



Khởi tạo cây t rỗng : creat(t)



Kiểm tra cây t rỗng : empty(t)



Chèn khóa x vào cây t : insert(x,t)



Loại khóa x trong cây t : del(x,t)



Duyệt cây t theo 3 cách duyệt cơ bản

34/51

Các phép toán cơ bản



Khởi tạo cây t rỗng : creat(t)

void creat(node *&t)
{
t = NULL;
}

35/51

Các phép toán cơ bản



Kiểm tra cây t rỗng : empty(t)

void empty(node *t)
{
return t == NULL;
}

36/51

Các phép toán cơ bản


Chèn khóa x vào cây t : insert(x,t)

void insert( x, node *&t)
{ if (t==NULL)
{ t =new node;
t->key=x ; t->left =NULL ; t->right =NULL ;
}

else if (xkey) insert(x,t->left)
else insert(x,t->right)
}
37/51

Các phép toán cơ bản


Loại khóa x trong cây t

Nếu t->key== x
x

38/51

Các phép toán cơ bản


Trường hợp 1 : nếu t->left==NULL
t
p
x

p=t ;
t =t->right ;
delete(p) ;

39/51

Các phép toán cơ bản


Trường hợp 2 : nếu t->right==NULL

p=t ;
t =t->right ;
delete(p) ;

p

t
x

40/51

Các phép toán cơ bản


Trường hợp 3 : Nếu t->left!=NULL, t->right!=NULL
t

p=t->left
Nếu p->right==NULL

p

q
x

41/51

Các phép toán cơ bản


Trường hợp 3 : nếu t->left!=NULL, t->right!=NULL
t

p
p=t->left
Nếu p->right!=NULL

max

s

q

max

42/51

Các phép toán cơ bản


Nếu t->key!=x
if (t->key>x) del(x,t->left) ;
else del(x,t->right);
!x

43/51

Các phép toán cơ bản


Loại khóa x trong cây t : del(x,t)

void del( x, node *&t)
{ node *p,*q,*s;
if (t!=NULL)
{ if (t->key==x)
if (t->left==NULL)
{ p=t; t =t->right; delete(p);}
else if (t->right==NULL)
{ p=t; t =t->left; delete(p);}
else
44/51

Các phép toán cơ bản
else
{ p=t->left;
if (p->right==NULL)
{p->right=t->right;q=t; t=p; delete q;}
else { s=p;
while (s->right->right!=NULL) s=s->right;
t->key=s->right->key; q=s->right;
s->right = s->right->left; delete q;
}
}
else if (t->key>x) del(x,t->left) ;
else del(x,t->right);
}

}
45/51

Các phép toán cơ bản


Duyệt cây t theo thứ tự trước

void hienpre(node * t)
{ if (t!=NULL)
{ cout<key<<“ “ ;
hienpre(t->left) ;
hienpre(t->right) ;
}
}
46/51

Các phép toán cơ bản


Duyệt cây t theo thứ tự giữa

void hienin(node * t)
{ if (t!=NULL)
{ hienin(t->left) ;
cout<key<<“ “ ;
hienin(t->right) ;
}
}
47/51

Các phép toán cơ bản


Duyệt cây t theo thứ tự sau

void hienpost(node * t)
{ if (t!=NULL)
{ hienpost(t->left) ;
hienpost(t->right) ;
cout<key<<“ “ ;
}
}
48/51