CẤU TRÚC CÂY
I. ÐỊNH NGHĨA VÀ CÁC KHÁI NIỆM CƠ BẢN
1. Ðịnh nghĩa :
Cây (Trees) là một tập hợp hữu hạn các phần tử gọi là nút cây (Node), trong đó có một nút đặc biệt gọi là nút gốc (Root). Trên tập hợp các nút này có
một quan hệ phân cấp gọi là quan hệ "cha - con".
Một nút có thể có kiểu bất ký, ta thường biểu diễn nút bằng tên nút. Tên nút có thể là một ký tự, một số hay một chuỗi và có thể được ghi trong một
vòng tròn. Ta quy ước biểu diễn cây như sau: Ta viết nút cha ở dòng trên, các nút con ở dòng dưới và quan hệ "cha-con" được biểu diễn bằng một đoạn
thẳng nối liền 2 nút.
Ví dụ :
Ngoài ra ta có thể định nghĩa cây một cách đệ qui như sau :
Một nút (đơn độc) là một cây và nút đó cũng là nút gốc của cây.
Nếu ta có n là một nút và T1, T2, ..., Tk là các cây với n1, n2,..., nk lần lượt là các nút gốc của các cây con thì ta có thể xây dựng một cây mới
bằng cách cho n trở thành cha của các nút n1, n2,..., nk; Nghĩa là trên cây mới này n là nút gốc còn các cây T1, T2, ..., Tk là các cây con của nút n.
Ðể tiện việc quản lý, người ta cho phép tồn tại một cây không có nút nào, mà ta gọi là cây rỗng (Null tree).
2. Các khái niệm cơ bản :
Một nút đơn độc cũng là một cây.
Tập hợp rỗng cũng là một cây mà ta gọi là cây rỗng.
Mức của một nút :
+ Nút gốc : Mức 0.
+ Các nút cách nút gốc i cạnh được gọi là nút ở mức i.
1
Ví dụ:
Cha - con: Nút A là nút cha của nút B khi nút A ở mức i và nút B ở mức i+1. Ðồng thời có một cạnh nối giữa cặp nút A và B (ta còn gọi B là con
của A).
Cha - ông (con - cháu)/ tiền bối - hậu duệ: Nếu có một đường nối từ nút A đến nút B và mức của nút A < mức của nút B thì ta nói A là cha ông
(tiền bối) của B và B gọi là con cháu (hậu duệ) của A.
Anh em ruột: Các nút con của cùng một nút cha được gọi là các nút anh em ruột.
Ðường đi: Cho một dãy các nút n1, n2,..., nk sao cho ni là nút cha của ni+1 thì ta nói n1 ( n2 ( ...( nk là một đường đi từ nút n1 ( nk. Ðộ dài của
đường đi bằng số nút trên đường đi trừ 1 hay bằng số cạnh trên đường đi.
Nút gốc (Root): Là nút không có nút cha.
Nút lá (leaf): Là nút không có nút con.

Trong cây trên thì n1, n2,..., n7 là các tên nút còn *, +, -, a, b, c là các nhản của nút.
5. Quy 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á sẽ biểu diễn cho một toán hạng đơn độc.
Mỗi nút trung gian sẽ biểu diễn cho một toán tử. Giả sử nút n biểu diễn cho toán tử 2 ngôi, nút con bên trái biểu diễn cho biểu thức E1, nút con bên
phải biểu diễn cho biểu thức E2 thì nút n sẽ biểu diễn cho biểu thức Eı E2
Thông thường khi chúng ta duyệt cây thì danh sách duyệt cây là một danh sách các nhản nút. Trong trường hợp cây biểu diễn cho biểu thức toán học
thì biểu thức duyệt tiền tự cho chúng ta biểu thức tiền tố (Prefix), duyệt trung tự cho chúng ta biểu thức trung tố (Infix) và duyệt hậu tự cho chúng ta biểu
thức hậu tố (Postfix) của biểu thức toán học ban đầu.
Ví dụ: Ðối với cây biểu thức được cho ở ví dụ trên, ta có:
+ Biểu thức tiền tố : * + a b - a c.
+ Biểu thức trung tố : a + b * a - c.
+ Biểu thức hậu tố : a b + a c - *.
4
II. KIỂU DỮ LIỆU TRỪU TƯỢNG CÂY
1. Các phép toán trên cây
Hàm Parent (n : Node; T : Tree) : Cho kết quả 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 kết quả là Null.
Hàm RightSibling (n : Node; T : Tree) : Cho kết quả là nút anh ruột phải của nút n trên cây T. Nếu n không có anh ruột phải thì hàm cho kết quả
là Null.
Hàm LeftMostChild (n : Node; T : Tree) : Cho kết quả là nút con trái nhất của nút n trên cây T. Nếu n không có con trái nhất thì hàm cho kết quả là
Null.
Hàm Root (T : Tree) : Cho kết quả là nút gốc của cây T. Nếu cây rỗng thì hàm cho kết quả là Null.
Thủ tục Createi (V, T1, T2,..., Ti) : Là thủ tục tạo cây mới có nhản gốc là V và i cây con T1, T2,..., Ti. Nếu i = 0 thì cây mới tạo chỉ có một nút
đơn độc.
Hàm LabelNode(n : Node; T : Tree) : Cho nhản của nút n của cây T.
Ví dụ : Dùng các phép toán trên để viết các thủ tục duyệt cây :
Procedure PreOrder (T : Tree);
Var n, c : Node;
Begin
n := Root (T);
Write (LabelNode (n, T);

End;
End;
2. Cài đặt cây
a. Cài đặt cây bằng mảng
Cho một cây T có các nút 1, 2, 3, ... , n. Ta có thể dùng mảng A 1 chiều để lưu trữ cây bằng cách cho A[i] = j. Với j là nút cha của nút i. Nếu i là nút
gốc thì ta cho A[i] = Null. (Cụ thể là Null = 0).
Ví dụ : Cây : Ðược biểu diễn trong mảng A như sau :
Nếu cây T có nhản ta có thể dùng thêm một mảng 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, hoặc khai báo
mảng A là mảng của các Record gồm có 2 trường : Trường Parent giữ chỉ số của nút cha; trường Labels giữ nhản của nút.
Khai báo :
Const Maxlenght = ... ;
Type ElementType = ... {Kiểu nhản} ;
Tree = Record
Parent: Array [1.. Maxlenght] of Integer;
Labels: Array [1.. Maxlenght] of ElementType;
End;
Var T:Tree;
NumNode: Integer; { Số nút tối đa trên cây }
6
Với cách cài đặt này hàm Parent chỉ tốn một hằng thời gian nhưng các hàm khác thì rất khó cài đặt, để khắc phục tình trạng này người ta quy ước
việc đặt tên nút như sau :
+ Ðánh số theo thứ tự tăng dần bắt đầu từ nút gốc.
+ Tại mỗi nút thì nút cha được đánh số trước rồi lần lượt đến các nút con từ trái sang phải.
b. Biểu diễn cây bằng danh sách các con
Một cách biểu diễn khác cũng thường được dùng là biểu diễn cây dưới dạng mỗi nút có một danh sách các nút con. Danh sách có thể được cài đặt
bằng bất kỳ cách nào mà ta đã biết. Tuy nhiên, vì số lượng các nút con của một nút là không biết trước nên cài đặt bằng danh sách liên kết sẽ thích hợp
hơn.
Ví dụ : Cây ở ví dụ trước có thể được lưu trữ theo dạng :
Nhận xét : Các hàm tìm kiếm thông tin về các con rất thuận lợi, nhưng hàm parent lại bất tiện. Ví dụ như cần tìm nút cha của nút 8 thì ta phải duyệt
qua tất cả các danh sách mới tìm ra kết quả.