Kiểu dữ liệu cây

Định nghĩa 1:

Một cây là tập hợp hữu hạn các nút trong đó có một nút đặc biệt gọi là gốc (root). Giữa các nút có một quan hệ phân cấp gọi là "quan hệ cha con".

Định nghĩa 2:

Cây được định nghĩa đệ qui như sau

1. Một nút là một cây và nút này cũng là gỗc của cây.

2. Giả sử T 1 , T 2 , …,T n (n ≥ 1) là các cây có gốc tương ứng r 1 , r 2 ,…, r n . Khi đó cây T với gốc r được hình thành bằng cách cho r trở thành nút cha của các nút r 1 , r 2 ,…, r n

Một số khái niệm cơ bản

Bậc của một nút: là số con của nút đó

Bậc của một cây: là bậc lớn nhất của các nút có trên cây đó (số cây con tối đa của một nút thuộc cây). Cây có bậc n thì gọi là cây n - phân

Nút gốc: là nút có không có nút cha

Nút lá: là nút có bậc bằng 0

Nút nhánh: là nút có bậc khác 0 và không phải là nút gốc

Mức của một nút

Mức (gốc (T₀)) =1

Gọi T₁, T₂,..., T_n là các cây con của T₀.

Khi đó Mức (T₁) = Mức (T₂) = ... = Mức (T_n) = Mức (T₀) +1 Chiều cao của cây: là số mức lớn nhất có trên cây đó

Đường đi: Dãy các đỉnh n₁, n₂, ...,n_k được gọi là đường đi nếu n_i là cha của n_i+1 (1 ≤ i ≤ k-1

Độ dài của đường đi: là số nút trên đường đi -1

Cây được sắp : Trong một cây, nếu các cây con của mỗi đỉnh được sắp theo một thứ nhất định, thì cây được gọi là cây được sắp (cây có thứ tự). Chẳng hạn, hình minh hoạ hai cây được sắp khác nhau

Rừng: là tập hợp hữu hạn các cây phân biệt

Biểu diễn cây tổng quát

- Đối với cây tổng quát cấp m nào đó có thể sử dụng cách biểu diễn móc nối tương tự như đối với cây nhị phân. Như vậy ứng với mỗi nút ta phải dành ra m trường mối nối để trỏ tới các con của nút đó và như vậy số mối nối không sẽ rất nhiều: nếu cây có n nút sẽ có tới n(m-1) + 1"mối nối không" trong số m.n mối nối.

- Nếu tuỳ theo số con của từng nút mà định ra mối nối nghĩa là dùng nút có kích thước biến đổi thì sự tiết kiện không gian nhớ này sẽ phải trả giá bằng những phức tạp của quá trình xử lý trên cây.

- Để khắc phục các nhược điêm trên là dùng cách biểu diễn cây nhị phân để biểu diễn cây tổngquát.

Ta có thể biến đổi một cây bất kỳ thành một cây nhị phân theo qui tắc sau

• Giữ lại nút con trái nhất làm nút con trái
• Các nút con còn lại chuyển thành các nút con phải
• Như vậy, trong cây nhị phân mới, con trái thể hiện quan hệ cha con và con phải thể hiện quan hệ anh em trong cây tổng quát ban đầu. Khi đó cây nhị phân này được gọi là cây nhị phân tương đương.

Ta có thể xem ví dụ dưới đây để thấy rõ qui trình. Giả sử có cây tổng quát như hình vẽ dưới đây

Cây nhị phân tương đương sẽ như sau

Phép duyệt cây tổng quát

Phép duyệt cây tổng quát cũng được đặt ra tương tự như đối với cây nhị phân. Tuy nhiên có một điều cần phải xem xét thêm,khi định nghĩa phép duyệt, đó là:

1) Sự nhất quán về thứ tự các nút được thăm giữa phép duyệt cây tổng quát và phép duyệt cây nhị phân tương đương của nó

2) Sự nhất quán giữa định nghĩa phép định nghĩa phép duyệt cây tổng quát với định nghĩa phép duyệt cây nhị phân. Vì cây nhị phân cũng có thể coi là cây tổng quát và ta có thể áp dụng định nghĩa phép duyệt cây tổng quát cho cây nhị phân.

Ta có thể xây dựng được định nghĩa của phép duyệt cây tổng quát T như sau

Duyệt theo thứ tự trước

a) Nếu T rỗng thì không làm gì

b) Nếu T khác rỗng thì

Thăm gốc của T

Duyệtcác cây con thứ nhất T₁ của gốc của cây T theo thứ tự trước

Duyệt các cây con còn lại T₂, T₃,...,T_n của gốc T theo thứ tự trước

Duyệt theo thứ tự giữa

a) Nếu T rỗng thì không làm gì

b) Nếu T khác rỗng thì

Duyệtcác cây con thứ nhất T₁ của gốc của cây T theo thứ tự giữa

Thăm gốc của T

Duyệt các cây con còn lại T₂, T₃,...,T_n của gốc T theo thứ tự giữa

Duyệt theo thứ tự sau

a) Nếu T rỗng thì không làm gì

b) Nếu T khác rỗng thì

Duyệtcác cây con thứ nhất T₁ của gốc của cây T theo thứ tự sau

Duyệt các cây con còn lại T₂, T₃,...,T_n của gốc T theo thứ tự sau

Thăm gốc của T

ví dụ với cây ở hình vẽ 5.17

Thì dãy tên các nút được thăm sẽ là

Thứ tự trước: A B C E H I F J D G

Thứ tự giữa : B A H E I C J F G D

Thứ tự sau : B H I E J F C G D A

Bây giờ ta dựng cây nhị phân tương đương với cây tổng quát ở hình 5.17

Dãy các nút được thăm khi duyệt nó theo phép duyệt của cây nhị phân:

Thứ tự trước: A B C E H I F J D G

Thứ tự giữa: B H I E J F C G D A

Thứ tự sau: I H JF E G D C B A

Nhận xét

Với thứ tự trước phép duyệt cây tổng quát và phép duyệt cây nhị phân tương đương của nó đều cho một dãy tên như nhau. Phép duyệt cây tổng quát theo thứ tự sau cho dãy tên giống như dãy tên các nút được duyệt theo thứ tự giữa trong phép duyệt cây nhị phân. Còn phép duyệt cây tổng quát theo thứ tự giữa thì cho dãy tên không giống bất kỳ dãy nào đối với cây nhị phân tương đương. Do đó đối với cây tổng quát, nếu định nghĩa phép duyệt như trên người ta thường chỉ nêu hai phép duyệt theo thứ tự trước và phép duyệt theo thứ tự sau

Biểu diễn cây nhị phân

Định nghĩa: Cây nhị phân là cây mà mỗi nút có tối đa hai cây con. Đối với cây con của một nút người ta cũng phân biệt cây con trái và cây con phải.

Như vậy cây nhị phân là cây có thứ tự.

Tính chất: Đối với cây nhị phân cần chú ý tới một số tính chất sau

i) Số lượng tối đa các nút có ở mức i trên cây nhị phân là 2 i -1 (i ≥ 1)

ii) Số lượng nút tối đa trên một cây nhị phân có chiều cao h là 2 h -1(h ≥ 1 )

Chứng minh

i) Sẽ được chứng minh bằng qui nạp

Bước cơ sở: với i = 1, cây nhị phân có tối đa 1 = 2⁰ nút.Vậy mệnh đề đúng với i = 1

Bước qui nạp: Giả sử kết quả đúng với mức i, nghĩa là ở mức này cây nhị phân có tối đa 2^{i - 1} nút, ta chứng minh mệnh đề đúng với mức i + 1.

Theo định nghĩa cây nhị phân thì tại mỗi nút có tối đa hai cây con nên mỗi nút ở mức i có tối đa hai con. Do đó theo giả thiết qui nạp ta suy ra tại mức i+ 1 ta có

2^{i - 1}x 2 = 2ⁱ nút.

ii) Ta đã biết rằng chiều cao của cây là số mức lớn nhất có trên cây đó. Theo i) ta suy ra số nút tối đa có trên cây nhị phân với chiều cao h là :

2⁰+ 2¹+ ...+ 2^h-1 = 2^h -1.

Từ kết quả này có thể suy ra:

Nếu cây nhị phân có n nút thì chiều cao của no là h = log₂(n + 1)

(Ta qui ước : x là số nguyên trên của x

[x] là số nguyên dưới của x )

1.lưu trữ kế tiếp

- Phương pháp tự nhiên nhất để biểu diễn cây nhị phân là chỉ ra đỉnh con trái và đỉnh con phải của mỗi đỉnh.

Ta có thể sử dụng một mảng để lưu trữ các đỉnh của cây nhị phân. Mỗi đỉnh của cây được biểu diễn bởi bản ghi gồm ba trường:

trường infor: mô tả thông tin gắn với mỗi đỉnh

letf : chỉ đỉnh con trái

right: chỉ đỉnh con phải.

Giả sử các đỉnh của cây được được đánh số từ 1 đến max. Khi đó cấu trúc dữ liệu biểu diễn cây nhị phân được khai báo như sau:

const max = ...; {số thứ tự lớn nhất của nút trên cây}

type

item = ...; {kiểu dữ liệu của các nút trên cây}

Node = record

infor : item;

letf :0..max;

right :0..max;

end;

Tree = array[1.. max] of Node;

Hình 5.4. Một cây nhị phân

Hình 5.5. minh hoạ cấu trúc dữ liệu biểu diễn cây nhị phân trong hình 5.4

	infor	left	right
1	A	2	3
2	B	4	5
3	C	6	7
4	D	0	8
5	E	9	10
6	F	0	0
7	G	11	9
8	H	0	0
9	I	0	0
10	J	0	0
11	K	0	0

Hình 5.5. Cấu trúc dữ liệu biểu diễn cây

- Nếu có một cây nhị phân hoàn chỉnh đầ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ở lên, hết mức này đến mức khác và từ trái qua phải đối với các nút ở mỗi mức.

ví dụ với hình 5.6 có thể đánh số như sau:

Ta có nhận xét sau: con của nút thứ i là các nút thứ 2i và 2i + 1 hoặc cha của nút thứ j là [j/2]

Nếu như vậy thì ta có thể lưu trữ cây này bằng một vectơ V, theo nguyên tắc: nút thứ i của cây được lưu trữ ở V[i]. Đó chính là cách lưu trữ kế tiếp đối với cây nhị phân. Với cách lưu trữ này nếu biết được địa chỉ của nút con sẽ tính được địa chỉ nút cha và ngược lại.

Như vậy với cây đầy đủ nêu trên thì hình ảnh lưu trữ sẽ như sau

Nhận xét

Nếu cây nhị phân không đầy đủ thì cách lưu trữ này không thích hợp vì sẽ gây ra lãng phí bộ nhớ do có nhiều phần tử bỏ trống (ứng với cây con rỗng). Ta hãy xét cây như hình 5.7. Để lưu trữ cây này ta phải dùng mảng gồm 31 phần tử mà chỉ có 5 phần tử khác rỗng; hình ảnh lưu trữ miền nhớ của cây này như sau

Nếu cây nhị phân luôn biến động nghĩa là có phép bổ sung, loại bỏ các nút thường xuyên tác động thì cách lưu trữ này gặp phải một số nhược điểm như tốn thời gian khi phải thực hiện các thao tác này, độ cao của cây phụ thuộc vào kích thước của mảng...

2. Lưu trữ móc nối

Cách lưu trữ này khắc phục được các nhược điểm của cách lưu trữ trên đồng thời phản ánh được dạng tự nhiên của cây.

Trong cách lưu trữ này mỗi nút tương ứng với một phần tử nhớ có qui cách như sau:

letf

info

right

Trường info ứng với thông tin (dữ liệu) của nútTrường left ứng với con trỏ, trỏ tới cây con trái của nút đó Trường right ứng với con trỏ, trỏ tới cây con phải của nút đó

Ta có thể khai báo như sau

type

item = ...;{kiểu dữ liệu của các nút trên cây

Tree = ^Node;

Node = record

info : item;

left, right: Tree;

end;

var Root :Tree;

ví dụ: cây nhị phân hình 5.8 có dạng lưu trữ móc nối như ở hình 5.9

Để truy nhập vào các nút trên cây cần có một con trỏ Root, trỏ tới nút gốc của cây

Duyệt cây nhị phân

Phép xử lý các nút trên cây - mà ta gọi chung là phép thăm các nút một cách hệ thống, sao cho mỗi nút được thăm đúng một lần, gọi là phép duyệt cây. Chúng ta thường duyệt cây nhị phân theo một trong ba thứ tự: duyệt trước, duyệt giữa và duyệt sau, các phép này được định nghĩa đệ qui như sau:

Duyệt theo thứ tự trước (preorder traversal)

- Thăm gốc

- Duyệt câycon trái theo thứ trước

- Duyệt cây con phải theo thư tự trước

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

- Duyệt câycon trái theo thứ giữa

- Thăm gốc

- Duyệt cây con phải theo thư tự giữa

Duyệt theo thứ tự sau (postorder traversal)

- Duyệt câycon trái theo thứ sau

- Duyệt cây con phải theo thư tự sau

- Thăm gốc

Tương ứng với ba phép duyệt ta có ba thủ tục duyệt cây nhị phân. Sau đây là thủ tục đệ qui duyệt cây theo thứ tự trước

procedure Preorder (Root : Tree);

Begin

if Root <> nil then

Begin

write(Root^.info);

Preorder(Root^.left);

Preorder(Root^.right);

end;

end;

Một cách tương tự, ta có thể viết được các thủ tục đệ qui đi qua cây theo thứ tự giữa và theo thứ tự sau.

Với cây nhị phân ở hình vẽ này, dãy các nút được thăm trong các phép duyệt là

a) Duyệt theo thứ tự trước

A B D G H E C F I G

b) Duyệt theo thứ giữa

G D H B E A F I C G

c) Duyệt theo thứ tự sau

G H D E B I F G C A