Giáo trình Cấu trúc dữ liệu - Phạm Trọng Huy

 F[least].weight then 
	begin
second:=least;
least:=i;
	end 
	else 
if F[i].weight<F[second].weight then second:=i;
end;
{ tạo cây mới từ hai cây có trọng lượng bé nhất }
Function create(lefttree,righttree: integer): integer;
begin
{cấp phát gốc mới}
lastnode:=lastnode+1;
{cho hai con trỏ của nút gốc trỏ hai nút gốc của hai cây con}
T[lastnode].leftchild:=F[lefttree].root;
T[lastnode].rightchild:=F[righttree].root;
{con trỏ trỏ nút cha của nút gốc = null}
T[lastnode].parent:=0;
{nút gốc mới là nút cha của hai nút gốc của hai cây con}
T[F[lefttree].root].parent:=lastnode;
T[F[righttree].root].parent:=lastnode;
create:=lastnode;
 end;
{ Giải thuật HUFFMAN }
procedure huffman(var root:integer);
var 	i,j:integer;
 	newroot:integer;
begin
{lặp cho đến khi chỉ còn một nút}
while lasttree>1 do 
	begin
lightones(i,j);{tìm hai nút bé nhất}
newroot:=create(i,j);
{tạo cây từ hai nút bé nhất}
{trọng số nút mới bằng tổng trọng số của hai nút con}
F[i].weight:=F[i].weight+F[j].weight;
F[i].root:=newroot;
F[j]:=F[lasttree];
lasttree:=lasttree-1;
	end;
root:=newroot;
end;
{ Mã hoá một ký tự thành các bit 0,1 }
function encodeOneChar(ch:char):string;
var	i,j,l:integer;
	S_encode:string;
begin
{khởi tạo chuỗi mã rỗng}
S_encode:='';
i:=0;
{tìm kí tự cần mã hoá trong bảng Alphabet}
repeat
	i:=i+1
until (i>n) or (A[i].symbol=ch);{n là số kí tự trong bảng}
{nếu tìm thấy}
if i<=n then
	{lần ngược từ lá chứa kí tự này lên gốc cây để tìm chuỗi bít 0,1	nếu nút nằm bên trái thì thêm 0, nằm bên phải thì thêm 1}
repeat
j:=T[i].parent; { lấy nút cha của nút i}
if T[j].leftchild=i then 
	S_encode:=’0’ + s_encode
	 else S_encode:=’1’+ S_encode;
i:=j;
until t[i].parent=0 { tới root }
	else 
	begin
	{không tìm thấy kí tự muốn mã hoá trong bảng kí tự}
writeln(' ký tự ',ch,' sai ');
S_encode:=S_encode+'*';
end;
 	encodeOneChar:=S_encode;
 end;
{ Mã hoá một chuỗi ký tự thành chuỗi bít 0,1 }
function encode(s:string):string;
var 	s_encode:string;
begin
s_encode:='';
for i:=1 to length(s) do
s_encode:=s_encode+encodeOneChar(s[i]);
encode:=S_encode;
end;
{ Giải mã một chuỗi bít 0,1 thành chuỗi ký tự thông thường a,b,c}
function decode(s:string):string;
var	S_decode: string;
	i,curr:integer;
	err:boolean;
begin
i:=1;
S_decode:='';
Err:=false;
while (i<= length(s)) and ( not Err ) do 
begin
 curr:=root;
 while ((T[curr].leftchild0) or 	(T[curr].rightchild0))and (not Err) do 
	begin
if s[i]='0' then
	if T[curr].leftchild0 then 	curr:=T[curr].leftchild
	else Err:=true
else if s[i]='1' then
	If t[curr].rightchild0 then 
	curr:=T[curr].rightchild
	else Err:=true
	else Err:=true;
i:=i+1
	end;
	S_decode:=S_decode+A[curr].symbol
end;
if Err then 
	begin
	writeln(' Lỗi trong chuỗi muốn giải mã ');
	S_decode:='';
	end;
decode:=S_decode;
 end;
{chương trình chính }
BEGIN
initialize;
lastnode:=lasttree;
n:=lasttree;
{xây dựng cây Huffman}
huffman(root);
{kiểm tra giải thuật mã hoá}
repeat
write('cho chuỗi ký tự muốn mã hoá ');
readln(s);
writeln(encode(s));
write('cho chuỗi bít 0,1 để giải mã ');
readln(s);
writeln(decode(s));
until s='';
END.
5.7. Cây nhị phân tìm kiếm
5.7.1 Ðịnh nghĩa
	Cây nhị phân tìm kiếm là cây nhị phân trong đó tại mỗi nút, khoá của tất cả các nút thuộc cây con trái đều nhỏ hơn khoá của nút đang xét và nhỏ hơn khoá của tất cả các nút thuộc cây con phải. (Khoá ở đây là một nhóm thuộc tính của một lớp đối tượng sao cho hai đối tượng khác nhau cần phải có giá trị khác nhau trên nhóm thuộc tính đó, giả thiết đó chính là giá trị gắn trên mỗi đỉnh của cây nhị phân)
	Nhờ sự ràng buộc về khoá trên cây nhị phân tìm kiếm, việc tìm kiếm trở nên có định hướng. Hơn nữa, do cấu trúc cây, việc tìm kiếm trở nên nhanh đáng kể. Nếu số nút trên cây là N thì chi phí tìm kiếm trung bình chỉ khoảng log2N.
	Trong thực tế, khi xét đến cây nhị phân chủ yếu người ta xét cây nhị phân tìm kiếm.
5.7.2 Các phép toán cơ bản trên cây nhị phân tìm kiếm
	a) Tìm kiếm: Bài toán đặt ra là: Cho cây nhị phân tìm kiếm, giả sử mỗi đỉnh của cây đều được gắn một giá trị xi thỏa mãn xi xj khi và chỉ khi i j, vấn đề đặt ra là tìm xem trên cây đó có tòn tại một đỉnh với khoá là x hay không. Ở đây mỗi đỉnh của cây được biểu diễn bởi một bản ghi có kiểu Note, biến con trỏ Root trỏ tới gốc cây và giá trị khoá x cho trước:
	Type Pointer = ^Note;	
	Note = Record
	Key: keytype;
	Left: Pointer;
	Right: Pointer;
	End;
	Procedure Search(x: keytype; Root: Pointer, Var P: Pointer);
	Begin
	P := Root;
	If P Nil then
	If x < P^.key then search(x, P^.left, P)
	Else if x > P^.key then search(x, P^.right, P)
	End;
	b) Xen vào cây tìm kiếm một lá
	Procedure Insert(Var Root: Pointer; x: keytype);
	{Xen vao goc Root dinh moi la khoa x}
	Var
	Q: Pointer;
	Begin
	If Root = nil then
	Begin
	New(Q); {Tao mot dinh moi}
	Q^.key := x;
	Q^.left := nil;
Q^.right := nil;
Root := Q;
	end
	else with Root^ do
if x < key then Insert(left,x)
else if x > key then insert(right,x);
	end;
	c) Loại bỏ khỏi cây tìm kiếm
	Khác với bài toán xen vào cây nhị phân tìm kiếm là xen thêm một lá, bài toán loại bỏ khỏi cây tìm kiếm một đỉnh có khoá x cho trước sao cho sau khi loại bỏ cây kết quả vẫn là cây nhị phân tìm kiếm. Việc loại bỏ một đỉnh rất đơn giản khi đó là một lá, nhưng khi đỉnh cần loại bỏ có một trong hai cây con là cây trống hay cả hai cây con đều khác trống thì vấn đề sẽ phức tạp hơn nhiều. Ta có nhận xét rằng, trong một cây tìm kiếm nhị phân khác trống bất kỳ, đỉnh có khoá nhỏ nhất là đỉnh ngoài cùng nằm bên trái, đỉnh có khoá lớn nhất là đỉnh ngoài cùng nằm bên phải. Do đó khi đỉnh cần loại bỏ có hai cây khác trống ta phải thay khoá của đỉnh cần loại bỏ bởi khoá khoá của đỉnh ngoài cùng bên phải của cây con trái (hoặc đỉnh ngoài cùng bên trái của cây con phải), rồi loại bỏ đỉnh ngoài cùng bên phải của cây con trái (hoặc đỉnh ngoài cùng bên trái của cây con phải). 
	Ví dụ minh hoạ: Cho cây T ban đầu như sau với T1, T2 cũng là các cây nhị phân tìm kiếm.
20
10
25
3
18
T1
T2
20
10
25
18
T1
T2
20
10
3
18
T1
T2
20
10
3
T1
T2
(a)
(b)
(c)
(d)
a) Cây T ban đầu
b) Cây T sau khi loại đỉnh 3 (Lá)
c) Cây T sau khi loại đỉnh 25 (Chỉ có một cây con khác trống)
c) Cây T sau khi loại đỉnh 20 (cả hai cây con khác trống)
	Thuật toán loại bỏ cây được mô tả trong thủ tục del sau, thủ tục này loại khỏi cây đỉnh mà con trỏ P trỏ tới, trong đó P là con trỏ liên kết trong cây.
Procedure Del(Var P: Pointer);
Var Q, Q1: Pointer;
Begin
If P^.right = nil then
Begin
Q := P;	P := P^.left;
End else
	If P^.left = nil then
	Begin
Q := P;
P := P^.right;
End 
else
Begin
Q := P^.left;
If Q^.right = nil then 
 Begin
P^.key := Q^.key;
P^.left := Q^.left;
End 
else
Begin
Repeat
	Q1 := Q;
	Q := Q^.right;
Until Q^.right = nil;
P^.key := Q^.key;
Q1^.right := Q^.left
End;
End;
Dispose(Q);
End;
	Khi đó thủ tục để loại bỏ khỏi cây gốc Root đỉnh có khoá x cho trước được viết đệ quy như sau: trước hết nó tìm ra đỉnh có khoá x, rồi sau đó áp dụng thủ tục Del để loại đỉnh đó ra khỏi cây
Procedure Delete(Var Root: Pointer; x: key);
Begin
	If Root nil then
	 If x < Root^.key then Delete(Root^.left,x) 	 else
	If x > Root^.key then Delete(Root^.right,x) 
	else Del(Root);
End;TÓM TẮT
	Trong chương này chúng ta đã nghiên cứu những khái niệm cơ bản về mô hình dữ liệu cây, một mô hình dữ liệu được sử dụng rất rộng rãi trong nhiều lĩnh vực, nhiều vấn đề khác nhau. Chẳng hạn như trong các hệ cơ sở dữ liệu, để mô tả cấu trúc cú pháp của các chương trình nguồn khi xây dựng chương trình dịch. Rất nhiều các bài toán mà ta gặp trong các lĩnh vực khác nhau được quy về việc thực hiện các phép toán trên cây. Đặc biệt là dạng mô hình cấu trúc của cây nhị phân. 
	Một ví dụ rất hay về cây nhị phân và ứng dụng của cây nhị phân là cây biểu thức. Cây biểu thức là cây nhị phân có gắn nhãn, biểu diễn cấu trúc của một biểu thức (số học hoặc Logic). Mỗi phép toán gồm hai toán hạng (chẳng hạn +, -, *, /) được biểu diễn bởi cây nhị phân, gốc của nó chứa ký hiệu phép toán, cây con trái biểu diễn toán hạng bên trái, còn cây con phải biểu diễn toán hạng bên phải. Với các phép toán một toán hạng như phủ định hoặc lấy giá trị đối hoặc các hàm chuẩn như exp( ), Cos( ).... thì cây con bên trái rỗng. Còn với các phép toán một toán hạng như phép lấy đạo hàm ( )' hoặc giai thừa ( )! thì cây con bên phải rỗng. 
	Ví dụ:
+
a
b
 a + b
x
exp(x)
 !
n
n!
a/(b + c)
/
a
+
b
c
(a = d)
or
>=
c
d
<
a
b
	Ngoài dạng cấu trúc cây nhị phân ra, còn có dạng cây K_phân là một dạng cấu trúc cây mà mỗi nút trên cây có tối đa là K nút con (có tính đến thứ tự của các nút con), và dạng cấu trúc cây tổng quát là cây mà không có sự ràng buộc gì về số con trên mỗi nút. Ta cũng có thể biểu diễn các cây này bằng mảng hay bằng cấu trúc liên kết. Về các cấu trúc cây này chúng tôi không đề cập trong giáo trình này. Bạn đọc có thể tự nghiên cứu tìm hiểu trong các cuốn giáo trình chuyên ngành.
BÀI TẬP CHƯƠNG 5
1. Trình bày các biểu thức duyệt tiền tự,trung tự, hậu tự của cây sau:
2. Duyệt cây theo mức là duyệt bắt đầu từ gốc, rồi duyệt các nút nằm trên mức 1 theo thứ tự từ trái sang phải, rồi đến các nút nằm trên mức 2 theo thứ tự từ trái sang phải...Và cứ như vậy.
a.    Hãy liệt kê các nút theo thứ tự duyệt theo mức của cây trong bài 1.
b.    Viết thủ tục duyệt cây theo mức. (Gợi ý: dùng hàng đợi)
3. Vẽ cây biểu diễn cho biểu thức ((a+b)+c*(d+e)+f)*(g+h)
Trình bày biểu thức tiền tố và hậu tố của biểu thức đã cho.
4. Viết chương trình để tính giá trị của biểu thức khi cho:
a.         Biểu thức tiền tố
b.         Biểu thức hậu tố.
Ví dụ:
-       Đầu vào (input): * + 6 4 5
-       Thì đầu ra (output) sẽ là: 50 vì biểu thức trên là dạng tiền tố của biểu thức (6+4) * 5
Tương tự:
-       Đầu vào (input): 6 4 5 + *
-       Thì đầu ra (output) sẽ là: 54 vì biểu thức trên là dạng hậu tố của biểu thức 6 * (4+5)
5. Cho cây nhị phân
	a.         Hãy trình bày các duyệt: tiền tự (node-left-right), trung tự (left-node-right), hậu tự (left-right-node).
	b.         Minh hoạ sự lưu trữ kế tiếp các nút cây này trong mảng.
6. Chứng minh rằng: nếu biết biểu thức duyệt tiền tự và trung tự của một cây nhị phân thì ta dựng được cây này. Ðiều đó đúng nữa không? Khi biết biểu thức duyệt:
a.       Tiền tự và hậu tự
b.      Trung tự và hậu tự
7. Giả sử ta khai báo cấu trúc dữ liệu để cài đặt cây nhị phân như sau:
Type	TREE = ^node;
	node = record
	parent: TREE;
	left,right: TREE;
	end;
Hãy viết các thủ tục/ hàm sau:
-       Procedure MakeNullTree(var T:TREE); khởi tạo cây rỗng
-       Function EmptyTree(T:TREE): boolean; kiểm tra cây rỗng
-       Function IsLeaf(n:TREE): Boolean; kiểm tra nút n có phải là nút lá không.
-       Function IsRoot(n:TREE): Boolean; kiểm tra nút n có phải là nút gốc không.
-       Function isParent(n,m:TREE): Boolean; kiểm tra nút n có phải là nút cha của nút m không.
	-       Function isAncestor(n,m:TREE): Boolean; kiểm tra nút n có phải là nút tiền bối của nút m không.
-       Function Height(n:TREE):integer; để tính chiều cao của nút n.
-       Function Depth(n:TREE):integer; để tính độ sâu của nút n.
-       Function nb_nodes(T:TREE):integer; tính số nút của cây có nút gốc T.
-       Viết các thủ tục duyệt tiền tự, trung tự, hậu tự.
-       Viết thủ tục/hàm đếm số nút lá của cây.
-       Viết thủ tục / hàm đếm số nút trung gian của cây.
Bài Thực Tập Số 1 : CÀI ÐẶT DANH SÁCH BẰNG MẢNG
Viết chương trình quản lý dòng văn bản.
Yêu cầu chi tiết: 
1. Viết phần khai báo để cài đặt một dòng văn bản (nội dung của văn bản là các ký tự, chiều dài tối đa của 1 dòng là 80 ký tự). 
2. Viết thủ tục khởi tạo dòng rỗng 
3. Thiết kế hàm kiểm tra dòng rỗng. 
4. Thiết kế hàm kiểm tra dòng đầy. 
5. Viết thủ tục nhập một dòng văn bản. 
6. Viết thủ tục hiển thị dòng văn bản ra màn hình. 
7. Viết thủ tục xen một ký tự x vào vị trí thứ p nào đó trong dòng văn bản D. 
8. Viết thủ tục xóa một ký tự tại vị trí thứ p nào đó ra khỏi dòng văn bản D. 
9. Thiết kế hàm copy một dòng văn bản để có một dòng văn bản mới. Copy k ký tự từ dòng D sang dòng D1 bắt đầu từ vị trí p trong dòng D (Không sử dụng hàm chuẩn của Pascal). 
10. Viết hàm tìm vị trí của phần tử đầu tiên trong dòng văn bản có nội dung là x. 
11. Viết thủ tục thay thế tất cả các ký tự c trong dòng văn bản D bằng ký tự c1. 
12. Thiết kế hàm hoặc thủ tục lấy nội dung của phần tử thứ p trong dòng. 
13. Viết thủ tục xóa tất cả các ký tự c trong dòng văn bản D. 
14. Viết thủ tục cắt các khoảng trắng dư (các khoảng trắng không cần thiết) giữa 2 ký tự trong một dòng. 
15. Thiết kế hàm kiểm tra dòng văn bản D1 có phải là dòng con của dòng văn bản D hay không. 
Viết chương trình nhập một dòng văn bản từ bàn phím, cắt tất cả các khoảng trống không cần thiết trong dòng này. Thay thế ký tự đầu dòng bằng ký tự hoa. Chép dòng văn bản này sang dòng mới để khi thao tác thì dòng văn bản cũ không bị mất đi. 
Trên dòng văn bản mới ta thực hiện các thao tác sau đây: 
	Xen một ký tự mới vào dòng. 
	Xóa một ký tự ra khỏi dòng. 
	Thay thế tất cả các ký tự nào đó trong dòng bằng ký tự mới. 
	Xóa tất cả các ký tự c trong dòng (c được nhập từ bàn phím). 
	Nhập một dòng văn bản mới và kiểm tra xem dòng văn bản này có phải là dòng con của dòng văn bản đang lưu trữ hay không?
Bài Thực tập số 2: CÀI ÐẶT DANH SÁCH LIÊN KẾT BẰNG CON TRỎ 
A. DANH SÁCH LIÊN KẾT ÐƠN 
 	Viết chương trình lưu trữ đa thức có dạng: 
Yêu cầu chi tiết: 
1. Viết các khai báo cần thiết để cài đặt một đa thức như trên. 
2. Viết thủ tục khởi tạo một đa thức rỗng. 
3. Viết hàm kiểm tra đa thức rỗng. 
4. Xen một phần tử mới x vào đa thức D sau vị trí p. 
5. Xóa một phần tử x sau vị trí p ra khỏi đa thức D. 
6. Viết thủ tục nhập một đa thức. 
7. Thiết kế hàm kiểm tra tính chuẩn hóa của đa thức (ứng với mỗi cấp số mũ thì chỉ có duy nhất một hệ số a tương ứng với nó). 
	Ví dụ : 2x3 + 3x3 	 Sai.	Ta phải viết thành: 5x3 
8. Thiết lập một hàm chuyển đa thức về dạng chuẩn hóa. 
9. Viết thủ tục hiển thị đa thức ra màn hình. 
10. Viết thủ tục sắp xếp đa thức theo thứ tự giảm dần của số mũ. 
11. Viết thủ tục cộng 2 đa thức D1 và D2 thành đa thức D3 
12. Viết thủ tục trừ 2 đa thức D1 và D2 thành đa thức D3 
13. Viết thủ tục nhân 2 đa thức D1 và D2 thành đa thức D3 
14. Viết hàm tính giá trị của đa thức với giá trị đã cho của x được nhập từ bàn phím. 
	Viết chương trình nhập vào một đa thức rồi thực hiện các yêu cầu sau: 
	- Hiển thị đa thức đã nhập. 
	- Xen một phần tử mới vào đa thức. 
	- Xóa một phần tử khỏi đa thức. 
	Chuẩn hóa đa thức, hiển thị đa thức sau khi đã chuẩn hóa (nếu đa thức là đa thức chưa chuẩn hóa). 
	Sắp xếp đa thức theo số mũ giảm dần, hiển thị đa thức sau khi đã sắp xếp. 
	Nhập vào 2 đa thức D1, D2 và thực hiện các phép toán cộng, trừ, nhân trên hai đa thức này. Hiển thị kết quả của mỗi phép toán để kiểm tra. 
	Nhập giá trị cho biến x và tính giá trị của đa thức. 
B. DANH SÁCH LIÊN KẾT KÉP 
 	Viết chương trình lưu trữ một danh sách các số nguyên, sắp xếp danh sách theo thứ tự (tăng hoặc giảm), trộn 2 danh sách có thứ tự để được một danh sách mới có thứ tự. 
Yêu cầu chi tiết: 
1. Viết các khai báo cần thiết để cài đặt một danh sách các số nguyên. 
2. Viết thủ tục khởi tạo một danh sách rỗng. 
3. Viết hàm kiểm tra danh sách rỗng. 
4. Viết thủ tục nhập một danh sách. 
5. Viết thủ tục hiển thị danh sách ra màn hình. 
6. Viết thủ tục sắp xếp danh sách theo thứ tự (tăng hoặc giảm). 
7. Xen một phần tử mới x vào danh sách sau cho danh sách mới vẫn bảo đảm thứ tự. 
8. Xóa một phần tử x ra khỏi danh sách sao cho danh sách mới vẫn bảo đảm thứ tự. 
9. viết thủ tục trộn 2 danh sách đã có thứ tự thành một danh sách mới sao cho danh sách mới vẫn bảo đảm thứ tự. 
	Viết chương trình nhập vào một danh sách các số nguyên và thực hiện các yêu cầu sau: 
	Hiển thị danh sách vừa nhập. 
	Sắp xếp danh sách theo thứ tự. Hiển thị danh sách sau khi sắp xếp. 
	Xen một phần tử mới vào danh sách. Hiển thị danh sách mới sau khi xen. 
	Xóa một phần tử khỏi danh sách. Hiển thị danh sách mới sau khi xóa. 
	Nhập 2 danh sách, sắp xếp 2 danh sách theo thứ tự, sau đó trộn 2 danh sách này để được một danh sách mới cũng có thứ tự. Hiển thị danh sách mới ra màn hình để kiểm tra. 
Bài Thực Tập Số 3 : CẤU TRÚC NGĂN XẾP (STACK) & HÀNG (QUEUE) 
	Ứng dụng ngăn xếp (Stack) và hàng Queue để viết chương trình biến đổi biểu thức trung tố thành tiền tố và hậu tố. 
	Viết chương trình tính giá trị của biểu thức tiền tố và hậu tố. 
Yêu cầu chi tiết: 
1. Viết các khai báo cần thiết để cài đặt một Stack, một Queue. 
2. Viết thủ tục khởi tạo một Stack rỗng. 
3. Viết hàm kiểm tra Stack rỗng. 
4. Viết thủ tục thêm một phần tử vào Stack. 
5. Viết thủ tục xóa một phần tử khỏi Stack. 
6. Viết chương trình con lấy nội dung của phần tử tại đỉnh của Stack. 
7. Viết thủ tục khởi tạo một Queue rỗng. 
8. Viết hàm kiểm tra Queue rỗng. 
9. Viết thủ tục thêm một phần tử vào Queue. 
10. Viết thủ tục xóa một phần tử khỏi Queue. 
11. Viết chương trình con lấy nội dung của phần tử tại đỉnh của Queue. 
12. Viết chương trình con đổi biểu thức từ dạng trung tố sang dạng tiền tố. 
13. Viết chương trình con đổi biểu thức từ dạng trung tố sang dạng hậu tố. 
14. Viết chương trình con tính giá trị của biểu thức tiền tố. 
15. Viết chương trình con tính giá trị của biểu thức hậu tố. 
Giải thuật chuyển đổi biểu thức từ dạng trung tố sang dạng hậu tố 
 Procedure HAUTO ( BT: Biểu thức trung tố ; Var HT: Hàng chứa biểu thức hậu tố sau khi đổi } 
Begin 
	MakeNullS(S);	{ Tạo một Stack rỗng } 
	MakeNullQ(S);	{ Tạo một Queue rỗng } 
	x = Phần tử đầu tiên trong biểu thức trung tố 
	While chưa xét hết biểu thức trung tố do 
	Begin 
	If x = '(' then Push (x,S) { thêm x vào Stack } 
	If x = ')' then 
	Begin 
	While (Not Empty(S)) and (Top(S) '(') do 
	Begin 
	Y:= Top (S);	EnQueue(y,Q); {Thêm Y vào hàng} 
	Pop(S);	{xóa phần tử tại đỉnh Stack} 
	End; 
	If EmptyS(S) then báo lỗi Stack rỗng 
	Else	Pop(S)	{ xóa phần tử tại đỉnh Stack } 
	End; { If } 
	If then 
	If EmptyS(S) then	Push (x,S)	{thêm x vào Stack} 
	Else	
	Begin 
	 While (Uutien(Top(S))'(') do 
	Begin 
	Y:= Top(S); 
	Enqueue(Y,Q); 
	Pop(S); 
	End; 
	Push(x,S); 
	End; 
	If then 
	EnQueue(x,Q); 
	X = phần tử kế tiếp trong biểu thức trung tố 
	End; { While } 
	While Not EmptyS(S) do	
	Begin 
	Y:= Top(S); 
	Enqueue(Y,Q); 
	Pop(S); 
	End;	
End; { Thủ tục } 
Trong đó hàm Uutien trả về thứ tự ưu tiên của các toán tử như sau: 
Toán tử 
( , ) 
* , / 
+ , - 
Thứ tự ưu tiên 
1 
2 
3 
Bài Thực Tập Số 4 : CẤU TRÚC CÂY 
	Viết chương trình cài đặt một cây biểu thức, tính trị của cây biểu thức này. 
Yêu cầu chi tiết: 
1. Viết phần khai báo để cài đặt một cây biểu thức. 
2. Viết thủ tục khởi tạo cây rỗng. 
3. Viết hàm kiểm tra cây rỗng. 
4. Thiết kế hàm tạo cây từ cây con trái L, cây con phải R và nhãn của nút n, bằng cách xem đây là có nút gốc là n và 2 cây con tương ứng là L (con trái) và R (con phải). 
5. Viết các thủ tục duyệt cây: 
	Duyệt tiền tự, trung tự, hậu tự . 	
	Duyệt theo mức. 
6. Viết hàm xác định số nút trong cây. 
7. Thiết kế hàm xác định chiều cao của cây. 
8. Viết hàm tính giá trị của cây biểu thức. 
9. Viết hàm xác định mức của một nút trong cây. 
-----------------cd-----------------
TÀI LIỆU THAM KHẢO
1. Cấu trúc Dữ liệu & Thuật toán
	Tg: TS Đinh Mạnh Tường; NXB: Khoa học và Kỹ thuật - 2003
2. Cấu trúc Dữ liệu + Giải thuật = Chương trình
	Tg: Nguyễn Quốc Cường, Hoàng Đức Hải; NXB: Giáo Dục - 1999
3. Cấu trúc Dữ liệu và Giải thuật
	Tg: Đỗ Xuân Lôi; NXB: Giáo Dục - 1993
4. Cơ sở toán trong lập trình
	Tg: Pgs, Pts Đỗ Đức Giáo; NXB: Khoa học và Kỹ thuật - 1998
5. Lập trình nâng cao bằng PASCAL với các cấu trúc Dữ liệu (2 tập)
	Tg: Larry Nyhoff - Sanford Leedstma; NXB: Đà nẵng - 1998
6. Giáo trình thuật toán
	Tg: Thomat H.Cormen, Charles E.Leiserson, Ronal L.Rivest;
	NXB: Thống kê - 2002