Bài giảng Cấu trúc dữ liệu 1: Chương 4A của Huỳnh Cao Thế Cường

Ạ Ọ Ạ Ọ

ƯỜ ƯỜ

NG Đ I H C AN GIANG NG Đ I H C AN GIANG Ậ Ậ

Ệ Ệ

TR TR Ỹ Ỹ

ƯỜ ƯỜ

KHOA K THU T CÔNG NGH MÔI TR KHOA K THU T CÔNG NGH MÔI TR

NG NG

Ữ Ệ Ữ Ệ

Ấ Ấ

C U TRÚC D LI U 1 C U TRÚC D LI U 1

ả

ụ

Gi ng viên ph trách: Ỳ

Ế ƯỜ

ộ

HU NH CAO TH C ọ B môn Tin h c

email: hctcuong@agu.edu.vn

11

CẤU TRÚC CÂY (TREES)

ữ ơ ả

ừ ượ

ng cây

ị

Các thu t ng c b n trên cây ậ Ki u d li u tr u t ể ữ ệ  Cài đ t cây ặ  Cây nh phân  Cây tìm ki m nh phân ế

2

CÁC THUẬT NGỮ CƠ BẢN TRÊN CÂY CÁC THUẬT NGỮ CƠ BẢN TRÊN CÂY

Cây là m t t p h p các ph n t

g i là nút (nodes), trong

ợ ượ

ầ ử ọ ệ ọ

ố

ộ ậ ộ đó có m t nút đ

c phân bi

ị

M i quan h

t g i là nút g c (root). ệ ệ cha con (parenthood): đ xác đ nh h ể

ấ

th ng c u trúc trên các nút.

ố ố ỗ

ộ

ố

ấ

ừ

ộ

ể

ỗ

ễ

ậ

ể ệ

ượ ố ở

ượ ở

ở

ợ trong t p h p đang xét ướ nút c c n i b i

M i nút, tr nút g c, có duy nh t m t nút cha. M t nút ặ ề có th có nhi u nút con ho c không có nút con nào. M i nút bi u di n m t ph n t ầ ử ộ M i ố quan h cha con ễ ể c bi u di n theo qui đ ướ và đ cha i dòng d dòng trên nút con ẳ . ạ ộ m t đo n th ng

3

Các thuật ngữ cơ bản Các thuật ngữ cơ bản

ộ ơ ộ

ị  M t nút đ n đ c là m t cây. Nút này cũng chính là nút

ộ  Gi

1,.., Tk v i ớ ự

ộ ố ươ ứ ng ng là n

1,..,

ể ủ ộ

ớ ằ ớ

ượ ộ

ỗ

Đ nh nghĩa ộ ố ủ g c c a cây. ả ử ơ s ta có n là m t nút đ n đ c và k cây T 1,.., nk thì có th xây d ng các nút g c t m t cây m i b ng cách cho nút n là cha c a các nút n ố 1,.., Tk nk. Cây m i này có nút g c là nút n và các cây T ậ ỗ ượ ọ c coi là m t c g i là các cây con. T p r ng cũng đ đ ệ ọ cây và g i là cây r ng kí hi u .

4

Các thuật ngữ cơ bản Các thuật ngữ cơ bản

5

Các thuật ngữ cơ bản Các thuật ngữ cơ bản

ỗ

i+1, v i i=1..k1, thì chu i này g i là m t

ắ

ọ

ọ ng đi ) t

n

i là nút ộ ừ 1 đ n ế

ượ ị ư ậ

ừ ộ

ộ

ế

đ ng đi tr 1. Nh v y đ dài đ

ố ằ c đ nh nghĩa b ng s nút trên ườ ng đi t

m t nút đ n

N u nế ộ 1,.., nk là m t chu i các nút trên cây sao cho n ỗ ớ ủ cha c a nút n ườ ườ đ ng đi trên cây (hay ng n g n là đ nk. Đ dài đ ườ ộ ng đi ừ ườ đ ằ chính nó b ng không.

6

Các thuật ngữ cơ bản Các thuật ngữ cơ bản

a là ti n b i

ủ

ừ h u duậ ệ ọ ề ố (ancestor) c a b, còn b g i là ế ừ ườ nút a đ n nút b ng đi t ệ ủ ậ

ộ ớ ủ ế (descendant) c a nút a: N u có đ  m t nút v a là ti n b i v a là h u du c a chính nó ố ừ .  Ti n b i ho c h u du c a m t nút khác v i chính nó ệ ủ

ố ề ề ặ ậ ố

ậ

ộ

ộ ề ệ ự ự ặ ậ ọ g i là ti n b i ho c h u du th c s .  Trên cây nút g c ố không có ti n b i th c s . ự ự ố ề nút lá (leaf): là nút không có h u du th c s . ệ ự ự ậ nút trung gian (interior): Là nút không ph i là lá ả Cây con c a m t cây là m t nút cùng v i t ớ ấ ả

t c các h u

ủ ệ ủ du c a nó.

7

Các thuật ngữ cơ bản Các thuật ngữ cơ bản

ủ

ộ

ườ

ấ ừ

: đ dài đ

ớ ng đi l n nh t t

nút

Chi u cao c a m t nút

đó t

ề ớ ề

ủ

ộ

ủ : chi u cao c a nút g c. ườ

ề ộ

: đ dài đ

ố ố ế ừ nút g c đ n nút

ng đi t

i lá. Chi u cao c a cây Đ sâu c a m t nút ủ

ộ đó.

ộ ộ

ọ

Các nút có cùng m t đ sâu i ta g i là các nút có cùng

ứ

ố ở ứ ủ m c 0, các nút con c a

ố ở ứ

ộ m t m c i.  Theo đ nh nghĩa này thì nút g c m c 1.

ị nút g c

8

Các thuật ngữ cơ bản Các thuật ngữ cơ bản

Th t ứ ự ế

các nút trong cây ệ

ứ ự ủ

ứ ự các nút con c a cùng m t nút thì ướ ừ c t ộ trái sang qui t th t cây có th tứ ự, th t

ứ ự  N u ta phân bi ọ cây g i là ph i.ả  Trong tr t rõ ràng th t các

ườ ng h p ta không phân bi ọ ệ ợ cây không có th tứ ự.

ộ ọ nút thì ta g i là • Các nút con cùng m t nút cha g i là các nút anh em

ộ

ru t (siblings). ệ

ở ộ ộ ế ắ

ệ ủ ậ

• Quan h "trái sang ph i" c a các anh em ru t có th ể ủ ả ấ ỳ m r ng cho hai nút b t k theo qui t c: n u a, b là ộ hai anh em ru t và a bên trái b thì các h u du c a a ệ ủ ọ ậ là "bên trái" m i h u du c a b.

9

Các thuật ngữ cơ bản Các thuật ngữ cơ bản

10

Các thuật ngữ cơ bản Các thuật ngữ cơ bản

ọ

Các th t

ệ ộ

ứ ự ệ

duy t cây quan tr ng  Duy t cây là m t qui t c cho phép đi qua l n l ắ

ủ ộ ầ

ọ ỗ ặ đi qua g i là danh sách duy t cây.

ầ ượ ấ ả t c t t ệ t kê các nút c a cây m i nút đúng m t l n, danh sách li ứ ị ứ các nút (tên nút ho c giá tr ch a bên trong nút) theo th ệ ự t  Có ba cách duy t cây quan tr ng ọ : ệ • Duy t ti n t ệ ề ự (preorder) NLR • Duy t trung t ự (inorder) LNR ệ • Duy t h u t ệ ậ ự (posorder) LRN

11

Các thuật ngữ cơ bản Các thuật ngữ cơ bản

ổ

ộ

Đ nh nghĩa các phép duy t cây t ng quát m t cách đ ệ ệ

ượ ỗ

ể

, h u t ồ ỉ

ể

ị qui:  Cây r ng thì danh sách duy t cây là r ng và nó đ ỗ ệ c ự ậ ự ủ ệ ề ự ứ , trung t coi là bi u th c duy t ti n t c a cây.  Cây ch có m t nút thì danh sách duy t cây g m ch ỉ ệ ộ ệ ề ự ứ c coi là bi u th c duy t ti n t

ộ m t nút đó và nó đ ự ậ ự ủ trung t ượ c a cây. , h u t

12

Các thuật ngữ cơ bản Các thuật ngữ cơ bản

ố

ả ử

Ng

s cây T có nút g c là n và có các cây con

ệ c a cây T là li t kê nút n

ượ ạ i: gi c l là T1,..,Tn thì:  Bi u th c duy t ti n t ể

ệ ề ự ủ , k ế c a các cây T1, T2, .., ứ bi u th c duy t ti n t

ứ ự ể ế ti p là Tn theo th t

ứ duy t ệ ứ nút n r i đ n bi u th c

ể trung t ệ duy t trung t

 Bi u th c duy t h u t

ứ ự ể c a cây T là bi u th c ể ồ ế ứ ự đó. theo th t ứ duy t ệ c a cây T là bi u th c ồ ế đó r i đ n ể theo th t ệ ề ự ủ ứ đó.  Bi u th c duy t trung t ệ ứ ự ủ ự ủ ế ế k ti p là c a cây T1, ự ủ c a các cây T2,.., Tn ệ ậ ự ủ ứ c a các cây T1, T2,.., Tn,

ể ậ ự ủ h u t nút n.

13

Các thuật ngữ cơ bản Các thuật ngữ cơ bản

ứ ứ ứ

ể ể ể

 Bi u th c duy t ti n t ệ ề ự : A B C D E F H K L  Bi u th c duy t trung t ự ệ : C B E D F A K H L  Bi u th c duy t h u t ệ ậ ự : C E F D B K L H A

14

Các thuật ngữ cơ bản Các thuật ngữ cơ bản

Cây có nhãn và cây bi u th c ứ ư

ộ nhãn (label) ho c còn

ớ

ể ữ ế ợ ng l u tr k t h p m t ộ giá tr (value) ộ ị ả

ủ ị ượ ư v i m t nút c a cây. c l u gi ặ (nhãn c a ủ ữ ạ i nút t

 Ta th ườ ọ g i là m t ộ m t nút không ph i là tên nút mà là giá tr đ đó)

ộ ủ ượ ọ c g i là khóa c a  Nhãn c a m t nút đôi khi còn đ

ị ồ i nút

ư ộ

ủ ỗ ụ ủ

ữ ạ ầ ủ ộ ề ị ỉ

ọ ặ ọ ể ặ ỳ

ế ậ ả ị ủ ấ . ệ nút, tuy nhiên hai khái ni m này là không đ ng nh t • Nhãn là giá tr hay n i dung l u tr t ộ • Khoá c a nút có th ch là m t ph n c a n i dung. ể ỉ  Ví d : m i nút cây ch a m t record v thông tin c a ộ ứ sinh viên (MSSV, h tên, ngày sinh, đ a ch ,...) thì khoá có th là MSSV ho c h tên ho c ngày sinh tu theo giá tr nào ta đang quan tâm đ n trong gi i thu t.

15

Các thuật ngữ cơ bản Các thuật ngữ cơ bản

ụ

ễ

ể

Ví d : Cây bi u di n bi u

ắ ễ ộ

ể ạ ể

ứ th c (a+b)(ac)  n1, n2,.., n7 là các tên nút và ,+,,a,b,c là các nhãn.  Qui t c bi u di n m t bi u ể ể ứ ọ th c toán h c trên cây: • M i nút lá có nhãn bi u ộ di n cho m t toán h ng. • M i nút trung gian bi u

ỗ ễ ỗ ễ ộ di n m t toán t ử .

16

Các thuật ngữ cơ bản Các thuật ngữ cơ bản

ọ ứ ể ệ Khi duy t m t cây bi u di n m t bi u th c toán h c và ễ

ộ ứ ự t kê nhãn c a các nút theo th t

ể ệ duy t thì: ớ ươ ứ ng ng v i phép ề ố (prefix) t

ủ duy t ti n t

ươ ứ ố (infix) t ớ ng ng v i phép

ủ duy t trung t

ươ ứ ậ ố (posfix) t ớ ng ng v i phép

ủ ộ ủ ệ li  Bi u th c d ng ti n t ứ ạ ể ệ ề ự c a cây.  Bi u th c d ng trung t ể ứ ạ ự c a cây. ệ  Bi u th c d ng h u t ứ ạ ể ệ ậ ự c a cây.

duy t h u t ố ớ ướ slide tr c, ta có:

ể ể ể Ví d : ụ đ i v i cây trong hình ở  Bi u th c ti n t ứ ề ố : *+abac  Bi u th c trung t ố ứ : a+b*ac  Bi u th c h u t ứ ậ ố : ab+ac*

17

KiỂU DỮ LIỆU TRỪU TƯỢNG CÂY KiỂU DỮ LIỆU TRỪU TƯỢNG CÂY

Các phép toán trên cây

ố ủ ị

ế

 Hàm PARENT(n,T) cho nút cha c a nút n trên cây T, ế ặ ụ n u n là nút g c thì hàm cho giá tr NULL (cài đ t c ị ộ ể th thì NULL là m t giá tr nào đó).  Hàm LEFTMOST_CHILD(n,T) cho nút con trái nh t ấ ị ủ c a nút n trên cây T, n u n là lá thì hàm cho giá tr NULL.

ộ ả ế ộ

ị  Hàm RIGHT_SIBLING(n,T) cho nút anh em ru t ph i ả nút n trên cây T, n u n không có anh em ru t ph i thì hàm cho giá tr NULL.

18

Kiểu dữ liệu trừu tượng Cây Kiểu dữ liệu trừu tượng Cây

ủ i nút n c a cây T.

ố ủ ế

 Hàm LABEL_NODE(n,T) cho nhãn t ạ  Hàm ROOT(T) tr ra nút g c c a cây T. N u Cây T ả ả ề ỗ r ng thì hàm tr v NULL.

ớ ủ ụ ạ

ố  Hàm CREATEi(v,T1,T2,..,Ti),v i i=0..n, th t c t o ượ c gán nhãn v và có i cây con

ỉ ồ ớ

ủ ụ ạ đ n đ c là n có nhãn v.

ớ cây m i có nút g c là n đ T1,..,Ti. • N u n= 0 thì th t c t o cây m i ch g m có 1 nút ế ộ ơ • Gi ả ử s ta có hai cây con T1 và T2, ta mu n thi

ố ờ ọ ớ ớ ế ậ t l p ủ ụ ẽ i g i th t c s

ố cây m i v i nút g c có nhãn là v thì l là CREATE2(v,T1,T2).

19

CÀI ĐẶT CÂY

ằ

ặ

ả

ể

ễ

ằ

ặ

Cài đ t cây b ng m ng Bi u di n cây b ng danh sách các con ằ Cài đ t cây b ng con tr ỏ

20

Cài đặt cây bằng mảng

Cho cây T có n nút

ầ ượ t là 0,1, 2, .., n1.

ể ư ề ả ộ

ữ ế ủ  Gán tên cho các nút l n l  Dùng m t m ng m t chi u A đ l u tr cây b ng cách ằ nút g cố . N u i là

ố ộ cho A[i] = j v i ớ j là nút cha c a nút i ta cho a[i] = 1 vì nút g c không có cha.

ể ộ

ề ế ộ ứ ủ ằ

ứ ớ

 ho c khai báo m ng a là m ng c a các struct có hai

ườ  N u cây T là cây có nhãn ta có th dùng thêm m t m ng ả m t chi u th hai L ch a các nhãn c a cây b ng cách ủ cho L[i] = x v i x là nhãn c a nút i ủ ả ả ữ ỉ ố ch s nút cha; tr ng Parent gi

ườ ủ ộ ườ ữ ố ng MaxNode gi ng Data s nút

ặ ườ tr ữ gi ệ ạ hi n t ng: tr nhãn c a nút và m t tr i đang có trên cây.

21

Cài đặt cây bằng mảng

ố ư ữ ư ế  V i cách l u tr nh th , hàm

ặ ả ố

ẳ ấ

c. ướ ệ ặ ể ạ ệ c vi c đ t tên cho

ố i nút g c.

ượ ắ ầ ạ ầ c các nút con.

tăng d n b t đ u t ố ướ ộ ố ầ ượ ượ c đánh s l n l t

ớ ỉ PARENT(n,T) t n ch ỏ ờ ộ ằ m t h ng th i gian trong khi các hàm đòi h i thông tin ể ệ ố ề v các con không làm vi c t t vì ph i t n vòng l p đ ộ ạ dò tìm. Ch ng h n cho m t nút i tìm nút con trái nh t ị ủ ượ c a nút i là không th xác đ nh đ  Đ c i thi n tình tr ng này ta qui ể ả ố ứ ự các nút (đánh s th t ) nh sau: • Đánh s theo th t ứ ự ố • Nút cha đ c đánh s tr • Các nút con cùng m t nút cha đ ả trái sang ph i ừ t

22

23

Cài đặt cây bằng mảng

ữ ệ

ỉ ố ố

ủ

ả

i đa c a m ng */

Khai báo c u trúc d li u ấ #define MAXLENGTH ... /* ch s t #define NIL 1 typedef ... DataType; typedef int Node;

24

Cài đặt cây bằng mảng

typedef struct { ư

ữ

ữ ệ

ủ

ắ

/* L u tr cha c a các nút trong cây theo nguyên t c: Cha c a nút i

ả

ữ ư ẽ ư ở ị s l u

v trí i trong m ng */

ố

/* L u tr nhãn (d li u) c a nút trong cây */ DataType Data[MAXLENGTH];

Node Parent[MAXLENGTH]; // S nút th c s trong cây int MaxNode; ự ự } Tree;

Tree T;

25

Cài đặt cây bằng mảng

ở ạ

Kh i t o cây r ng:

ỗ void MakeNull_Tree (Tree *T) {

(*T).MaxNode=0;

}

ỗ

ể

Ki m tra cây r ng

int EmptyTree(Tree T) {

return T.MaxNode == 0;

}

26

Cài đặt cây bằng mảng

ủ

ị

Xác đ nh nút cha c a nút trên cây

Node Parent(Node n,Tree T) {

if (EmptyTree(T) || (n>T.MaxNode1))

return NIL;

else

return T.Parent[n];

}

27

Cài đặt cây bằng mảng

ị

ủ

Xác đ nh nhãn c a nút trên cây DataType Label_Node(Node n,Tree T)

{

if (!EmptyTree(T) && (n<=T.MaxNode1))

return T.Data[n];

}

28

Cài đặt cây bằng mảng

ố

ị

Hàm xác đ nh nút g c trong cây Node Root(Tree T)

{

if (!EmptyTree(T)) return 0; else return NIL;

}

29

Cài đặt cây bằng mảng

ị ấ ủ ộ

Hàm xác đ nh con trái nh t c a m t nút Node LeftMostChild(Node n,Tree T) { Node i;

ủ ầ ọ ị

int found; if (n<0) return NIL; i=n+1; /* V trí nút đ u tiên hy v ng là con c a nút n */ found=0; while ((i<=T.MaxNode1) && !found)

ấ ủ

if (T.Parent[i]==n) found=1; //con trái nh t c a nút n else i=i+1; if (found) return i; else return NIL;

}

30

Cài đặt cây bằng mảng

ị

ả ủ

ộ

Hàm xác đ nh anh em ru t ph i c a m t nút Node RightSibling(Node n,Tree T) {

Node i,parent; int found; if (n<0) return NIL; parent=T.Parent[n]; i=n+1; found=0;

31

Cài đặt cây bằng mảng

while ((i<=T.MaxNode1) && !found)

if (T.Parent[i]==parent) found=1;

else i=i+1;

if (found) return i; else return NIL;

}

32

Cài đặt cây bằng mảng

ủ ụ

ệ ề ự

Th t c duy t ti n t void PreOrder(Node n,Tree T) {

Node i; printf("%c ",Label_Node(n,T)); i=LeftMostChild(n,T); while (i!=NIL) { PreOrder(i,T);

i=RightSibling(i,T);

}

33

Cài đặt cây bằng mảng

ệ ủ ụ ự

Th t c duy t trung t void InOrder(Node n,Tree T) { Node i;

i=LeftMostChild(n,T); if (i!=NIL) InOrder(i,T); printf("%c ",Label_Node(n,T)); i=RightSibling(i,T); while (i!=NIL)

Bài giảng Cấu trúc dữ liệu 1: Chương 4A - Huỳnh Cao Thế Cường

Chương 2 cung cấp kiến thức về cấu trúc cây (trees). Chương này gồm có những nội dung chính sau: Các thuật ngữ cơ bản trên cây, kiểu dữ liệu trừu tượng cây, cài đặt cây, cây nhị phân, cây tìm kiếm nhị phân. Mời các bạn tham khảo.

Chủ đề:

Cấu trúc dữ liệu