Giải thuật và lập trình: §6. CÂY (TREE)

Author:

Category:

Đăng ký nhận thông tin về những video mới nhất

ĐỊNH NGHĨA

Cấu trúc tài liệu trừu tượng ta chăm sóc tới trong mục này là cấu trúc cây. Cây là một cấu trúc tài liệu gồm một tập hữu hạn những nút, giữa những 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 quan trọng 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 những cây T1, T2, …, Tk ; những 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 những 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 những cây T1, T2, …, Tk trở thành những cây con ( subtree ) của gốc .

Để tiện, người ta còn được cho phép sống sót 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 :

giai-thuat-va-lap-trinh-cay-tree
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 :

giai-thuat-va-lap-trinh-muc-cua-nut-tren-cay
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 hoàn toàn có thể coi là gốc của cây

đó với những cây con là những 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 những phép toán cộng, trừ, nhân, chia cũng hoàn toàn có thể tàng trữ trong một cây mà những toán hạng được tàng trữ ở những nút lá, những toán tử được tàng trữ ở những nút nhánh, mỗi nhánh là một biểu thức con .

giai-thuat-va-lap-trinh-cay-bieu-dien-bieu-thuc

Hình 3 : Cây màn 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 thù 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 những nhánh con .
Cần chú ý quan tâm tới 1 số ít dạng đặc biệt quan trọng 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.

giai-thuat-va-lap-trinh-cac-dang-cay-nhi-phan-suy-bien

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.

giai-thuat-va-lap-trinh-cay-nhi-phan-hoan-chinh-va-day-du

Hình 5 : Cây nhị phân hoàn hảo và cây nhị phân khá đầy đủ
Ta hoàn toàn có thể thấy ngay những đặc thù sau bằng phép chứng tỏ quy nạp :
Trong những 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 to lớn nhất, còn cây nhị phân hoàn hảo thì có chiều cao nhỏ nhất .
Số lượng tối đa những nút trên mức i của cây nhị phân là 2 i – 1, tối thiểu là 1 ( i ≥ 1 ) .
Số lượng tối đa những nút trên một cây nhị phân có chiều cao h là 2 h – 1, tối thiểu là h ( h ≥ 1 ). Cây nhị phân hoàn hảo, không vừa đủ, có n nút thì độ cao của nó là h = [ log2 ( n + 1 ) ] + 1 .
Cây nhị phân vừa đủ có n nút thì độ cao của nó là h = log2 ( n + 1 ) .

BIỂU DIỄN CÂY NHỊ PHÂN

Biểu diễn bằng mảng

Nếu có một cây nhị phân vừa đủ, ta hoàn toàn có thể thuận tiện đánh số cho những 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 so với những nút ở mỗi mức .

giai-thuat-va-lap-trinh-danh-dau-cac-vi-tri-cay-nhi-phan-day-du

Hình 6 : Đánh số những nút của cây nhị phân rất đầy đủ để màn 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 không thiếu ở Hình 6 thì khi tàng trữ bằng mảng, ta sẽ được mảng như sau :

giai-thuat-va-lap-trinh-bieu-dien-dang-mang-cay-nhi-phan

Trong trường hợp cây nhị phân không vừa đủ, ta hoàn toàn có thể thêm vào 1 số ít nút giả để được cây nhị phân vừa đủ, và gán những giá trị đặc biệt quan trọng cho những thành phần 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ụ để ghi lại những nút nào là nút giả tự ta thêm vào. Chính vì nguyên do này nên với cây nhị phân không vừa đủ, ta sẽ gặp phải sự tiêu tốn lãng phí bộ nhớ vì hoàn toàn 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 không thiếu .
Ví dụ với cây lệch trái, ta phải dùng một mảng 31 thành phần để lưu cây nhị phân chỉ gồm 5 nút .

giai-thuat-va-lap-trinh-nhuoc-diem-bieu-dien-cay-nhi-phan-dang-mang

Hình 7 : Nhược điểm của chiêu thức trình diễn cây bằng mảng

Biểu diễn bằng cấu trúc liên kết

Khi trình diễn cây nhị phân bằng cấu trúc link, 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 link ( 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 quan trọng .
  • Trường Right : Chứa link ( 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 quan trọng .

giai-thuat-va-lap-trinh-lien-ket-trai-phai

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 chăm sóc giữ lại nút gốc, bởi từ nút gốc, đi theo những hướng link Left, Right ta hoàn toàn có thể duyệt mọi nút khác .

giai-thuat-va-lap-trinh-cay-bang-cau-truc-lien-ket

Hình 9 : Biểu diễn cây bằng cấu trúc link

PHÉP DUYỆT CÂY NHỊ PHÂN

Phép giải quyết và xử lý những nút trên cây mà ta gọi chung là phép thăm ( Visit ) những nút một cách mạng lưới 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ì link Left ( Right ) của nút đó được link thẳng tới một nút đặc biệt quan trọng 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ó, hoàn toàn có thể miêu 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 mở màn 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ì những 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

Duyệt theo thứ tự giữa (inorder traversal)

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 đó, hoàn toàn có thể miêu 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 mở màn 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ì những 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 đó, hoàn toàn có thể diễn đạ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 mở màn 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ì những giá trị sẽ lần lượt được liệt kê theo thứ tự :

CÂY K_PHÂN

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 những nút con ) .

Biểu diễn cây K_phân bằng mảng

Cũng tương tự như như việc trình diễn cây nhị phân, người ta hoàn toàn có thể thêm vào cây K_phân 1 số ít nút giả để cho mỗi nút nhánh của cây K_phân đều có đúng K nút con, những 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ố những nút trên cây K_phân mở màn từ 0 trở đi, mở màn 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 hoàn toàn có thể dùng một mảng T đánh số từ 0 để lưu những giá trị trên những nút : Giá trị tại nút thứ i được tàng trữ ở thành phần T [ i ] .

giai-thuat-va-lap-trinh-danh-dau-cac-nut-cay-3-phan

Hình 10 : Đánh số những nút của cây 3 _phân để mà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 trình diễn cây K_phân bằng cấu trúc link, 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 thành phần, thành phần thứ i chứa link ( 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 quan trọng .
Đố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 những hướng link hoàn toàn có thể đi tới mọi nút khác .

CÂY TỔNG QUÁT

Trong trong thực tiễn, có một số ít ứng dụng yên cầu một cấu trúc tài 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 mạng lưới hệ thống đề mục của một cuốn sách. Khi đó, ta phải tìm cách miêu tả một cách khoa học cấu trúc tài 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 trình diễn cây tổng quát bằng hai cách : Lưu trữ tiếp nối bằng mảng và tàng trữ bằng cấu trúc link .

Biểu diễn  cây tổng quát bằng mảng

Để tàng trữ cây tổng quát bằng mảng, trước hết, ta đánh số những nút trên cây khởi đầ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 tục những thành phần là chỉ số những nút con của nút i. Như vậy mảng Children sẽ chứa tổng thể 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 thành phần, quan tâm 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 list những nút con của một nút lá ) .
Một mảng Head [ 1 .. n + 1 ], để lưu lại 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ố những 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ụ :

giai-thuat-va-lap-trinh-cay-tong-quat-bang-mang

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 tàng trữ cây tổng quát bằng cấu trúc link, 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 link ( con trỏ ) tới nút con tiên phong 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 quan trọng .
Trường Sibling : Chứa link ( 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ự những 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 quan trọng .

giai-thuat-va-lap-trinh-cau-truc-nut-cua-cay-tong-quat

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 giải pháp trình diễn, bởi từ một nút N bất kể, ta hoàn toàn có thể đi theo link FirstChild để đến nút con cả, nút này chính là chốt của một list nối đơn những nút con của nút N : từ nút con cả, đi theo link Sibling, ta hoàn toàn có thể duyệt toàn bộ những nút con của nút N .

Bài tập

Bài 1

Viết chương trình diễn đạt cây nhị phân dùng cấu trúc link, mỗi nút chứa 1 số ít nguyên, và viết những 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 những 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ì hoàn toàn có thể dựng được cây nhị phân đó. Điều này con đúng nữa không so 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 những thủ tục duyệt trước, giữa, sau không đệ quy. Nguồn : Giáo trình Giải thuật và Lập trình – Lê Minh Hoàng – Đại học sư phạm TP.HN

Source: dolatrees.com
Category: Cây

Đàm Minh Đứchttps://dolatrees.com
Tôi là Đàm Minh Đức người đã từng gắn bó và nghiên cứu rất nhiều năm trong ngành nông nghiệp. Trong đầu tôi luôn suy nghĩ về việc trồng cây gì và ăn quả gì để dân tộc Việt Nam bớt nghèo. Dolatrees là một Websites được viết từ những trải nghiệm thực tế và từ cái tâm của mình. Đây là một kênh bạn có thể tham khảo để nâng cao sức khỏe và cuộc sốc của bạn

Read More

Related Articles

BÌNH LUẬN

Vui lòng nhập bình luận của bạn
Vui lòng nhập tên của bạn ở đây