Đồ án cơ sở chuyên ngành phần mềm: Quản lý sinh viên bằng cây nhị phân

TR

I H C DUY TÂN

NG Đ

ƯỜ

Ạ Ọ KHOA CÔNG NGHÊ THÔNG TIN

̣

ĐÔ AN

́ C SƠ Ở

̀

CHUYÊN NGANH CÔNG NGH PH N M M

Ầ

Ệ

Ề

̀

TÊN Đ TÀI

Ề

SINH VIÊN QU N LÝ Ả B NGẰ CÂY NH PHÂN Ị

hs. NGUY N T N THU N

Ậ

Ễ

Giáo viên h Ng

ng d n: T ẫ i th c hiên:

Ấ NGUY N MINH TRUNG

ưỡ ườ ự

̣

Ễ Ma sô SV: 162123079

̃ ́

Đa Năng,4/2012

̀ ̃

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

TÊN ĐÊ TAI

̀ ̀

Chuyên nganh: Công ngh ph n m m

ệ

ề

ầ

̀

Ngay băt đâu: 10/4/2012

Ngay kêt thuc:10/5/2012

̀ ́ ̀ ̀ ́ ́

Giang viên h

ng dân: THs. Nguy n T n Thu n

ướ

ễ

ấ

ậ

̉ ̃

Sinh viên th c hiên: Nguy n Minh

Trung

Ma sô: 162123079

ự

ễ

̣ ̃ ́

Ngay nôp/ nhân xet:

̀ ̣ ̣ ́

Ngay bao vê: 29/5/2012

Trang 2

̀ ̉ ̣

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

NHÂN XET CUA GIANG VIÊN H

NG DÂN

ƯỚ

̣ ́ ̉ ̉ ̃

--------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- L I M Đ U Ờ Ở Ầ

Trang 3

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

Trong th gi i hi n nay công ngh thông tin ngày càng phát tri n v t b c và ế ớ ệ ệ ể ượ ậ

ngày càng đ t đ c thành t u to l n trong vi c phát tri n kinh t t c ạ ượ ự ệ ể ớ ế .Trên h u h t t ầ ế ấ ả

ầ lĩnh v c thì đ u có m t ngành công ngh thông tin trong đó, nó đã tr thành m t ph n ự ề ệ ặ ở ộ

thi t y u trong cu c s ng. Ch ế ế ộ ố ươ ầ ng trình tin h c ng d ng ngày càng nhi u góp ph n ọ ứ ụ ề

thay đ i cu c s ng,nâng cao kh năng chính xác và hoàn thành công vi c nhanh chóng. ộ ố ệ ả ổ

Đ có đ t phân ể ượ c nh ng ch ữ ươ ng trình nh v y đòi h i ng ư ậ ỏ ườ i làm tin h c ph i bi ọ ả ế

tích thi ế ế ệ ố ữ t k h th ng, xây d ng m t ph n m m qu n lý ng d ng đó. Và nh ng ề ự ứ ụ ầ ả ộ

ph n m m đó s tr thành nh ng công c h tr đ t l c nh m đáp ng nh ng công ụ ỗ ợ ắ ự ẽ ở ữ ữ ứ ề ằ ầ

vi c qu n lý nh nh ng công c có s n. ờ ữ ụ ệ ẵ ả

Ch ng trình qu n lý sinh viên là m t ch ươ ả ộ ươ ứ ng trình xây d ng nh m đáp ng ự ằ

ệ nh ng nhu c u qu n lý nh ghi danh , tìm ki m, l u thông tin…và r t nhi u công vi c ư ữ ư ế ề ấ ầ ả

m t cách chính xác và nhanh chóng. ộ

V i đ tài này giúp chúng ta c ng c l ớ ề ố ạ ủ i nh ng ki n th c v cây nh phân. Đ ứ ề ữ ế ị ồ

ứ án th c hi n d a trên nh ng ki n th c đã h c và tìm ki m trên internet. Do ki n th c ự ữ ự ứ ệ ế ế ế ọ

và trình đ còn non kém nên em ch a hoàn thành đ y đ các công tác qu n lý.Trong ư ủ ầ ả ộ

quá trình th c hi n n u có sai sót mong th y cô thông c m. ệ ế ự ầ ả

CH

NG I:

ƯƠ

Trang 4

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

C S LÝ THUY T

Ơ Ở

Ế

1.1. Lý thuy t đ quy

ế ệ

1.1.1 Khái ni m:ệ

a. Đ quy: ệ

M c dù lý thuy t đ quy đã t n t i r t lâu t ế ệ ồ ạ ấ ặ ừ ể khi toán h c ra đ i và phát tri n ọ ờ

nh ng nó ch cho th y t m quan tr ng và ng d ng c a mình khi con ng ọ ấ ầ ư ứ ụ ủ ỉ ư i phát minh ờ

ra máy vi tinh và tin h c. Trong toán tin m t đ i t ng là đ quy n u nó đ ộ ố ượ ọ ệ ế ượ c đ nh ị

nghĩa qua chính nó ho c m t đ i t ộ ố ượ ặ ạ ạ

vd: Công th c truy h i c a dãy fibonacci.n ng khác cùng d ng b ng quy n p. ằ ˛ N N u n=0 ho c n=1 thì F n=1, n u n>1 thì ồ ủ ứ ế ế ặ

Fn=Fn-1+Fn-2

b. Thu t toán đ quy trong tin h c: ọ ệ ậ

Thu t toán đ quy là m t thu t ng tin h c ch các b c th c hi n gi i bài ữ ệ ậ ậ ộ ọ ỉ ướ ự ệ ả

ng nào đó b ng đ quy.M t bài toán gi c thông qua cách xác toán, ho c đ i t ặ ố ượ ệ ằ ộ i đ ả ượ

ng h p đ c bi t và tính quy n p c a nó đ c g i là bài toán đ quy. đ nh nh ng tr ị ữ ườ ặ ợ ệ ạ ủ ượ ệ ọ

Nói cách khác gi i m t bài toán đ quy là vi c chia nh l i gi ả ỏ ờ ệ ệ ộ ả i thành nh ng bài toán ữ

ng” d gi i h n.Và thu t toán t ng ng v i l i gi i nh v y g i là con “t m th ầ ườ ễ ả ơ ậ ươ ớ ờ ứ ả ư ậ ọ

thu t toán đ quy. ệ ậ

c. C u trúc c a thu t toán đ quy: ủ ệ ấ ậ

Đ nh nghĩa m t hàm đ quy g m hai ph n: ệ ầ ộ ồ ị

- Ph n neo: Xác đ nh nh ng tr ng h p đăc bi t c a bài toán, đ i t ng.Là ữ ầ ị ườ ợ ệ ủ ố ượ

ph n th c hi n nh ng công vi c r t đ n gi n, có th gi ệ ấ ơ ữ ự ể ệ ả ầ ả ự ầ i tr c ti p mà không c n ế

đ n bài toán con nào c . Ph n này cũng quy t đ nh tính h u h n c a thu t toán. ế ữ ạ ủ ế ị ậ ả ầ

- Ph n đ quy: Đ g i đ quy nh ng bài toán con và ph i h p chúng l ữ ể ọ ệ ố ợ ệ ầ ạ ằ i nh m

tìm ra l i gi i chính trong tr ng h p ch a gi c b ng ph n neo. i đ ờ ả ườ ư ợ ả ượ ằ ầ

vd: Trong công th c c a dãy fibonacci ph n neo là tr ứ ủ ầ ườ ể ọ ng h p n=0 và n=1,ph n đ g i ầ ợ

Trang 5

đ quy chính là công th c F ệ ứ n=Fn-1+Fn-2.

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

d.Các lo i đ quy ạ ệ : Có 2 lo i: Đ quy tr c ti p và đ quy gián ti p ế ự ế ệ ệ ạ

- Đ quy tr c ti p là lo i đ quy mà đ i t ng đ c mô t tr c ti p qua nó: A ự ế ạ ệ ố ượ ệ ượ ả ự ế

mô t qua B, C,.. trong đó B, C, … không ch a A. ả ứ

- Đ quy gián ti p là lo i đ quy mà đ i t ng đ c mô t gián ti p qua nó: A ạ ệ ố ượ ế ệ ượ ả ế

i đ

1, A2, …, An. Trong đó có m t Aộ

mô t qua A c mô t qua A. ả ượ ả

1.1.2. u và nh Ư

ượ

c đi m c a thu t toán đ quy: ậ

ủ

ệ

ể

Bên c nh nhi u gi i thu t khác nh gi ề ạ ả ư ả ặ i l p, quy ho ch đ ng, vét c n...đ quy ộ ệ ạ ậ ạ

v n là m t công c r t h u ích đ x lý các s li u.M t u đi m quan tr ng là không ẫ ụ ấ ữ ố ệ ể ử ộ ư ể ộ ọ

gi i h n s vòng l p nên s m r ng đ ớ ạ ố ẽ ở ộ ặ ượ c kh năng x lý s li u đ u vào.Ngoài ra, ố ệ ử ả ầ

ng mà vi c xây thu t toán đ quy đ n gi n h n nhi u so v i các các có nhi u đ i t ề ố ượ ệ ệ ề ậ ả ơ ơ ớ

thu t toán khác nh l p. ư ặ ậ

M c dù v y m t s bài toán hay đ i t ng khi đ c l p trình trên máy tính ộ ố ố ượ ặ ậ ượ ậ

ố ớ b ng thu t toán đ quy thì gây t n b nh và th i gian th c hi n quá lâu đ i v i ằ ự ệ ệ ậ ố ộ ớ ờ

nh ng s li u l n.Nguyên nhân c b n là vì b n ch t c a đ quy th c ch t là m t dây ấ ủ ệ ố ệ ớ ơ ả ữ ự ả ấ ộ

chuy n mà trong đó các l nh đ quy khi th c hi n thì trình d ch ph i chuy n các mã ự ề ệ ệ ệ ể ả ị

c x p ch ng lên nhau r i m i x lý chúng theo th t l nh thành các th t c đ ệ ủ ụ ượ ế ớ ử ứ ự ế . N u ồ ồ

m t thu t toán đ quy đòi h i máy tính th c hi n s l ng l n các th t c đ c bi ệ ố ượ ự ệ ậ ộ ỏ ủ ụ ặ ớ ệ t

nh các hàm mũ th th i gian th c hi n và b nh t ng đ ng cũng ph i l n. ị ờ ớ ươ ư ự ệ ộ ươ ả ớ

1.2. C u trúc d li u cây

ữ ệ

ấ

1.2.1. Cây t ng quát:

ổ

a. Khái ni m:ệ A Cây là m t c u trúc l u tr trong đó ộ ấ ư ữ

các phân t c a cây (g i là các n t) có ử ủ ọ ố

ữ ệ cùng ki u d li u. M i n t g m d li u ỗ ố ồ ữ ệ ể D D B

và các liên ki ế ế ố t đ n n t khác.Gi a các n t ữ ố

D

D D C

Trang 6

C

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

có quan h phân c p g i là “quan h cha con”. Trong cây có m t n t đ c bi t g i là ộ ố ặ ệ ệ ấ ọ ệ ọ

node g c không là con c a b t kỳ n t nào. ủ ấ ố ố

Cây có th đ nh nghĩa b ng đ quy nh sau: ể ị ư ệ ằ

- M i n t là m t cây, nó cũng là n t g c c a cây đó. ố ố ủ ỗ ố ộ

1,n2,...nk l

1,T2,...Tk .Và cho n t n tr thành

- N u n là m t n t và n ộ ố ế ượ ố ố t là n t g c

c a các cây T ủ ở ố

n t cha c a các n t n ủ ố 1,n2,...nk thì ta s đ ẽ ượ ố c m t ộ

cây m i T. Cây này có n t g c là n, các cây T ố ố ớ ủ ố 1,T2,...Tk tr thành các cây con c a n t ở

g c n.ố

- Cây không có n t nào g i là cây r ng. ố ọ ỗ

b. Các khái ni m liên quan: ệ

M c c a cây: Ng i ta quy ứ ủ ườ ướ ố ố c n t g c có m c 1, n u n t cha có m c i thì n t con ố ứ ứ ế ố

có m c i+1. ứ

Chi u cao c a cây: Là m c cao nh t c a các n t trong cây. ủ ề ấ ủ ứ ố

B c c a n t: ậ ủ ố là s n t con c a cây đó. ố ố ủ

B c c a cây: là s b c cao nh t c a các n t trong cây. ậ ủ ấ ủ ố ậ ố

N t lá: là n t không có cây con (b c b ng 0). ố ậ ằ ố

là n tt trên cây có ít nh t m t con. N t n i (n t trong): ố ố ộ ấ ố ộ

c. Các cách bi u di n cây: ể ễ

ặ ằ Có 2 cách thông d ng đ bi u di n c u trúc cây trên máy tính là b ng m ng ho c b ng ễ ấ ể ể ụ ả ằ

i bi u di n b ng c u trúc liên k t. c u trúc liên k t. ấ ế Ở đây ta ch quan tâm t ỉ ớ ễ ằ ế ể ấ

A

A B C E D B

C

Trang 7

Hình 2: b ng c u trúc liên k t ế ấ ằ Hình 3: B ng m ng ằ ả

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

t trong cây là m t tr ng g m các ghi Khi bi u di n b ng c u trúc liên k t m i n ấ ể ế ễ ằ ỗ ố ộ ườ ồ

trong đó:

-Tr ng data ch a d li u l u t ườ ứ ữ ệ ư ạ ặ i nút đó.D li u có th là m t giá tr đ n gi n ho c ữ ệ ị ơ ể ả ộ

m t c u trúc d li u ph c t p. ứ ạ ộ ấ ữ ệ

- Tr ng liên k t ch a thông tin đ n các cây con khác.Tuỳ vào lo i cây mà s th ườ ố ườ ng ứ ế ế ạ

liên k t có th thay đ i. ế ể ổ

2.2. Cây nh phân:

ị

a.Khái ni m: ệ

Cây nh phân là m t tr ng h p quan tr ng c a c u trúc cây. ộ ườ ị ủ ấ ọ ợ

M i n t trên cây nh phân đ u có t i đa hai cây con có phân ọ ố ề ị ố data

bi t th t là cây con trái và cây con ph i. ệ ứ ự ả C u trúc nh sau: ư ấ

- Tr ườ ng data : ch a d li u ứ ữ ệ

left

right

- Tr i n t con trái.Tr ườ ng left : ch a liên k t t ứ ế ớ ố ườ ợ ng h p

không có con trái tr ng này đ c gán 1 giá tr đ c bi t ườ ượ ị ặ ệ

(trong ngôn ng C là NULL). ữ

- Tr i n t con ph i.Tr ng h p không có con ph i tr ườ ng right : ch a liên k t t ứ ế ớ ố ả ườ ả ườ ng ợ

này đ c gán 1 giá tr đ c bi t (trong ngôn ng C là NULL). ượ ị ặ ệ ữ

ộ ố ủ

t c a cây nh phân: Hình 4: M t n t c a cây b. Các d ng đ c bi ạ ặ ệ ủ ị

nhi phân

Cây nh phân suy bi n: ế các n t không ph i là lá ả ố ị

ch có m t nhánh con. ộ ỉ

Các tr ng h p c a cây nh phân suy bi n : ườ ợ ủ ế ị

4

3

4 1

2

2 6

Trang 8

3 5

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

Hình 5: Cây l ch trái Hình 6: Cây l ch ph i Hình 7 ệ ệ ả :Cây zích z cắ

Cây nh phân hoàn ch nh ị ỉ ủ : Các m c nh h n h-1 đ u có 2 con (v i h là chi u cao c a ỏ ơ ứ ề ề ớ

cây).

Cây cân b ngằ : Là cây nh phân tho mãn đi u ki n v i m i n t c a cây thì chi u cao ọ ố ủ ề ề ệ ả ớ ị

con trái và chi u cao con ph i h n kém nhau không quá 1. ả ơ ề

2.3. Cây nh phân tìm ki m (BST):

ế

ị

a.Đ nh nghĩa: ị

có giá tr khoá tìm ki m Cây nh phân tìm ki m là cây nh phân ế ị ị ế (key) t ị ạ i m i n ỗ tố đ uề

l n h n giá tr key c a m i ị ớ ọ n tố thu c cây con trái và ủ ơ ộ nhỏ h n giá tr key c a m i ị ọ n tố ủ ơ

ả . thu c cây con ph i ộ

b. Các tính ch t:ấ

- V i cây thông th ng đ tìm 1 giá tr trong cây có n n t thì đ ph c t p s là O(n). ớ ườ ứ ạ ẽ ể ố ộ ị

2n) r t thu n ti n cho thao tác tìm ki m.

Còn đ i v i cây BST thì s l n tìm ki m t ng đ ố ớ ố ầ ế ố i đa b ng chi u cao c a cây t ề ủ ằ ươ ươ ng

v i đ ph c t p O(log ớ ộ ứ ạ ệ ế ậ ấ

- Cây BST khi duy t trung t thì các giá tr đ c s p x p tăng d n. ệ ự ị ượ ắ ế ầ

- Giá tr nh nh t trong cây n m ấ ằ ở ỏ ị ả bên trái nh t, giá tr l n nh t n m phía bên ph i ấ ằ ị ớ ấ

nh t c a cây. ấ ủ

3.Thu t toán và s đ kh i:

ơ ồ ố

ậ

Cây Nh phân tìm ki m (BST): ế ị

3.1. T o cây BST: ạ

-Hàm chèn m t giá tri vào cây BST: ộ

Trang 9

S đ kh i: ơ ồ ố

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

begi n

T=NUL L

S

T=new SinhVien T->info=x T->left=T->right=null

Đ

T- >info>x Đ

S

T=T->left

T- >right

T=T->right

end

S S

Thu t toán: ậ

B1: N u cây r ng. ế ỗ

B1.1: T o n t m i. ạ ố ớ

Trang 10

B1.2: Gán cây b ng n t v a t o. ằ ố ừ ạ

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

B2: Ng c l ượ ạ ế ủ i n u giá tr chèn nh h n giá tr c a cây thì chèn vào bên trái c a ị ủ ỏ ơ ị

cây.

B3: Ng c l ượ ạ ế ả ủ i n u giá tr chèn l n h n giá tr c a cây thì chèn vào bên ph i c a ị ủ ơ ớ ị

cây.

B4: trùng giá tr đã có thì báo đã có trong cây. ị

5<8 chèn bên trái

Cây T:

5>4 chèn bên phải

8

5<6 chèn bên trái

4

12

2

14

10

6

NULL

NULL NULL

NULL

NULL

NULL

NULL

NULL

Ví d : Chèn giá tr 5 vào cây BST sau : ị ụ

Hình 38: Chèn BST. - Khi g i hàm chèn vì 5 <8 nên hàm g i đ quy chèn bên trái c a cây 8. ọ ệ ủ ọ

- T ng t 5>4 nên hàm ti p t c g i đ quy chèn bên ph i cây 4. ươ ự ế ụ ọ ệ ả

Trang 11

- 5<6 chèn bên trái cây 6.

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

Cây T:

5

8

NULL NULL

4

12

2

14

10

6

NULL

NULL

NULL NULL

NULL

NULL

NULL

NULL

Hình 39: Chèn BST. -Vì con trái c a 6 r ng nên hàm t o n t m i có giá tr b ng 5 và gán vào con trái c a 6. ớ ạ ị ằ ủ ủ ỗ ố

- K t thúc. ế

-Hàm t o cây BST: ạ

Đ u vào: Cây T r ng. ầ ỗ

Đ u ra: Cây BST không ch a giá tr 0. ứ ầ ị

Thuât toán:

B1: Khai báo bi n nh p. ế ậ

B2: T o m t cây r ng. ộ ạ ỗ

i khi bi n nh p = 0. B3: L p cho t ặ ớ ế ậ

B3.1: Nhâp giá tr chèn. ị

B3.2: G i hàm chèn. ọ

3.2. Các phép duy t :ệ

Đ u vào: Cây nh phân l u các s nguyên. ư ầ ố ị

K t qu : xu t ra màn hình 1 dãy các giá tr c a cây c n duy t. ị ủ ế ệ ầ ấ ả

3.2.1 Duy t ti n t : ệ ề ự

Trang 12

S đ khôi: ơ ồ

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

begin

T!=null

S

T->info

T=T->left

T=T->right

Đ

T==nul l

S

end

Đ

Thu t toán: ậ

Trang 13

B1: Trong khi cây khác r ng:ỗ

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

B1.1: xu t ra giá tr c a cây. ị ủ ấ

B1.2: g i hàm đ quy duy t cây con trái. ệ ệ ọ

B1.3: g i hàm đ quy duy t cây con ph i. ệ ệ ả ọ

: 3.2.2 Duy t trung t ệ ự

begin

S đ kh i: ơ ồ ố

T!=null

S

T=T->left

T->info

T=T->right

Đ

T==nul l

S

end

Trang 14

Đ

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

Thu t toán: ậ

B1: Trong khi cây khác r ng:ỗ

B1.1: g i hàm đ quy duy t cây con trái. ệ ệ ọ

B1.2: xu t ra giá tr c a cây. ị ủ ấ

B1.3: g i hàm đ quy duy t cây con ph i. ệ ệ ả ọ

3.2.2 Duy t h u t : ệ ậ ự

begin

S đ kh i: ơ ồ ố

T!=null

S

T=T->left

T=T->right

T->info

Đ

T==nul l

S

end

Trang 15

Đ

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

Thu t toán: ậ

B1: Trong khi cây khác r ng:ỗ

B1.1: g i hàm đ quy duy t cây con trái. ệ ệ ọ

B1.2: g i hàm đ quy duy t cây con ph i. ệ ệ ả ọ

B1.3: xu t ra giá tr c a cây. ị ủ ấ

Cây T:

10

20

50

NULL

30

40

60

NULL

NULL

NULL

NULL

NULL

Ví d minh ho thu t toán: ạ ụ ậ

NULL Hình 12:Ví d v duy t cây ụ ề

1. G i hàm duy t ti n t

ệ Duy t ti n t : ệ ề ự

cây T. ệ ề ự ọ

2. Xu t s 10 ra màn hình. ấ ố

3. G i hàm duy t ti n t quy T->left đ n n t 20 (hàm con đ quy c a n t 10). ệ ề ự ọ ế ố ủ ố ệ

5. G i hàm duy t ti n t

4. Xu t s 20 ra màn hình. ấ ố

T->left đ n n t 30 (hàm con đ quy c a n t 20). ệ ề ự ọ ế ố ủ ố ệ

6. Xu t s 30 ra màn hình. ấ ố

7. G i hàm duy t ti n t ệ ề ự ọ T->left đ n NULL. ế

8. G i hàm duy t ti n t ệ ề ự ọ T->right đ n NULL. ế

9. G i hàm duy t ti n t T->right đ n n t 40 (hàm con đ quy c a n t 20). ệ ề ự ọ ế ố ủ ố ệ

10. Xu t 40 ra màn hình. ấ

11. G i duy t ti n t ệ ề ự ọ T->left đ n NULL. ế

Trang 16

12. G i hàm duy t ti n t ệ ề ự ọ T->right đ n NULL. ế

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

13. G i hàm duy t ti n t T->right đ n 50 (hàm con c a n t 10). ệ ề ự ọ ủ ố ế

14. Xu t 50 ra màn hình. ấ

15. G i hàm duy t ti n t ệ ề ự ọ T->left đ n NULL. ế

16. G i hàm duy t ti n t T->right đ n 60 (hàm con c a n t 50). ệ ề ự ọ ủ ố ế

17. Xu t 60 ra màn hình. ấ

18. G i hàm duy t ti n t ệ ề ự ọ T->left đ n NULL. ế

19. G i hàm duy t ti n t ệ ề ự ọ T->right đ n NULL. ế

20. K t thúc. ế

Vây k t qu sau khi duy t ti n t 20 30 40 50 60 ệ ề ự ế ả cây T s là:10 ẽ

T ng t ta v i hàm duy t trung t 20 40 10 50 60 ươ ự ệ ớ ự ế k t qu là: 30 ả

Duy t h u t : 30 40 20 60 50 10 ệ ậ ự

3.3. Các thao tác đ m :ế

Đ u vào: Cây nh phân l u các s nguyên ư ầ ố ị

Đ u ra: Tr v s l ng các n t t ng ng (t ả ề ố ượ ầ ố ươ ứ ấ ả ố ố t c , s n t lá,n t n i...)tuỳ vào các ố ộ

hàm d i đây. ướ

3.3.1. Đ m t ế ấ ả t c các n t trên cây: ố

ổ Đ tính s n t c a cây ta c n tính s n t c a cây con trái và ph i.Khi đó t ng ố ố ủ ố ố ủ ầ begin ể ả

d=1

n t s b ng t ng n t c a các cây con c ng thêm 1. ố ẽ ằ ố ủ ổ ộ

T! =null

T->left! =null

S đ kh i: ơ ồ ố

T=T->left

d++

Đ S S

T->right! =null

T=T->right

Trang 17

end

Đ

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

S

Đ

Thu t toán : ậ

B1: N u cây r ng tr v 0. ỗ ả ề ế

B2: Ng c l ượ ạ ả ề i tr v 1 c ng v i hàm đ m n t cây con trái c ng ti p v i hàm ố ế ế ớ ộ ớ ộ

đ m s n t cây con ph i. ế ố ố ả

Cây T:

10

20

50

30

40

60

NULL 0

NULL NULL 0 0 1=(1+0+0)

NULL NULL 0 0 1=(1+0+0)

NULL NULL 0 0 1=(1+0+0)

3=(1+1+1)

2=(1+0+1)

Ví d minh ho thu t toán : Đ m s n t c a cây T. ố ố ủ ụ ế ậ ạ

t c các n t. ấ ả

6=(1+3+2) Hình 13: Đ m t ế 1. S n t c a cây T=1+ s n t cây con trái 20 + s n t cây con ph i 50. ố ố

ố ố ố ố ố ủ ả

2. S n t cây 20 = 1+ s n t cây con trái 30 + s n t con ph i 40. ố ố ố ố ố ố ả

3. S n t cây 30 = 1 + 0 (cây r ng ) + 0 (cây r ng). ố ố ỗ ỗ

4. S n t cây 30=1. ố ố

5. S n t cây 40 = 1 + 0 (cây r ng ) + 0 (cây r ng). ố ố ỗ ỗ

Trang 18

6. S n t cây 40=1. ố ố

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

7. S n t cây 20=3. ố ố

8. S n t cây 50 = 1+ 0(cây r ng) + s n t con ph i 60. ố ố ố ố ả ỗ

9. S n t cây 60 = 1 + 0 (cây r ng ) + 0 (cây r ng). ố ố ỗ ỗ

10. S n t cây 60 =1. ố ố

11. S n t cây 50 =2. ố ố

12. S n t cây T(cây 10)=6. ố ố

13. K t thúc. ế

V y k t qu hàm tr v là b ng 6. ậ ế ả ề ằ ả

begin S đ kh i: ố

3.4. Xoá 1 n t c a cây BST. ố ủ

T!=Null

T=T->right

T=T->left

ơ ồ

T- >info=x

T- >info

Đ

S S

Tree *p=T->left Tree *q=T

=nu ll

T- >left=null T- >right=null

Đ Đ T->left!

S Đ

p->right! =Null

S

Tree *p=T T=T->right Free(p)

Tree *p=T Đ Free(p) T=null

q=p p=p->right

S

T->info=p->info

T=p x=p->info

Trang 19

end

Đ

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

Trang 20

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

Thu t toán: ậ ị ố ượ c xác đ nh d a vào mã s sinh viên) c. ượ

ả ả ỉ ỉ (giá tr xóa đ ị ự B1: N u cây r ng báo không xoá đ ế ỗ c giá tr c n xoá): i (tìm đ c l B2: Ng ị ầ ượ ượ ạ B2.1: N u cây là lá thì xoá cây. ế B2.2: N u cây ch có con trái thì gán cây =con trái. ế B2.3: N u cây ch có con ph i thì gán cây =con ph i. ế B2.4: Tr ườ ợ ng h p cây có 2 con th c hi n 1 trong 2 cách: ự ị ớ ấ ị ấ ả ệ - Tìm giá tr l n nh t bên con trái thay vào cây sau đó xoá giá tr l n nh t bên con trái cây v a thay. ớ - Ho c tìm giá tr nh nh t bên con ph i thay vào cây sau đó xoá ỏ ị giá tr nh nh t bên con ph i cây v a thay. ừ ấ ả ặ ị ừ ấ ỏ

ả i n u giá tr xoá > h n giá tr c a cây thì chuy n sang xoá bên ph i ị ủ ể ị ơ c l ượ ạ ế

i n u giá tr xoá < h n giá tr c a cây thì chuy n sang xoá bên trái c l ị ủ ể ị ượ ạ ế ơ

10>5 xoá bên trái

Cây T:

6

10=10 nốt 10 có 2 cây con

2

10

1

11

4

8

7

9

3

5

B3: Ng c a cây. ủ B4: Ng c a cây. ủ Ví d : Xoá n t 10 trên cây nh phân sau : ụ ố ị

Trang 21

Hình 40: Xoá n t cây BST. - 10 >5, chuy n sang xoá bên ph i cây. ể ố ả

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

Cây T:

6

2

10

1

11

4

8

7

9

3

5

Hình 41: Xoá n t cây BST. ố c n t 10 trong cây. ượ ố

ủ

6

2

9

1

11

4

8

7

- Tìm đ - 10 có 2 cây con. - Tìm giá tr nh nh t bên con trái c a cây 10. ị ỏ ấ - 9 là giá tr l n nh t bên con trái. ấ ị ớ - Gán n t 10= 9. ố Cây T:

3

5

Hình 42: Xoá n t cây BST. ố

- Tìm xoá n t 9.ố - K t qu sau khi xoá nh hình trên. ả ư ế

3.5.Ki m tra cây có ph i cây BST không: ể ả

Dùng m ng m t chi u l u các giá tr c a cây khi duy t trung t , n u m ng đ ề ư ị ủ ệ ả ộ ự ế ả ượ c

đ c l u theo th t tăng d n thì cây v a đ c x lý là BST. ượ ư ứ ự ừ ượ ử ầ

Trang 22

-Hàm sao chép các giá tr c a cây sang m ng m chi u:: ị ủ ề ả ộ

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

Đ u vào: Cây nh phân T l u s nguyên, m ng m t chi u a, m t bi n n l u kích th ư ố ư ề ế ả ầ ộ ộ ị ướ c

m ng (ban đ u b ng 0). ầ ả ằ

Đ u ra: M ng a (l u các giá tr c a cây ) có kích th ị ủ ư ầ ả ướ c n (b ng s n t trên cây). ố ố ằ

B1: Trong khi cây khác r ng:ỗ

B1.1: g i hàm đ quy cho cây con trái. ệ ọ

B1.2: Tăng kích th c m ng lên 1. ướ ả

B1.3: Gán giá tr c a cây vào m ng. ị ủ ả

B1.4: g i hàm đ quy cho cây con ph i. ệ ả ọ

Cây T:

4

2

6

1

7

3

5

NULL

NULL

NULL

NULL

NULL

Ví d : Cây nh phân T. ụ ị

NULL NULL NULL Hình 32: Sao chép sang m ng.ả

ế ả ư ả

3

5

7

K t qu l u trên m ng: 1

2 6 4 Hình 33: Cây m ng cây T.

ả + Hàm ki m tra cây BST: ể

Đ u vào: Cây nh phân T. ầ ị

Đ u ra: Tr v 1 (n u là cây BST) ho c 0 (không ph i cây BST). ả ề ế ả ặ ầ

Thu t toán: ậ

B1: Khai báo m ng a kích th ả ướ c ban đ u n=0. ầ

B2: G i hàm chuy n sang m ng cây T. ể ả ọ

Trang 23

1 đ n n. N u a[i] >a[i+1] tr v không. B3: L p i t ặ ừ ả ề ế ế

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

B4: Tr v 1 ả ề

3.6.Ki m tra n t g c có l n h n m i n t trong cây hay không: ớ ơ ọ ố ố ố ể

Đ u vào: Cây nh phân l u các s nguyên không có 2 n t cùng giá tr . ị ư ầ ố ố ị

Đ u ra: Tr v 0(n u cây r ng ho c n t g c không l n nh t) ho c 1 n u n t g c là ế ố ố ặ ố ố ả ề ế ặ ấ ầ ỗ ớ

l n nh t. ớ ấ

ả Mu n ki m tra xem n t g c c a cây có l n h n m i n t trong cây hay không ta ph i ố ố ủ ớ ơ ọ ố ể ố

xây d ng hàm tìm giá tr l n nh t trong cây và hàm so sánh gi ị ớ ự ấ ả ị ớ ố ố ủ tr này v i n t g c c a

cây.

Thuât toán:

-Hàm tìm giá tr l n nh t trong cây: ị ớ ấ

B1: N u cây r ng tr v 0. ỗ ả ề ế

B2: Ng i n u cây là không có cây con nào thì tr v giá tr c a cây. c l ượ ạ ế ả ề ị ủ

B3: Ng i khai báo m = giá tr c a cây. c l ượ ạ ị ủ

B3.1: N u con trái khác r ng khai báo mleft = giá tr l n nh t c a con ấ ủ ị ớ ế ỗ

trái.N u mleft >m thì m=mleft. ế

B3.1: N u con ph i khác r ng khai báo mright =giá tr l n nh t c a con ấ ủ ị ớ ế ả ỗ

ph i. N u mleft >m thì m=mright. ế ả

B4: Tr v m. ả ề

Trang 24

Ví d minh ho : Tìm giá tr l n nh t c a cây T. ấ ủ ị ớ ụ ạ

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

Cây T:

10

20

50

NULL

30

60

40

NULL

NULL

NULL

NULL

NULL

NULL

m=40

m=30

m=60

m=30 vì 30>20

m=60 vì 60>50

m=40 vì 40>30 m=40 vì 40>10

m=60 vì 60>40

ị ớ ậ ấ Ghi chú: m là giá tr l n nh t nh trong thu t toán. Hình 31: Tìm giá tr l n nh t. ư ị ớ ấ K t qu cu i cùng tr v m=60. ả ố ả ề ế

-Hàm ki m tra n t g c có l n nh t không: ố ố ể ấ ớ

B1: N u cây r ng tr v 0. ỗ ả ề ế

B2: Ng i n u n t g c l n h n ho c b ng giá tr l n nh t c a cây thì tr c l ượ ạ ế ố ố ớ ơ ặ ằ ấ ủ ị ớ ả

v 1ề

B3: Còn l i tr v 0. ạ ả ề

3.7.Tính t ng các giá tr c a cây: ị ủ ổ

Đ tính t ng n t c a cây ta ph i tính t ng n t c a các cây con ,khi đó t ng n t c a cây ố ủ ố ủ ố ủ ể ả ổ ổ ổ

b ng giá tr c a cây c ng v i t ng n t các cây con. ằ ớ ổ ị ủ ộ ố

Thu t toán: ậ

B1: N u cây r ng tr v tr v 0. ả ề ả ề ế ỗ

B2: Ng c l ượ ạ ớ i thì tr v giá tr c a cây c ng v i t ng cây con ph i c ng v i ả ộ ớ ổ ả ề ị ủ ộ

t ng cây con trái. ổ

Trang 25

Ví d : Tính t ng cây T. ụ ổ

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

Cây T:

10

20

50

30

60

40

NULL 0

NULL 0

NULL 0

NULL NULL 0 0 30=(30+0+0)

NULL 0 40=(40+0+0)

NULL 0 60=(60+0+0)

110=(50+0+60)

90=(20 +30+40)

210=(10+90+110) Hình 29: Tính t ng các n t.

ố ổ K t qu : T ng các n t cây T b ng 210. ả ổ ế ằ ố

3.8.Tìm chi u cao c a cây: ủ ề

ủ Đ tính chi u cao c a cây ta ph i tính chi u cao c a các cây con, khi đó chi u cao c a ề ủ ủ ề ề ể ả

cây b ng chi u cao l n nh t c a các cây con c ng thêm 1. ấ ủ ề ằ ớ ộ

Thu t toán : ậ

B1: N u cây r ng thì chi u cao b ng 0. ế ề ằ ỗ

B2: Ng i: c l ượ ạ

B2.1: Khai báo h1=chi u cao cây con trái. ề

B2.2: Khai báo h2=chi u cao cây con ph i. ề ả

B2.3: N u h1>h2 thì tr v h1+1. ả ề ế

B2.4: Ng i tr v h2+1. c l ượ ạ ả ề

Trang 26

Ví d :Tìm chi u cao c a cây T. ề ụ ủ

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

Cây T:

10

20

50

3

2

2

0

NULL

30

60

40

1

1

1

0

0

0

0

NULL

NULL

NULL

NULL

0

NULL

0

NULL

Trang 27

ề K t qu : Chi u cao cây T b ng 3. ề ế ả Hình 28: Tìm chi u cao cây. ằ

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

NG II:

CH

Ự

Ứ

Ụ

Ằ

ƯƠ XÂY D NG NG D NG QU N LÝ SINH VIÊN B NG CÂY Ả NH PHÂN BST

Ị

2.1.Đ c t

bài toán

ặ ả

Cây có ng d ng trong r t nhi u gi ứ ụ ề ấ ả ể ấ ầ i thu t trong tin h c.Ta có th th y t m ậ ọ

quan tr ng c a c u trúc d ng cây trên r t nhi u m t.Trong t nhiên có th l y m t ví ủ ấ ề ặ ấ ạ ọ ự ể ấ ộ

d đi n hình nh t đúng nh tên g i c a nó chính là các cây xanh, chúng có đ ụ ể ọ ủ ư ấ ượ ứ c s c

t là nh kh năng v n chuy n ch t t g c t i t s ng r t t ố ấ ố ấ ừ ố ớ ấ ả t c các đi m là c a cây ể ủ ể ậ ả ờ

i v n d ng trong khoa h c c th là khoa h c máy tính. Có th , u đi m mà con ng ư ể ườ ậ ụ ọ ủ ể ọ ể

ng là ngu n,các n t là các c a sông và các giao l y m t ví d khác hãy coi đ i d ấ ạ ươ ụ ộ ử ồ ố

đi m cúa các con sông ,sông và su i,m t cách bao quát đ i d ng,sông, su i-dòng ạ ươ ể ộ ố ố

ch y duy trì s s ng trên trái đ t cũng dùng c u trúc đ c bi t này.Trong các ngành ự ố ấ ặ ấ ả ệ

khoa h c ,”Cây” cũng đ ọ ượ ứ ọ ể c ng d ng r t sâu r ng nh cây gia ph các dòng h ,bi u ư ụ ấ ả ộ

di n các h p ch t hoá h c,s p x p m c l c, hay b n đ t duy-m t công trình khoa ụ ụ ọ ắ ồ ư ế ễ ả ấ ợ ộ

duy sánh t o c a con ng i cũng áp d ng cây h c n i ti ng giúp t ọ ổ ế ố ư i u kh năng t ả ư ạ ủ ườ ụ

bi u đ .Còn trong lĩnh v c toán tin cây đ ự ể ồ ượ ị c đ nh nghĩa là m t đ th liên thông không ộ ồ ị

có chu trình, giúp gi ả ể i quy t r t nhi u thu t toán v tìm ki m, s p x p ,tính các bi u ế ấ ề ề ế ế ắ ậ

th c...Và đ tìm hi u sâu h n v gi i thu t đ quy trên khía c nh tin h c đ tài s s ề ả ứ ể ể ơ ọ ề ậ ệ ẽ ử ạ

ng h p đ c bi d ng cây nh phân-m t tr ị ụ ộ ườ ặ ợ ệ ủ t c a cây làm m c tiêu nghiên c u. ụ ứ

ọ Cây nh phân BST là m t trong nh ng c u trúc d li u c b n và r t quan tr ng ấ ữ ệ ơ ả ữ ấ ộ ị

đây ta s t o m t h th ng qu n lý sinh viên b ng cây nh phân BST trong l p trình. ậ Ở ộ ệ ố ẽ ạ ả ằ ị

ệ g m nh ng thao tác c b n trên cây nh phân b ng thu t toán đ quy nh t o,duy t ồ ơ ả ư ạ ữ ệ ậ ằ ị

2.Yêu c u bài toán

cây nh phân và cây nh phân tìm ki m, m t s thao tác đ m, tìm ki m,chèn... ộ ố ế ế ế ị ị

ầ

M c đích đ tài: Xây d ng và t o đ c ch ng trình qu n lý sinh viên b ng cây nh ụ ề ự ạ ượ ươ ả ằ ị

Trang 28

phân BST.

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

N i dung đ tài: ộ ề

- Ch ươ ng trình t o ra có th th c hi n đ y đ các công vi c c a ng ệ ệ ủ ể ự ủ ầ ạ ườ i qu n lý ả

sinh viên: Nh p, xóa, thêm, tìm ki m,s p x p. ế ế ắ ậ

- M i sỗ inh viên ph i đ m b o đ y đ các thông tin: mã s sinh viên, tên ủ ả ả ầ ả ố

sinh viên,ngày/tháng/năm sinh,gi i tính, l p, quê quán ớ ớ

c thao tác trên vùng - H th ng ph i đ m b o m i công vi c ph i đ ả ệ ệ ả ả ả ố ọ ượ

d li u ữ ệ chung.

-Các thao tác ph i rõ ràng, d s d ng. ễ ử ụ ả

Phân tích:

Yêu c u quan tr ng nh t c a đ tài đ t là n m v ng lý thuy t đ quy, đ c bi ặ ấ ủ ề ế ệ ữ ắ ặ ầ ọ ệ t

là gi ả i thu t đ quy trong tin h c.Th hai là c u trúc d li u cây trong đó c ng c và ấ ậ ệ ữ ệ ứ ủ ọ ố

tìm hi u k v cây nh phân g m đ nh ngĩa, các khái ni m liên quan đ n cây nh phân. ỹ ề ể ệ ế ồ ị ị ị

Cu i cùng là ng d ng các thu t toán đ quy đ cài đ t m t s bài toán trên cây nh ộ ố ứ ụ ệ ể ậ ặ ố ị

phân, ch ng trình đ c vi t b ng ngôn ng C. ươ ượ ế ằ ữ

Ch ng trình đ c th c hi n trên ngôn ng l p trình C++, ch ng trình s bao ươ ượ ữ ậ ự ệ ươ ẽ

s g m các thao tác th c hi n trên cây nh phân. V i các thu t toán ng d ng ị ồ ự ứ ụ ệ ậ ớ thẽ ể

hi n rõ đ c các thu c tính cũng nh đ t tr ng trên cây ệ ượ ư ặ ư ộ vào bài toán qu n lýả

sinh viên. Ch ng trình đ c thi t k d ng menu, trên menu ươ ượ ế ế ở ạ ứ bao g m các ch c ồ

năng c a ch ng trình nh : Đ c d li u t file, thêm sinh viên vào danh ủ ươ ữ ệ ư ọ ừ

sách, tìm sinh viên, li t kê các sinh viên , xóa sinh viên, l u d li u vào file. ệ ư ữ ệ

3. KHAI BÁO C U TRÚC D LI U QU N LÝ SINH VIÊN

Ữ Ệ

Ấ

Ả

3.1.Cây nh phân là m t ki u d li u t đ nh ngĩa: ể ữ ệ ự ị ộ ị

Đ t o ra môt c u trúc cây nh phân qu n lý sinh viên g m các tr ng: mã ệ ạ ả ấ ồ ị ườ

i tính,năm sinh,l p,đ a ch trên máy tính , v i ngôn ng C ta đ nh nghĩa cây s ,h tên,gi ố ọ ớ ữ ớ ớ ị ỉ ị

nh phân là m t ki u d li u g m tr ể ữ ệ ộ ồ ị ườ ể ng ch a thông tin x lý là ki u s nguyên,ki u ể ố ứ ử

ký t , hai tr ng ch a đ a ch t i con trái và con ph i c a cây. Có th khai báo nh ự ườ ỉ ớ ứ ị ả ủ ể ư

Trang 29

sau:

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

struct SinhVien

{

int maso;

char name[30];

char ngaysinh[20];

char gioitinh[5];

char lop[10];

char diachi[50];

Tree *left, *right;

};

Cây nh phân là m t ki u c u trúc trên lý thuy t không gi ng ph n t ể ấ ế ộ ị i h n s l ớ ạ ố ươ . ầ ử

3.2. Khai báo toàn c c:ụ

G m hai c u trúc ki u cây đ c khai báo trong ch ng trình đ quy x lý trên ể ấ ồ ượ ươ ử ệ

cây nh phân tìm ki m. ế ị

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

Khai báo:

SinhVien *T;

S d ng trong các thao tác t o, duy t, chèn và xoá c a menu cây BST. ệ ử ụ ủ ạ

int x;char H[30];char date[20];char G[5];char L[10];char D[50] là các m ng dùng đ gán ể ả

d li u trong các thao tác thêm, chèn. ữ ệ

4. L P TRÌNH

Ậ

4.1. Các b c l p trình. ướ ậ

- N i dung ch ng trình là cài đ t các thao tác trên cây nh phân b ng gi i thu t đ ộ ươ ặ ằ ị ả ậ ệ

quy nên b c đ u tiên th c hi n là nhóm các thao tác t ng t nhau thành các menu ướ ự ệ ầ ươ ự

Trang 30

con (ch ng trình g m 8 menu tác v đã nêu ph n phân tích h th ng) ươ ụ ồ ở ầ ệ ố

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

ậ - Sau khi nhóm các tác v thành các menu con ph n vi c ti p theo là xây d ng thu t ự ụ ế ệ ầ

toán b ng ngôn ng t nhiên cho các tác v c a t ng menu. ữ ự ằ ụ ủ ừ

- M i tác v con s th c hi n tu n t các b ý th ng thu t toán , l p mã gi ẽ ự ầ ự ụ ệ ỗ c t ướ ừ ưở ậ ậ ả ,

vi ế t mã c a ch ủ ươ ng trình và cu i cùng là ki m th . ử ể ố

4.2. Ghi chú:

- Trong mã ch c thông báo ươ ng trình m i menu s đ ỗ ẽ ượ tr ở ướ c các hàm c a menu đó. ủ

4.3. Mã ch ng trình (code): ươ

- Ph n code c a ch ng trình vì h u h t đ c vi t b ng gi ủ ầ ươ ế ượ ầ ế ằ ả ấ i thu t đ quy nên r t ậ ệ

ng n g n, gi ng viên có th xem thông các trình so n th o C++ (C Free, DevC...). ắ ọ ể ạ ả ả

4.4.Đ c d li u t file: ọ ữ ệ ừ

begin

f=fopen(file, “r”)

S đ kh i: ơ ồ ố

Đ

F==Null

S

!feof(f)

Đ

S

fgets(data,100,f);

end

Trang 31

chenDS(data,T);

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

Thu t toán: ậ

B1:m file đ đ c d li u. ể ọ ữ ệ ở

B2:ki m tra file ể

B.2.1.N u không có sinh viên nào ế thông báo ra màn hình file tr ngố

B.2.2.Ng i n u file có d li u thì toàn b d li u s đ c l c t i lên cây nh ượ ạ ế ộ ữ ệ ẽ ượ ả ữ ệ ị

phân.

Code:

void docfile(char *filename,SinhVien *&T){

FILE *f=fopen(filename,"r");

If(f==NULL) cout<< “khong co du lieu”;

while(!feof(f)){

char maso[30];//fscanf(f,"%d",&x);

fgets(maso,100,f);

x=atoi(maso);

fgets(H,100,f);

fgets(date,100,f);

fgets(G,100,f);

fgets(L,100,f);

fgets(D,100,f);

chenDS(x,H,date,G,L,D,T);

}

fclose(f);

Trang 32

}

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

Menu

ch

ng

L u ư ươ trình

Thoát ng ch ươ trình

Thêm sinh viên

In danh sách

Xóa sinh viên

S a ử thông tin sinh viên

Đ m ế s ố sinh viên

Tìm sinh viên theo mã số

4.5.H th ng menu ch ng trình: ệ ố ươ

Ch ươ ng trình s th c hi n các thao tác và m s bài toán c b n trên cây nh phân có ộ ố ẽ ự ơ ả ệ ị

tr ng d li u là các s nguyên và ký t . S đ h th ng ch ng trình (đ c minh ườ ữ ệ ố ự ơ ồ ệ ố ươ ươ

ho hình 8 ) g m menu chính hi n th đ ng d n đ n các menu tác v nh h n: ạ ở ị ườ ể ồ ụ ỏ ơ ế ẫ

: T o ra m t cây nh phân b ng c u trúc liên k t l u tr các s -Menu nh p sinh viên ậ ế ư ữ ằ ấ ạ ộ ị ố

nguyên và kí t . nh p t bàn phím đ t o ra m t cây nh phân. N u b qua menu này ự ậ ừ ế ỏ ể ạ ộ ị

thì ch ng trình s th c hi n các tác v v i cây đã đ c cài m c đ nh. ươ ẽ ự ụ ớ ệ ượ ặ ị

T o cây BST: ạ

-Hàm chèn m t đ i t ng vào cây BST: ộ ố ượ

Trang 33

S đ kh i: ơ ồ ố

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

begi n

S T=NUL L

T=new SinhVien T->data=dulieu T->left=T->right=null

Đ

T=T->left

T- >right

T=T->right

end

S T- >info>x Đ S

Thu t toán: ậ

B1: N u cây r ng. ế ỗ

B1.1: T o n t m i. ạ ố ớ

B1.2: Gán cây b ng n t v a t o. ằ ố ừ ạ

B2: Ng i n u mã s c a sinh viên c n chèn nh h n mã s c a sinh viên c l ượ ạ ế ỏ ơ ố ủ ố ủ ầ

Trang 34

trong cây thì chèn vào bên trái c a cây. ủ

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

B3: Ng i n u mã s c a sinh viên c n chèn l n h n mã s c a sinh viên c l ượ ạ ế ố ủ ố ủ ầ ớ ơ

trong cây thì chèn vào bên ph i c a cây. ả ủ

B4: trùng giá tr đã có thì báo đã có trong cây. ị

Code:

void chenDS(int x,char H[30],char date[20],char G[5],char L[10],char D[50], SinhVien

*&T)

{

if (T==N)

{

T=new SinhVien;

T->maso=x;

strcpy(T->name,H);

strcpy(T->ngaysinh,date);

strcpy(T->gioitinh,G);

strcpy(T->lop,L);

strcpy(T->diachi,D);

T->left=T->right=N;

}

else if(T->maso>x) chenDS(x,H,date,G,L,D,T->left);

else if(T->masoright);

else cout<<"\nDa co ten";

}

vào in thông -Menu in danh sách sinh viên: Duy t toàn b cây theo cách duy t trung t ệ ệ ộ ự

tin ra màn hình.

S d ng ử ụ phép duy t :ệ

Đ u vào: Cây nh phân l u các s nguyên. ư ầ ố ị

Trang 35

K t qu : xu t ra màn hình 1 dãy các giá tr c a cây c n duy t. ị ủ ế ệ ầ ấ ả

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

begin

S đ kh i: ơ ồ ố

T! =null

S

T->left! =null

Đ S

T->data

Đ T=T->left

T->right! =null

S

T=T->right

end

Đ

Thu t toán : ậ

Duy t trung t : ệ ự

B1: Trong khi cây khác r ng:ỗ

B1.1: g i hàm đ quy duy t cây con trái. ệ ệ ọ

thông tin sinh viên. B1.2: xu t raấ

Trang 36

B1.3: g i hàm đ quy duy t cây con ph i. ệ ệ ả ọ

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

Code:

void F(SinhVien *T){

if(T!=N){

F(T->left);

cout<<"\nMa so SV: "<maso;

cout<<"\nTen SV: "<name;

cout<<"\nNgay sinh: "<ngaysinh;

cout<<"\nGioi tinh: "<gioitinh;

cout<<"\nLop: "<lop;

cout<<"\nDia chi: "<diachi;

F(T->right);

}

}

t c các n t duy -Menu tìm ki mế : Thu t toán th c hi n nhi m v này s duy t qua t ự ụ ệ ẽ ệ ệ ậ ấ ả ố

nh t m t l n , tuỳ vào t ng tr ng h p c th mà m i hàm vi ộ ầ ừ ấ ườ ợ ụ ể ỗ ế t ra có nhi m v khác ệ ụ

nhau. Ở ặ đây nhi m v c a hàm duy t là v xu t ra màn hình sinh viên có mã s ho c ụ ấ ụ ủ ệ ệ ố

tên t ng ng l u trên các n t c a cây.Có 2 cách tìm ki m: ươ ứ ố ủ ư ế

Trang 37

+ Tìm ki m theo mã s : X lý và tìm ki m các mã s sinh viên gi ng v i t khóa. ớ ừ ử ế ế ố ố ố

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

begin

T=null

Đ

T->data

T->data=x S

S Đ

T->left! =null Đ

T=T->left

T=T->right

end

S

Thu t toán: ậ

B1: N u cây r ng báo không t n t i ồ ạ ế ỗ

i trong cây hi n th B2: N u mã s sinh viên c n tìm trùng v i mã s t n t ầ ố ồ ạ ế ố ớ ể ị

thông tin c a sinh viên đó ra màn hình. ủ

B3: N u mã s c a sinh viên c n tìm nh h n mã s sinh viên trong cây thì ỏ ơ ố ủ ế ầ ố

chuy n qua so sánh bên trái c a cây. ủ ể

B4: Ng i n u mã s c a sinh viên c n tìm l n h n mã s sinh viên trong c l ượ ạ ế ố ủ ầ ơ ớ ố

Trang 38

cây thì chuy n qua so sánh bên ph i c a cây. ả ủ ể

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

-S a danh sách sinh viên : đ u tiên tìm và hi n thông tin c a sinh viên c n s a , sau ử ầ ử ủ ệ ầ

đó gán thông tin c n s a vào tr ầ ử ườ ng c n s a. ầ ử

Code:

void SuaDS(SinhVien *&T,int r){

SinhVien *p;

cout<<"\nThong tin SV can sua:";

p=Timmaso(T,r);

cout<<"\nNhap lai thong tin:";

fflush(stdin);

cout<<"\nTen SV: ";

gets(H);

strcat(H,"\n");

cout<<"\nNgay sinh: ";

gets(date);

strcat(date,"\n");

cout<<"\nGioi tinh: ";

gets(G);

strcat(G,"\n");

cout<<"\nLop: ";

gets(L);

strcat(L,"\n");

cout<<"\nDia chi: ";

gets(D);

strcat(D,"\n");

strcpy(p->name,H);

strcpy(p->ngaysinh,date);

strcpy(p->gioitinh,G);

Trang 39

strcpy(p->lop,L);

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

strcpy(p->diachi,D);

}

-Xóa sinh viên : tìm và ki m tra sinh viên c n xóa có t n t i hay không n u t n t i thì ồ ạ ể ầ ế ồ ạ

xóa node ch a thông tin v sinh viên đó và thi i các node phía sau nó. ứ ề t l p l ế ậ ạ

begin

S đ kh i: ơ ồ ố

T!=Null

S

Đ

T=T->right

T=T->left

T- >maso=x

T- >maso

S S

Đ

T->left!

SinhVien *p=T->left SinhVien *q=T

T->left=null T- >right=null

=nu ll

S Đ

p->right! =Null Đ

SinhVien *p=T T=T->right Free(p)

SinhVien *p=T Free(p) T=null

q=p p=p->right

T->maso=p->maso

T=p x=p->maso

end

Trang 40

Đ S S

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

c xác đ nh d a vào mã s sinh viên) Thu t toán: ậ (giá tr xóa đ ị ượ ự ố ị

B1: N u cây r ng báo không xoá đ c. ế ỗ ượ

B2: Ng i (tìm đ c mã s sinh viên c n xoá): c l ượ ạ ượ ầ ố

B2.1: N u sinh viên n m trong cây là lá thì xoá cây ch a sinh viên đó. ứ ế ằ

B2.2: N u cây ch có con trái thì gán cây =con trái. ế ỉ

B2.3: N u cây ch có con ph i thì gán cây =con ph i. ế ả ả ỉ

B2.4: Tr ườ ng h p cây có 2 con th c hi n 1 trong 2 cách: ự ệ ợ

- Tìm mã s sinh viên l n nh t bên con trái thay vào cây sau đó xoá ấ ố ớ

mã s sinh viên l n nh t bên con trái cây v a thay. ừ ấ ố ớ

- Ho c tìm mã s sinh viên nh nh t bên con ph i thay vào cây sau ấ ả ặ ố ỏ

đó xoá mã s sinh viên nh nh t bên con ph i cây v a thay. ỏ ấ ừ ả ố

B3: Ng i n u mã s sinh viên c n xoá > h n mã s sinh viên c a cây thì c l ượ ạ ế ủ ầ ố ố ơ

chuy n sang xoá bên ph i c a cây. ả ủ ể

B4: Ng i n u mã s sinh viên c n xoá < h n mã s sinh viên c a cây thì c l ượ ạ ế ủ ầ ố ơ ố

chuy n sang xoá bên trái c a cây. ủ ể

Code:

void XoaDS(SinhVien *&T,int s){

if(T!=N)

if(T->maso==s)

if(T->left==N && T->right==N){

SinhVien *p=T;

free(p);

T=N;

}

Trang 41

else if(T->left!=N){

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

SinhVien *p=T->left,*q=T;

while(p->right!=N){

q=p;

p=p->right;

}

T->maso=p->maso;

XoaDS(p,p->maso);

}

else{

SinhVien *p=T;

T=T->right;

free(p);

}

else if(T->masoright,s);

else XoaDS(T->left,s);

}

-Th ng kê sô l ng sinh viên : Thao tác s đ m xem có bao nhiêu sinh viên có trong ố ượ ẽ ế

danh sách.

Đ tính s ể ố sinh viên ta c n tính s ầ ổ ố sinh viên c a cây con trái và ph i.Khi đó t ng ủ ả

sinh viên c a các cây con c ng thêm 1. số s b ng t ng ẽ ằ ổ ủ ộ

Trang 42

S đ kh i: ơ ồ ố

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

begin

d=1

T! =null

S

T->left! =null

Đ S

T=T->left

d++

Đ

T->right! =null Đ

T=T->right

end

S

Thu t toán : ậ

B1: N u cây r ng tr v 0. ỗ ả ề ế

B2: Ng c l ượ ạ ả ề ế i tr v 1 c ng v i hàm đ m s sinh viên cây con trái c ng ti p ố ế ộ ớ ộ

v i hàm đ m s sinh viên cây con ph i. ớ ế ả ố

Code:

int dem(SinhVien *T){

if(T==NULL)return 0;

else

{

return 1+dem(T->left)+dem(T->right);

Trang 43

}

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

}

ng trình : ch c năng này cho phép l u l i các thao tác phía trên. -L u ch ư ươ ư ạ ứ Ghi các dữ

li u đã đ c s a ch a vào trong file. N u ch c năng không đ c kh i đ ng thì các ệ ượ ử ữ ứ ế ượ ở ộ

thao tác đã đ c l u vào ch ng trình. ượ c th c hi n s không đ ệ ẽ ự ươ ư ươ

Code:

void GhiFile(char *FileName,SinhVien *&T){

char c= (int)10;

if(T!=NULL){

FILE *f = fopen(FileName,"a");

fprintf(f,"%d\n",T->maso);

fprintf(f,"%s",T->name);

fprintf(f,"%s",T->ngaysinh);

fprintf(f,"%s",T->gioitinh);

fprintf(f,"%s",T->lop);

fprintf(f,"%s",T->diachi);

//fprintf(f,"\n"); //xuong dong

GhiFile(FileName,T->left);

GhiFile(FileName,T->right);

}

}

Trang 44

-Thoát kh i ch ng trình. ỏ ươ

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

CH

NG III

ƯƠ

DEMO CH

NG TRÌNH

ƯƠ

Ch ng trình đ c vi t b ng ngôn ng C++ v i trình so n th o và biên d ch là C Free ươ ượ ế ằ ữ ạ ả ớ ị

version 4. Các trình biên d ch C/C++ khác khi th c thi ch ng trình có th g p m t s ự ị ươ ể ặ ộ ố

main(),Turbo C là v n đ v cú pháp nh cách khai báo hàm main (trong Dev C là int ấ ề ề ư

Void main(),C Free 4 c hai cách trên đ u đ ề ượ ả ể c). Ngoài ra còn m t s l nh đi u khi n ộ ố ệ ề

nh l nh xóa màn hình ch ng trình dùng l nh system(“cls”) thay cho l nh clrscr() ư ệ ươ ệ ệ

trong turbo C. Vì v y ch ng trình s ch y t ậ ươ ẽ ạ ố t nh t trên ph n m m C Free. ầ ề ấ

H ng d n thao tác: ẫ ướ

Các menu khi ch n đã đ c tô màu, đ ọ ượ ể ch n menu và các tác v chi c n di chuy n các ụ ể ầ ọ

phím lên xu ng. Khi th c thi xong m t tác v c a m t menu con ,ch ng trình s ụ ủ ự ố ộ ộ ươ ẽ

chuy n v menu chính khi nh n phím b t kỳ. ề ể ấ ấ

Ví d :ụ

Hình :Menu chính ch ng trình. ươ

Dùng phím di chuy n đ ch n thao tác.Nh n enter đ ch y ch ng trình. ể ạ ể ọ ể ấ ươ

Trang 45

Ch n dòng đ u tiên nh n enter đ thêm sinh viên vào trong cây nh phân ể ầ ấ ọ ị

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

Ch n dòng 2 thì t t c d li u sinh viên có trong cây s đ c in ra màn hình ọ ấ ả ữ ệ ẽ ượ

Ch n dòng 3 thì ch ng trình s tìm ki m sinh viên trong cây theo mã s nh p t bàn ọ ươ ậ ừ ẽ ế ố

Trang 46

phím.

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

Ch n dòng 4 ch ng trình s tìm sinh viên và d li u s a c a sinh viên s nh p l i t ọ ươ ữ ệ ử ủ ậ ạ ừ ẽ ẽ

bàn phím.

Trang 47

Ch n dòng 5 ch ng trình s tìm và xóa sinh viên có mã s t ọ ươ ố ươ ứ ng ng kh i danh sách. ỏ ẽ

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

Ch n dòng 6 ch ng trình s đ m xem có bao nhiêu sinh viên có trong cây. ọ ươ ẽ ế

Ch n dòng 7 ch ng trình s l u toàn b thao tác thêm, xóa ,s a đã đ c th c hi n ọ ươ ẽ ư ử ộ ượ ệ ở ự

trên.N u không ch n thao tác này tr c khi t t ch ng trình thì toàn b thao tác thêm, ế ọ ướ ắ ươ ộ

Trang 48

s a ,xóa s không l u l ẽ ử ư ạ i cho l n sau. ầ

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

Trang 49

ng trình. Ch n dòng 8 đ thoát kh i ch ể ỏ ọ ươ

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

KÊT LUÂN

́ ̣

uƯ đi m :ể

- N m rõ yêu c u c a bài toán g m hai ph n quan tr ng là lý thuy t đ quy và ắ ầ ủ ế ệ ầ ồ ọ

cây nh phân. ị

-Th c hi n đ y đ các yêu c u v n i dung và hình th c trình bày c a đ tài. ầ ề ộ ầ ủ ủ ề ự ứ ệ

- Hi u rõ các t t c các thu t toán đ quy trong ch ng trình. ể ấ ả ệ ậ ươ

- Ch ng trình đ c b c c rõ r àng : Ph n c t th c hi n theo s ươ ượ ố ụ ự ệ ầ ố ườ n đ tài, ề

menu th c thi đ c chia nh và săp x p ti n thao tác. ự ượ ế ệ ỏ

Nh ượ c đi m: ể

- Ch ng trình ch d ng l các thao các c b n. ươ ỉ ừ i ạ ở ở ả

- Ch ng trình không phân bi t tính đúng sai c a d li u c n nh p. ươ ệ ủ ữ ệ ầ ậ

Phát tri n :ể

- Đi m m nh c a cây nh phân là tính ng d ng cho vi c tìm ki m. Tr ng d ụ ứ ủ ể ế ệ ạ ị ườ ữ

li u có th đ ể ượ ệ ợ c xây d ng ph c t p h n (không ch là các s nguyên) phù h p ứ ạ ự ố ơ ỉ

ng phát tri n c a đ t i s chú tr ng sâu h n vào v i nhi u bài toán.Vì v y h ớ ậ ướ ề ể ủ ề ạ ẽ ọ ơ

ằ ph n cây nh phân tìm ki m, c th nâng cao các thu t toán ph c t p h n nh m ụ ể ứ ạ ế ậ ầ ơ ị

Trang 50

c i ti n công tác qu n lý sinh viên. ả ế ả

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

TÀI LI U THAM KH O

Ả

Ệ

Tieng viet

[1] Gi i thu t và l p trình. Lê Minh Hoàng. ĐH s ph m Hà N i. Năm 2002. ả ư ạ ậ ậ ộ

[2 ]C u trúc d li u và gi i thu t (bài gi ng chuyên đ ). Lê Minh Hoàng. ữ ệ ấ ả ề ậ ả

[3] Giáo trình c u trúc d li u và gi ữ ệ ấ ả i thu t. Đ i h c Duy Tân. ạ ọ ậ

[4] Trang web Wikipedia (C u trúc d li u cây ): ữ ệ ấ

Web site

1.h ttp://vi.wikipedia.org/wiki/C%C3%A2y_%28c%E1%BA%A5u_tr%C3%BAc_d%E1%BB

%AF_li%E1%BB%87u%29

2. www.congdongcviet.com

Trang 51

3. www.laptrinhc.daitudiem.com

ĐẠI HỌC DUY TÂN

DTU

KHOA CÔNG NGHỆ THÔNG TIN

M C L C

Ụ

Ụ

ậ

C s lý thuy t ươ ế ệ

c đi m c a thu t toán ủ Ư

ượ ấ ữ ệ 2.1.Cây t ng quát ổ 2.2.Cây nh phân 2.3.Cây nh phân tìm ki m(BST) ị ị ậ ế 3.Thu t toán và s đ kh i ạ

ọ ố ể ể ớ ổ

Xây d ng ng d ng qu n lý sinh viên b ng cây nh phân ị ủ ủ ả ự ứ ươ ằ ị bài toán

ặ ả ầ ư ệ ả ng II: Ch 1.Đ c t 2.Yêu c u bài toán 3.Khai báo c u trúc d li u qu n lý sinh viên 4.L p trình c l p trình ướ ậ

ng trình

Tri n khai ch y demo ch ng trinh ươ ể ạ

Trang 52

Ch ươ K t lu n ế Tài li u tham kh o Tên đ tàiề .............................................................................................................................02 Nh n xét c a GVHD ...........................................................................................................03 ủ ở ầ ..........................................................................................................................04 L i m đ u ờ Ch ế ..................................................................................................05 ng I: ơ ở .............................................................................................05 1.Lý thuy t đ quy 1.1.Khái ni mệ ................................................................................................05 1.2. u nh ............................................................06 ậ ể ........................................................................................06 2.C u trúc d li u cây ..........................................................................................06 ............................................................................................08 .................................................................09 ơ ồ ố ................................................................................08 3.1.T o cây BST ...........................................................................................10 3.2.Các phép duy tệ .......................................................................................12 3.3.Các thao tác đ mế ....................................................................................17 .....................................................................19 3.4.Xóa m t n t c a cây BST ộ ố ủ ..........................................................21 3.5.Ki m tra có ph i cây BST không ả ...............22 3.6.Ki m tra n t g c có l n h n m i n t trong cây hay không ơ ố ố ........................................................................24 3.7.Tính t ng giá tr c a cây ..........................................................................25 3.8.Tính chi u cao c a cây ề ...........................27 ụ .................................................................................................27 ...............................................................................................27 .................................................28 ấ ...........................................................................................................29 ậ 4.1.Các b .................................................................................29 4.2.Ghi chú....................................................................................................30 .....................................................................................30 4.3.Mã ch ươ file 4.4.Đ c d li u t .................................................................................30 ọ ữ ệ ừ .......................................................................................32 4.5.H th ng menu ệ ố ng III: .............................................................44 ậ ...............................................................................................................................49 ả ..............................................................................................................50 ệ