TỔNG QUÁTXUẤTNODETHEOĐIỀUKIỆNĐẾMNODETHEOĐIỀUKIỆNTÍNHTỔNGCÁC GIÁTRỊ CỦANODETHEOĐIỀUKIỆNVÍ DỤ: Áp dụng cho các node có gtrị là số chẵnvoid Xuat[Tree T]{if [T!=NULL]{if [T->left != NULL]Xuat[T->left];if [………]printf["%4d", T->key];if [T->right != NULL]Xuat[T->right];}}void Xuat[Tree T]{if [T!=NULL]{if [T->left != NULL]Xuat[T->left];if [T->key % 2 == 0]printf["%4d", T->key];if [T->right != NULL]Xuat[T->right];}}int Dem[Tree T]{if [T!=NULL]{int a = Dem[T->left];int b = Dem[T->right];if [………]return 1 + a + b;return a + b;}return 0;}int Dem[Tree T]{if [T!=NULL]{int a = Dem[T->left];int b = Dem[T->right];if [T->key%2==0]return 1 + a + b;return a + b;}return 0;}int Tinh[Tree T]{if [T!=NULL]{int a = Tinh[T->left];int b = Tinh[T->right];if [………]return T->key + a + b;return a + b;}return 0;}int Tinh[Tree T]{if [T!=NULL]{int a = Tinh[T->left];int b = Tinh[T->right];if [T->key % 2 == 0]return T->key + a + b;return a + b;}return 0;}Viết hàm xuất các giá trị trong câyViết hàm xuất các giá trị chẵn trong câyviết xuất địa chỉ các nút trên cây có giá trị [khoá] lớn hơn x và nhỏ hơn yViết hàm xuất các số hoàn thiện trong câyViết hàm xuất tất cả các nút trên tầng thứ k của câyViết hàm xuất tất cả các nút trên cây theo thứ tự từ tầng 0 đến tầng h-1 củacây [với hlà chiều cao của cây]Đếm số lượng nút có đúng 1 conĐếm số lượng nút có đúng 2 conĐếm số lượng nút chẵnĐếm số lượng nút lá mà thông tin tại nút đó là giá trị chẵnĐếm số lượng nút có đúng 1 con mà thông tin tại nút đó là số nguyên tốĐếm số lượng nút có đúng 2 con mà thông tin tại nút đó là số chính phươngĐếm số lượng nút trên tầng thứ k của câyĐếm số lượng nút nằm ở tầng thấp hơn tầng thứ k của câyĐếm số lượng nút nằm ở tầng cao hơn tầng thứ k của câyTính tổng các nút trong câyTính tổng các nút lá trong câyTính tổng các nút có đúng một conTính tổng các nút có đúng hai conTính tổng các nút lẻtính tổng các nút lá mà thông tin tại nút đó là giá trị chẵnTính tổng các nút có đúng 1 con mà thông tin tại nút đó là số nguyên tốTính tổng các nút có đúng 2 con mà thông tin tại nút đó là số chính phươngTính chiều cao câyKiểm tra cây nhị phân T có phải là "cây nhị phân tìm kiếm" hay không?Kiểm tra cây nhị phân T có phải là "cây nhị phân cân bằng" hay không?
Cấu trúc dữ liệu trừu tượng ta quan tâm tới trong mục này là cấu trúc cây. Cây là một cấu trúc dữ liệu gồm một tập hữu hạn các nút, giữa các nút có một quan hệ phân cấp gọi là quan hệ "cha - con". Có một nút đặc biệt gọi là gốc [root].
Có thể định nghĩa cây bằng các đệ quy như sau:
Mỗi nút là một cây, nút đó cũng là gốc của cây ấy
Nếu n là một nút và n1, n2, …, nk lần lượt là gốc của các cây T1, T2, …, Tk; các cây này đôi một không có nút chung. Thì nếu cho nút n trở thành cha của các nút n1, n2, …, nk ta sẽ được một cây mới T. Cây này có nút n là gốc còn các cây T1, T2, …, Tk trở thành các cây con [subtree] của gốc.
Để tiện, người ta còn 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].
Xét cây trong Hình 1:
Hình 1: Cây [Tree]
A là cha của B, C, D, còn G, H, I là con của D.
Số các con của một nút được gọi là cấp của nút đó, ví dụ cấp của A là 3, cấp của B là 2, cấp của C là 0.
Nút có cấp bằng 0 được gọi là nút lá [leaf] hay nút tận cùng. Ví dụ như ở trên, các nút E, F, C, G, J, K và I là các nút là. Những nút không phải là lá được gọi là nút nhánh [branch].
Cấp cao nhất của một nút trên cây gọi là cấp của cây đó, cây ở hình trên là cây cấp 3.
Gốc của cây người ta gán cho số mức là 1, nếu nút cha có mức là i thì nút con sẽ có mức là i + 1. Mức của cây trong Hình 1 được chỉ ra trong Hình 12:
Hình 2: Mức của các nút trên cây
Chiều cao [height] hay chiều sâu [depth] của một cây là số mức lớn nhất của nút có trên cây đó. Cây ở trên có chiều cao là 4.
Một tập hợp các cây phân biệt được gọi là rừng [forest], một cây cũng là một rừng. Nếu bỏ nút gốc trên cây thì sẽ tạo thành một rừng các cây con.
Ví dụ:
Mục lục của một cuốn sách với phần, chương, bài, mục v.v… có cấu trúc của cây
Cấu trúc thư mục trên đĩa cũng có cấu trúc cây, thư mục gốc có thể coi là gốc của cây
đó với các cây con là các thư mục con và tệp nằm trên thư mục gốc.
Gia phả của một họ tộc cũng có cấu trúc cây.
Một biểu thức số học gồm các phép toán cộng, trừ, nhân, chia cũng có thể lưu trữ trong một cây mà các toán hạng được lưu trữ ở các nút lá, các toán tử được lưu trữ ở các nút nhánh, mỗi nhánh là một biểu thức con.
Hình 3: Cây biểu diễn biểu thức
CÂY NHỊ PHÂN [BINARY TREE]
Cây nhị phân là một dạng quan trọng của cấu trúc cây. Nó có đặc điểm là mọi nút trên cây chỉ có tối đa hai nhánh con. Với một nút thì người ta cũng phân biệt cây con trái và cây con phải của nút đó. Cây nhị phân là cây có tính đến thứ tự của các nhánh con.
Cần chú ý tới một số dạng đặc biệt của cây nhị phân.
Các cây nhị phân trong Hình 4 được gọi là cây nhị phân suy biến [degenerate binary tree], các nút không phải là lá chỉ có một nhánh con. Cây a] được gọi là cây lệch phải, cây b] được gọi là cây lệch trái, cây c] và d] được gọi là cây zíc-zắc.
Hình 4: Các dạng cây nhị phân suy biến
Các cây trong Hình 5 được gọi là cây nhị phân hoàn chỉnh [complete binary tree]: Nếu chiều cao của cây là h thì mọi nút có mức < h - 1 đều có đúng 2 nút con. Còn nếu mọi nút có mức ≤ h - 1 đều có đúng 2 nút con như trường hợp cây f] ở trên thì cây đó được gọi là cây nhị phân đầy đủ [full binary tree]. Cây nhị phân đầy đủ là trường hợp riêng của cây nhị phân hoàn chỉnh.
Hình 5: Cây nhị phân hoàn chỉnh và cây nhị phân đầy đủ
Ta có thể thấy ngay những tính chất sau bằng phép chứng minh quy nạp:
Trong các cây nhị phân có cùng số lượng nút như nhau thì cây nhị phân suy biến có chiều cao lớn nhất, còn cây nhị phân hoàn chỉnh thì có chiều cao nhỏ nhất.
Số lượng tối đa các nút trên mức i của cây nhị phân là 2i-1, tối thiểu là 1 [i ≥1].
Số lượng tối đa các nút trên một cây nhị phân có chiều cao h là 2h-1, tối thiểu là h [h ≥ 1]. Cây nhị phân hoàn chỉnh, không đầy đủ, có n nút thì chiều cao của nó là h = [log2[n + 1]] + 1.
Cây nhị phân đầy đủ có n nút thì chiều cao của nó là h = log2[n + 1].
BIỂU DIỄN CÂY NHỊ PHÂN
Nếu có một cây nhị phân đầy đủ, ta có thể dễ dàng đánh số cho các nút trên cây đó theo thứ tự lần lượt từ mức 1 trở đi, hết mức này đến mức khác và từ trái sang phải đối với các nút ở mỗi mức.
Hình 6: Đánh số các nút của cây nhị phân đầy đủ để biểu diễn bằng mảng
Với cách đánh số này, con của nút thứ i sẽ là các nút thứ 2i và 2i + 1. Cha của nút thứ j là nút j div 2. Từ đó có thể lưu trữ cây bằng một mảng T, nút thứ i của cây được lưu trữ bằng phần tử T[i].
Với cây nhị phân đầy đủ ở Hình 6 thì khi lưu trữ bằng mảng, ta sẽ được mảng như sau:
Trong trường hợp cây nhị phân không đầy đủ, ta có thể thêm vào một số nút giả để được cây nhị phân đầy đủ, và gán những giá trị đặc biệt cho những phần tử trong mảng T tương ứng với những nút này. Hoặc dùng thêm một mảng phụ để đánh dấu những nút nào là nút giả tự ta thêm vào. Chính vì lý do này nên với cây nhị phân không đầy đủ, ta sẽ gặp phải sự lãng phí bộ nhớ vì có thể sẽ phải thêm rất nhiều nút giả vào thì mới được cây nhị phân đầy đủ.
Ví dụ với cây lệch trái, ta phải dùng một mảng 31 phần tử để lưu cây nhị phân chỉ gồm 5 nút.
Hình 7: Nhược điểm của phương pháp biểu diễn cây bằng mảng
Khi biểu diễn cây nhị phân bằng cấu trúc liên kết, mỗi nút của cây là một bản ghi [record] gồm 3 trường:
Trường Info: Chứa giá trị lưu tại nút đó.
Trường Left: Chứa liên kết [con trỏ] tới nút con trái, tức là chứa một thông tin đủ để biết nút con trái của nút đó là nút nào, trong trường hợp không có nút con trái, trường này được gán một giá trị đặc biệt.
Trường Right: Chứa liên kết [con trỏ] tới nút con phải, tức là chứa một thông tin đủ để biết nút con phải của nút đó là nút nào, trong trường hợp không có nút con phải, trường này được gán một giá trị đặc biệt.
Hình 8: Cấu trúc nút của cây nhị phân
Đối với cây ta chỉ cần phải quan tâm giữ lại nút gốc, bởi từ nút gốc, đi theo các hướng liên kết Left, Right ta có thể duyệt mọi nút khác.
Hình 9: Biểu diễn cây bằng cấu trúc liên kết
Phép xử lý các nút trên cây mà ta gọi chung là phép thăm [Visit] các nút một cách hệ thống sao cho mỗi nút chỉ được thăm một lần gọi là phép duyệt cây.
Giả sử rằng nếu như một nút không có nút con trái [hoặc nút con phải] thì liên kết Left [Right] của nút đó được liên kết thẳng tới một nút đặc biệt mà ta gọi là NIL [hay NULL], nếu cây rỗng thì nút gốc của cây đó cũng được gán bằng NIL. Khi đó có ba cách duyệt cây hay được sử dụng:
Duyệt theo thứ tự trước [preorder traversal]
Trong phép duyệt theo thứ tự trước thì giá trị trong mỗi nút bất kỳ sẽ được liệt kê trước giá trị lưu trong hai nút con của nó, có thể mô tả bằng thủ tục đệ quy sau:
procedure Visit[N]; {Duyệt nhánh cây nhận N là nút gốc của nhánh đó}
begin
if N ≠ nil then begin
Visit[Nút con trái của N];
Visit[Nút con phải của N];
end;
end;
Quá trình duyệt theo thứ tự trước bắt đầu bằng lời gọi Visit[nút gốc].
Như cây ở Hình 9, nếu ta duyệt theo thứ tự trước thì các giá trị sẽ lần lượt được liệt kê theo thứ tự:
A B D H I E J C F K G L
Trong phép duyệt theo thứ tự giữa thì giá trị trong mỗi nút bất kỳ sẽ được liệt kê sau giá trị lưu ở nút con trái và được liệt kê trước giá trị lưu ở nút con phải của nút đó, có thể mô tả bằng thủ tục đệ quy sau:
procedure Visit[N]; {Duyệt nhánh cây nhận N là nút gốc của nhánh đó}
begin
if N ≠ nil then begin
Visit[Nút con trái của N];
Visit[Nút con phải của N];
end;
end;
Quá trình duyệt theo thứ tự giữa cũng bắt đầu bằng lời gọi Visit[nút gốc].
Như cây ở Hình 9, nếu ta duyệt theo thứ tự giữa thì các giá trị sẽ lần lượt được liệt kê theo thứ tự:
H D I B E J A K F C G L
Duyệt theo thứ tự sau [postorder traversal]
Trong phép duyệt theo thứ tự sau thì giá trị trong mỗi nút bất kỳ sẽ được liệt kê sau giá trị lưu ở hai nút con của nút đó, có thể mô tả bằng thủ tục đệ quy sau:
procedure Visit[N]; {Duyệt nhánh cây nhận N là nút gốc của nhánh đó}
begin
if N ≠ nil then begin
Visit[Nút con trái của N];
Visit[Nút con phải của N];
end;
end;
Quá trình duyệt theo thứ tự sau cũng bắt đầu bằng lời gọi Visit[nút gốc].
Cũng với cây ở Hình 9, nếu ta duyệt theo thứ tự sau thì các giá trị sẽ lần lượt được liệt kê theo thứ tự:
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 K nút con [có tính đến thứ tự của các nút con].
Cũng tương tự như việc biểu diễn cây nhị phân, người ta có thể thêm vào cây K_phân một số nút giả để cho mỗi nút nhánh của cây K_phân đều có đúng K nút con, các nút con được xếp thứ tự từ nút con thứ nhất tới nút con thứ K, sau đó đánh số các nút trên cây K_phân bắt đầu từ 0 trở đi, bắt đầu từ mức 1, hết mức này đến mức khác và từ "trái qua phải" ở mỗi mức.
Theo cách đánh số này, nút con thứ j của nút i là: i * K + j. Nút cha của nút x là nút [x - 1] div K. Ta có thể dùng một mảng T đánh số từ 0 để lưu các giá trị trên các nút: Giá trị tại nút thứ i được lưu trữ ở phần tử T[i].
Hình 10: Đánh số các nút của cây 3_phân để biểu diễn bằng mảng
Biểu diễn cây K_phân bằng cấu trúc liên kết
Khi biểu diễn cây K_phân bằng cấu trúc liên kết, mỗi nút của cây là một bản ghi [record] gồm hai trường:
Trường Info: Chứa giá trị lưu trong nút đó.
Trường Links: Là một mảng gồm K phần tử, phần tử thứ i chứa liên kết [con trỏ] tới nút con thứ i, trong trường hợp không có nút con thứ i thì Links[i] được gán một giá trị đặc biệt.
Đối với cây K_ phân, ta cũng chỉ cần giữ lại nút gốc, bởi từ nút gốc, đi theo các hướng liên kết có thể đi tới mọi nút khác.
CÂY TỔNG QUÁT
Trong thực tế, có một số ứng dụng đòi hỏi một cấu trúc dữ liệu dạng cây nhưng không có ràng buộc gì về số con của một nút trên cây, ví dụ như cấu trúc thư mục trên đĩa hay hệ thống đề mục của một cuốn sách. Khi đó, ta phải tìm cách mô tả một cách khoa học cấu trúc dữ liệu dạng cây tổng quát. Cũng như trường hợp cây nhị phân, người ta thường biểu diễn cây tổng quát bằng hai cách: Lưu trữ kế tiếp bằng mảng và lưu trữ bằng cấu trúc liên kết.
Biểu diễn cây tổng quát bằng mảng
Để lưu trữ cây tổng quát bằng mảng, trước hết, ta đánh số các nút trên cây bắt đầu từ 1 theo một thứ tự tuỳ ý. Giả sử cây có n nút thì ta sử dụng:
Một mảng Info[1..n], trong đó Info[i] là giá trị lưu trong nút thứ i.
Một mảng Children được chia làm n đoạn, đoạn thứ i gồm một dãy liên tiếp các phần tử là chỉ số các nút con của nút i. Như vậy mảng Children sẽ chứa tất cả chỉ số của mọi nút con trên cây [ngoại trừ nút gốc] nên nó sẽ gồm n - 1 phần tử, lưu ý rằng khi chia mảng Children làm n đoạn thì sẽ có những đoạn rỗng [tương ứng với danh sách các nút con của một nút lá].
Một mảng Head[1..n + 1], để đánh dấu vị trí cắt đoạn trong mảng Children: Head[i] là vị trí đứng liền trước đoạn thứ i, hay nói cách khác: Đoạn con tính từ chỉ số Head[i] + 1 đến Head[i] của mảng Children chứa chỉ số các nút con của nút thứ i. Khi Head[i] = Head[i+1] có nghĩa là đoạn thứ i rỗng. Quy ước: Head[n+1] = n - 1.
Giữ lại chỉ số của nút gốc. Ví dụ:
Hình 11: Biểu diễn cây tổng quát bằng mảng
Lưu trữ cây tổng quát bằng cấu trúc liên kết
Khi lưu trữ cây tổng quát bằng cấu trúc liên kết, mỗi nút là một bản ghi [record] gồm ba trường:
Trường Info: Chứa giá trị lưu trong nút đó.
Trường FirstChild: Chứa liên kết [con trỏ] tới nút con đầu tiên của nút đó [con cả], trong trường hợp là nút lá [không có nút con], trường này được gán một giá trị đặc biệt.
Trường Sibling: Chứa liên kết [con trỏ] tới nút em kế cận bên phải [nút cùng cha với nút đang xét, khi sắp thứ tự các con thì nút đó đứng liền sau nút đang xét]. Trong trường hợp không có nút em kế cận bên phải, trường này được gán một giá trị đặc biệt.
Hình 12: Cấu trúc nút của cây tổng quát
Dễ thấy được tính đúng đắn của phương pháp biểu diễn, bởi từ một nút N bất kỳ, ta có thể đi theo liên kết FirstChild để đến nút con cả, nút này chính là chốt của một danh sách nối đơn các nút con của nút N: từ nút con cả, đi theo liên kết Sibling, ta có thể duyệt tất cả các nút con của nút N.
Bài tập
Bài 1
Viết chương trình mô tả cây nhị phân dùng cấu trúc liên kết, mỗi nút chứa một số nguyên, và viết các thủ tục duyệt trước, giữa, sau.
Bài 2
Chứng minh rằng nếu cây nhị phân có x nút lá và y nút cấp 2 thì x = y + 1.
Bài 3
Chứng minh rằng nếu ta biết dãy các nút được thăm của một cây nhị phân khi duyệt theo thứ tự trước và thứ tự giữa thì có thể dựng được cây nhị phân đó. Điều này con đúng nữa không đối với thứ tự trước và thứ tự sau? Với thứ tự giữa và thứ tự sau.
Bài 4
Viết các thủ tục duyệt trước, giữa, sau không đệ quy.