Giáo trình Lập trình nâng cao trên ngôn ngữ Pascal - Chương 4: Con trỏ và cấu trúc động

ằng 2. 
c. Cây một phía hay còn gọi là cây mọc lệch 
Cây một phía là loại cây mà cấp của tất cả các nút ñều bằng 1. 
Hình 4.5 dưới ñây mô tả các loại cây ñã nêu: 
   
   
   
a. Cây lệch phải b. Cây lệch trái 
  
   
  
  
  	 
d. Cây tự nhiên 
 	  
     
 e. Cây ñối xứng 
Hình 4.5 
Trường ðại học Nông nghiệp 1 - Giáo trình Lập trình nâng cao ..............................................................- 126 
Cây ñược vẽ theo chiều từ trên xuống dưới với nút gốc ở trên và nút lá ở dưới. Môt 
nút mà từ ñó có thể truy nhập ñến các nút khác thì ñược gọi là nút cha của các nút ñó, còn các 
nút ñược truy nhập gọi là nút con. 
Cây nhị phân có thể cài ñặt bằng cách dùng các cấu trúc liên kết ñã nêu trên. Dữ liệu 
trên một nút ñược lưu trữ bằng bản ghi, tại mỗi nút có hai con trỏ, CTT và CTP. CTT dùng ñể 
trỏ ñến con bên trái và CTP dùng ñể chỉ ñến con bên phải. Ví dụ dưới ñây nêu cách cài ñặt 
cây nhị phân, dữ liệu tại mỗi nút là một ký tự của bảng mã ASCII. Cần chú ý rằng theo quy 
ước thì các ký tự có thứ tự là: 
 a < b < c < ..... < z và A < B < C < ..... < Z 
 Type 
 ct=^Kytu; 
 Kytu = record 
 Nut : char; 
 Ctt,Ctp : ct; 
 end; 
 Var chucai : char; tim : boolean; 
 goc, ct1 : ct; batdau : pointer; 
Ví dụ trên ñã khai báo kiểu dữ liệu con trỏ ñặt tên là Kytu, ñây là kiểu bản ghi với mục 
ñích lưu trữ một ký tự của bảng mã, con trỏ CT dùng ñể trỏ vào kiểu dữ liệu Kytu. Bên trong 
kiểu Kytu có các con trỏ Ctt và Ctp dùng ñể trỏ vào các nút biểu diễn con bên trái và con bên 
phải của nút cha. 
CTT Dữ liệu CTP 
 Con bên trái Con bên phải 
Như vậy cây nhị phân trong hình 4.5e có thể ñược biểu diễn như là cây liên kết của 
các bản ghi dưới ñây 
 Nút gốc 
 6 
 4 8 
• 3 • • 5 • • 7 • • 9 • 
 Hình 4.6 
Trường ðại học Nông nghiệp 1 - Giáo trình Lập trình nâng cao ..............................................................- 127 
Trong hình 4.6 các nút chứa các giá trị 3, 5, 7, 9 là nút lá, chúng không có con bên trái 
hoặc con bên phải. Các con trỏ trái CTT và con trỏ phải CTP của chúng ñều trỏ vào Nil 
Một nút cha có thể có một hoặc hai cây con và bài toán xử lý cây nhị phân là thăm một 
nút, xử lý dữ liệu tại nút ñó rồi chuyển sang thăm nút khác. Vấn ñề phức tạp là ở chỗ mỗi nút 
ñều có hai con trỏ do vậy khi di chuyển sang nút khác chúng ta chọn hướng ñi nào, không 
những thế khi ñến một nút chúng ta xử lý dữ liệu trước rồi mới ñi thăm các nút con hay thăm 
nút con trước rồi xử lý dữ liệu tại nút cha sau? Tuỳ thuộc vào cách thức thăm và xử lý chúng 
ta sẽ có các kết quả khác nhau. 
Dưới ñây là một ví dụ minh hoạ. 
 	  
     
Hình 4.7 
Chúng ta gọi thao tác quét một cây nhị phân là việc thăm mỗi nút ñúng một lần, không 
sót một nút nào và thông tin tại mỗi nút ñược xử lý cũng chỉ một lần. 
Giả sử với cây nhị phân trên hình 4.7, chúng ta thục hiện quá trình quét như sau: 
1. Thăm nút gốc và xử lý dữ liệu, cụ thể là hiện giá trị có tại nút 
2. Quét cây con bên trái 
3. Quét cây con bên phải 
Với trình tự này kết quả nhận ñược sẽ là 6 4 3 5 8 7 9 
ðể tổng quát chúng ta ký hiệu các bước của tiến trình quét cây như sau: 
G: xử lý dữ liệu tại nút (tức là gốc của các cây mẹ hoặc cây con) 
T: quét cây con bên trái 
P: quét cây con bên phải 
Như vậy có tất cả 6 cách quét khác nhau: 
TGP; GTP; TPG; GPT; PGT; PTG 
Có thể nhận thấy rằng ñối với việc quét một cây ñiều quan trọng không phải là xử lý dữ 
liệu tại các nút mà là việc xử lý ấy ñược thực hiện khi nào. Trên cùng một cây với mỗi trình tự 
thực hiện chúng ta nhận ñược một kết quả và các kết quả này là không giống nhau. 
Trong 6 cách trên, ba cách ñầu (cây con bên trái ñược quét trước cây con bên phải) là ba 
cách ñược quan tâm nhiều hơn cả. Căn cứ vào thời ñiểm xử lý dữ liệu tại nút (bước G), chúng 
ta ñặt cho ba cách quét này các tên như sau: 
Trường ðại học Nông nghiệp 1 - Giáo trình Lập trình nâng cao ..............................................................- 128 
TGP: quét trung tâm (Inorder) 
GTP: quét trước (Preorder) 
TPG: quét sau (Postorder) 
Với cây hình 4.7 nếu xử dụng cách quét TGP chúng ta có kết quả như sau: 
3 4 5 6 7 8 9 
Sở dĩ có kết quả như trên là vì chúng ta ñã quét theo nguyên tắc: quét cây con bên trái, 
xử lý dữ liệu ở gốc rồi sau ñó quét cây con bên phải. Vì số 6 nằm ở gốc nên nó chưa ñược xử 
lý mà phải chuyển sang cây bên trái. Với cây con bên trái, số 4 nằm ở gốc nên lại phải theo 
nguyên tắc TGP nghĩa là sang bên trái tiếp. Số 3 nằm ở nút lá nên không còn ñi ñâu nữa kết 
quả là ñầu ra ta có số 3. Quay về G ta có số 4 sau ñó sang phải ta có số 5. Xong cây con bên 
trái ta quay về G và có số 6, tiếp tục với cây con bên phải ta có kết quả ñã nêu. 
Cách quét TGP sẽ cho ta kết quả là một dãy sắp xếp theo chiều tăng dần, ñiều này 
không những ñúng với số mà cũng ñúng với cây nhị phân chứa các ký tự tại mỗi nút, chúng ta 
sẽ nghiên cứu kỹ ñiều này qua ví dụ 4.16. 
Khi xây dựng cây nhị phân, dữ liệu tại nút gốc mang một ý nghĩa quan trọng, nó sẽ 
quyết ñịnh dữ liệu nhập tiếp theo sẽ nằm ở cây con bên trái hay cây con bên phải. 
Giả sử với một tập các ký tự : P, M, U, B, O, Q, T, V, Y nếu chúng ta tạo cây bằng cách 
ñặt ký tự P vào nút gốc và nhập theo thú tự trên thì cây sẽ có dạng hình 4. 8 
 P 
 M U 
 B O Q T 
 V 
 Y 
 Hình 4.8 
Còn nếu chúng ta ñặt U vào gốc và nhập dữ liệu theo thứ tự U, T, V, O, M, Q, Y, B, P 
thì cây sẽ có dạng như trong hình 4.9 
 U 
 T V 
 O Y 
 M Q 
 B P 
 Hình 4.9 
Trường ðại học Nông nghiệp 1 - Giáo trình Lập trình nâng cao ..............................................................- 129 
Ví dụ 4.16 
 Program Caynhiphan; 
 Uses crt; 
 Type 
 ct=^kytu; 
 kytu = record 
 Nut:char; 
 ctt,ctp:ct; 
 end; 
 Var chucai:char; goc:ct; i,j:byte; 
 A:array[1..100] of char; 
 ch:char; 
 Procedure Taocay (Var tg: ct); 
 {Chuong trinh con kiem tra xem ky tu dua vao da co trong cay chua 
 neu chua thi chen vao} 
 Begin 
 If tg=nil then 
 Begin 
 New(tg); 
 With tg^ do 
 Begin 
 Nut:= chucai; 
 ctt:=nil; ctp:=nil; 
 End; 
 End 
 Else 
 With tg^ do 
 Begin 
 if chucai<nut then taocay(ctt) 
 else 
 if chucai>nut then taocay(ctp) 
 else 
 Begin 
 textcolor(red); 
 Writeln('Ky tu ',chucai,' da co trong cay-Hay nhap tiep'); 
 end; 
 End; 
 End; 
Trường ðại học Nông nghiệp 1 - Giáo trình Lập trình nâng cao ..............................................................- 130 
 Procedure quet_trung_tam(contro:ct); 
 Begin 
 if contronil then 
 Begin 
 quet_trung_tam(contro^.ctt); 
 write(contro^.nut,' '); 
 quet_trung_tam(contro^.ctp); 
 end; 
 End; 
 Procedure quet_truoc(contro:ct); 
 Begin 
 if contronil then 
 Begin 
 write(contro^.nut,' '); 
 quet_truoc(contro^.ctt); 
 quet_truoc(contro^.ctp); 
 end; 
 End; 
 Procedure quet_sau(contro:ct); 
 Begin 
 if contronil then 
 Begin 
 quet_sau(contro^.ctt); 
 quet_sau(contro^.ctp); 
 write(contro^.nut,' '); 
 end; 
 End; 
 BEGIN 
 Clrscr; 
 writeln('Xay dung cay nhi phan cac ky tu'); 
 goc:=nil; i:=1; taocay(goc); 
 Repeat 
 textcolor(14); 
 write('Nhap ky tu vao nut - Bam so 9 de dung '); 
 readln(chucai); chucai:=upcase(chucai); 
 if (ord(chucai)>=65) and (ord(chucai)<=90) then 
 Begin 
Trường ðại học Nông nghiệp 1 - Giáo trình Lập trình nâng cao ..............................................................- 131 
 taocay(goc); 
 a[i]:=chucai; 
 i:=i+1; 
 end; 
 Until (Ord(chucai)90); 
 writeln; 
 textcolor(14); 
 writeln('Du lieu nhap ban dau'); 
 for j:= 1 to i do write(a[j],' '); 
 writeln; 
 writeln('Du lieu hien theo cach quet Trung tam TGP'); 
 quet_trung_tam(goc); 
 writeln; 
 writeln('Du lieu hien theo cach quet Truoc GTP'); 
 quet_truoc(goc); 
 writeln; 
 writeln('Du lieu hien theo cach quet Sau TPG'); 
 quet_sau(goc); 
 readln; 
 END. 
Chương trình con Taocay trong ví dụ 4.6 tạo nên một cây nhị phân mà dữ liệu tại các 
nút là các ký tự của bảng mã ASCII, khi bấm một phím bất kỳ trên bàn phím không phải là 
một trong các chữ cái chương trình tạo cây sẽ kết thúc. Các chương trình con 
Quet_trung_tam, Quet_truoc, Quet_sau thực hiện việc quét cây theo các trình tự TGP, GTP, 
TPG. 
Nếu chúng ta nhập vào dãy ký tự U, T, V, O, M, Q, Y, V, U thì chương trình sẽ cho 
kết quả: 
Du lieu nhap ban dau: 
U T V O M Q Y V U 
Du lieu hien theo cach quet Trung tam TGP 
B M O P Q T U V Y 
Du lieu hien theo cach quet Truoc GTP 
U T O M B Q P V Y 
Du lieu hien theo cach quet Sau TPG 
B M P Q O T Y V U 
Trường ðại học Nông nghiệp 1 - Giáo trình Lập trình nâng cao ..............................................................- 132 
Bài tập ứng dụng chương 4 
1. Lập chương trình nhập vào mảng A n số thực, n nhập từ bàn phím. Nhập vào chuỗi 
S tối ña 30 ký tự. Sử dụng phương pháp cấp phát ñộng cho các ñối tượng A, S. Cho hiện lên 
màn hình cách thức bố trí bộ nhớ mà hệ thống dành cho mảng A và chuỗi S. 
2. Sử dụng con trỏ mảng và mảng con trỏ ñể quản lý sách trong thư viện, giả thiết rằng 
mỗi cuốn sách gồm các thông tin: Tên sách, tên tác giả, số trang, giá tiền. Với cùng một số 
sách, bộ nhớ mà hệ thống sử dụng cho con trỏ mảng và mảng con trỏ có bằng nhau không? 
3. Số liệu tuyển sinh bao gồm: 
SBD, Họ và tên, phòng thi, ñiểm thi. 
Sử dụng biến ñộng nhập vào một số thí sinh, cho hiện danh sách thí sinh theo hai cách: 
hiện theo thứ tự nhập vào và hiện từ cuối lên ñầu. 
4. Tên người Việt là một chuỗi dài nhất là 7 ký tự. Nhập vào bộ nhớ n tên, sử dụng 
một trong các cách quét cây ñể hiện tên theo thứ tự tăng dần. 
5. Tạo cây nhị phân mà mỗi nút chứa một số thực. Quét cây theo trình tự GTP, TGP, 
TPG. Tại mỗi nút yêu cầu xử lý dữ liệu là : hiện giá trị tổng các số trong nút cha và nút con. 
6. Dãy số a1, a2, .... , an là các số thực. Lập chương trình ñưa dãy số trên vào cây nhị 
phân. Thiết kế 6 chương trình con tương ứng với 6 cách quét cây, yêu cầu xử lý tại mỗi nút là 
hiện trị tuyệt ñối của số trong nút.