Các Phép Duyệt Cây Nhị Phân - Giáo Trình Cấu Trúc Dữ Liệu Và Giải Thuật

Phép xử lý mỗi nút của cây theo một thứ tự nào đó được gọi là phép duyệt cây. Thông thường có 3 phép duyệt cây:

- Duyệt cây theo thứ tự trước. - Duyệt cây theo thứ tự giữa. - Duyệt cây theo thứ tự sau.

Ở mỗi phép duyệt cây ta phải thăm lần lượt các nút sao cho mỗi nút chỉ được thăm một lần. Giả sử với có cây nhị phân sau ta sẽ có dãy các nút khác nhau tương ứng với từng phép duyệt cây.

3.1. Duyệt cây theo thứ tự trước (Preorder traversal). 3.1.1. Phép duyệt. 3.1.1. Phép duyệt.

Phép duyệt được thực hiện bằng việc thăm gốc trước tiên, cụ thể theo các thứ tự sau:

- Thăm gốc.

- Duyệt cây con trái theo thứ tự trước. - Duyệt cây con phải theo thứ tự trước. 3.1.2. Giải thuật:

Với cấu trúc cây nhị phân cài đặt bằng danh sách liên kết như sau:

117 typedef char ElementType; struct node

{ ElementType info; node *Lchild; node *Rchild; };

typedef struct node* TreeNode; TreeNode T;

Giải thuật PreOrder được cài đặt đệ qui như sau:

// Tham số hình thức T là một con trỏ chứa địa chỉ nút gốc của cây

void PreOrder (TreeNode T) { if (T != NULL)

{ printf(“% c”, T->info); //in ra màn hình giá trị trường info

PreOrder (T-> Lchild) PreOrder (T-> Rchild) }

}

Dãy các nút của cây nhị phân hình 6.12 tương ứng với phép duyệt cây theo thứ tự trước là: ABDEHICFGJ.

3.2. Duyệt cây theo thứ tự giữa (Inorder traversal). 3.2.1. Phép duyệt. 3.2.1. Phép duyệt.

Phép duyệt được thực hiện bằng việc thăm gốc sau khi đã thăm hết các nút của cây con trái, cụ thể như sau:

- Duyệt cây con trái theo thứ tự giữa. - Thăm gốc.

- Duyệt cây con phải theo thứ tự giữa. 3.2.2. Giải thuật:

Giải thuật đệ qui của InOrder được cài tương tự như sau:

// Tham số hình thức T là một con trỏ chứa địa chỉ nút gốc của cây

void InOrder (TreeNode T) { if (T != NULL)

{ InOrder (T-> Lchild)

printf(“% c”, T->info); //in ra màn hình giá trị trường info

InOrder (T-> Rchild) }

118

Dãy các nút của cây nhị phân hình 6.12 tương ứng với phép duyệt cây theo thứ tự giữa là: DBHEIAFCGJ.

3.3. Duyệt cây theo thứ tự sau (Postorder traversal). 3.3.1. Phép duyệt. 3.3.1. Phép duyệt.

Phép duyệt được thực hiện bằng việc thăm gốc sau cùng, khi đã thăm hết các nút của cây con trái và các nút của cây con phải theo thứ tự sau:

- Duyệt cây con trái theo thứ tự sau. - Duyệt cây con phải theo thứ tự sau. - Thăm gốc.

3.3.2. Giải thuật:

Giải thuật đệ qui của PostOrder được cài tương tự như sau:

// Tham số hình thức T là một con trỏ chứa địa chỉ nút gốc của cây

void PostOrder (TreeNode T) { if (T != NULL)

{ PostOrder (T-> Lchild) PostOrder (T-> Rchild)

printf(“% c”, T->info); //in ra màn hình giá trị trường info

} }

Dãy các nút của cây nhị phân hình 6.12 tương ứng với phép duyệt cây theo thứ tự sau là: DHIEBFJGCA

Các phép duyệt cây được cài đặt khá dễ dàng bằng giải thuật đệ qui vì nó phản ánh đúng dạng các định nghĩa của phép duyệt cây. Phép thăm mỗi nút ở đây là hiển thị giá trị trường info của nút đó.

3.4. Ví dụ áp dụng.

Sử dụng cấu trúc cây nhị phân để lưu trữ một biểu thức số học, với qui định là các nút cha chứa toán tử còn các nút lá chứa toán hạng.

Giả sử ta có biểu thức:

119 Cây nhị phân tương ứng:

Tương ứng với các phép duyệt cây ta có các biếu thức số học theo các dạng ký pháp Ba Lan:

- Duyệt cây theo thứ tự trước (dạng tiền tố): / * + 5 7- 6 4 - 3 8 - Duyệt cây theo thứ tự giữa (dạng trung tố): 5 + 7 * 6 – 4 / 3 - 8 - Duyệt cây theo thứ tự sau (dạng hậu tố): 5 7 + 6 4 - * 3 8 - /

Các biểu thức dạng ký pháp Ba Lan do nhà logic toán Jan Łukasiewicz người Ba Lan đề xuất khoảng năm 1920. Ký pháp Ba Lan là một cách viết một biểu thức đại số rất thuận lợi cho việc thực hiện các phép toán. Về lý thuyết, ký pháp dạng tiền tố và ký pháp dạng hậu tố có thể thực hiện các phép toán theo thứ tự từ trái sang phải mà không phải dùng tới dấu ngoặc để thể hiện độ ưu tiên các phép toán, còn ký pháp dạng trung tố thì không thể.

Thứ tự các phép toán trong các biểu thức dạng ký pháp Ba Lan tương ứng với các phép duyệt cây hình 6.13 như sau:

- Biểu thức dạng tiền tố thì dấu toán tử trước hai toán hạng. Thứ tự các phép toán được thực hiện là:

Bắt đầu từ trái sang phải ta gặp phép toán: + 5 7 (lấy 5+7=12) Tiếp đến phép toán: - 6 4 (lấy 6 – 4=2)

Rồi đến phép toán: * 12 2 (lấy 12 * 2 = 24) Tiếp theo đến phép toán: - 3 8 (lấy 3 – 8 = -5) Cuối cùng là phép toán: 24 -5 / (lấy 24/-5= -4.8)

- Biểu thức dạng hậu tố thì dấu toán tử ở sau hai toán hạng. Thứ tự các phép toán được thực hiện từ trái sang phải như sau:

Đầu tiên là phép toán: 5 7 + (lấy 5+7 =12). Tiếp đến phép toán: 6 4 – (lấy 6-4 = 2).

/ - * - + 7 3 6 4 5 8

120

Rồi đến phép toán 12 2 * (lấy 12 * 2=24). Tiếp theo là phép toán 3 8 – (lấy 3 – 8 = -5). Cuối cùng là phép toán 24 -5 / (lấy 24/-5= -4.8).

- Biểu thức dạng trung tố thì dấu toán tử ở giữa hai toán hạng. Thứ tự các phép toán được thực hiện là:

5 + 7 * 6 – 4 / 3 - 8

Đầu tiên là phép toán: 5+7 =12. Tiếp theo là phép toán: 12*6 =72. Rồi đến phép toán: 72-4= 68. Tiếp đến phép toán: 68/3 = 22.7. Cuối cùng là phép toán: 22.7 -8 =14.7.

Nhận xét:

- Biểu thức dạng trung tố cho kết quả sai vì theo nguyên tắc là toán tử ở giữa hai toán hạng, do đó mỗi khi thấy một toán tử ở giữa hai toán hạng là một phép toán được thực hiện (cần phải có các dấu ngoặc tròn để thay đổi thứ tự các phép toán như chúng ta vẫn quen dùng).

- Biểu thức dạng tiền tố và hậu tố không cần phải có cặp ngoặc tròn vẫn thực hiện đúng biểu thức.

121

CÂU HỎI VÀ BÀI TẬP CUỐI CHƯƠNG 6

1) Hãy trình bày định nghĩa đệ qui của cấu trúc dữ liệu cây.

2) Hãy nêu những tính chất của cấu trúc dữ liệu cây tổng quát và cây nhị phân 3) Hãy trình bày hai cách biểu diễn cây nhị phân là lưu trữ kế tiếp và lưu trữ

bằng danh sách liên kết? So sánh ưu, nhược điểm của hai cách biểu diễn này và cho ví dụ minh họa.

4) Cho cây hình 6.14 sau:

a. Hãy liệt kê các nút lá b. Hãy liệt kê các nút nhánh c. Cha của nút J là nút nào ? d. Con của nút E là nút nào?

e. Mức của K, của M là bao nhiêu? f. Cấp của cây là bao nhiêu?

g. Chiều cao của cây là bao nhiêu?

h. Độ dài đường đi từ A tới F, Q, S là bao nhiêu? i. Có bao nhiêu đường đi có độ dài 3 trên cây này?

5) Vẽ cây nhị phân biểu diễn các biểu thức sau và viết chúng dưới dạng tiền tố, hậu tố: Hình 6.14 : Cây tổng quát A D B C E M J G I L K F H P Q O N S a.

122

6) Cho cây nhị phân hình 6.15 sau:

a. Hãy viết ra các nút khi duyệt cây theo thứ tự trước. b. Hãy viết ra các nút khi duyệt cây theo thứ tự giữa. c. Hãy viết ra các nút khi duyệt cây theo thứ tự sau.

d. Hãy minh họa bộ nhớ khi thực hiện lưu trữ kế tiếp với cây này.

e. Hãy minh họa bộ nhớ khi thực hiện lưu trữ bằng danh sách liên kết với cây này. 7) Viết chương trình để tính giá trị của biểu thức khi cho biểu thức tiền tố

8) 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ố. A C B E D I F J K H G L O N M P Hình 6.15 : Cây nhị phân b. c. d. e.

123

124

CHƯƠNG 7 ĐỒ THỊ

Mục tiêu:

- Hiểu được khái niệm về đồ thị;

- Cài đặt được đồ thị trên máy tính bằng các cấu trúc mảng và cấu trúc danh sách liên kết;

- Thực hiện được các phép duyệt đồ thị.

1. Khái niệm về đồ thị

1.1. Định nghĩa

Một đồ thi G(V,E) bao gồm một tập hữu hạn V các nút, hay đỉnh (Vertices) và một tập hữu hạn E các cặp đỉnh mà ta gọi là cung (Edges)

Nếu (v1,v2) là một cặp đỉnh thuộc E thì ta nói: Có một cung nối v1 và v2 Nếu cung (v1,v2) khác với cung (v2,v1) thì ta có một đồ thị định hướng (Directed graph hay digraph). Lúc đó (v1,v2) được gọi là cung định hướng từ v1 tới v2. nếu thứ tự các nút trên cung không được coi trọng thì ta có đồ thị không định hướng (Undirected graph) hay đồ thị vô hướng.

Bằng hình vẽ ta có thể biểu diễn đồ thị như sau:

Mạch điện, mạng lưới đường giao thông, mạng máy tính ,v ..v là các ví dụ thực tế của đồ thị. Cây là một trường hợp đặc biệt của đồ thị.

1.2. Các khái niệm.

- Lân cận: Nếu (v1,v2) là một cung trong tập E(G) thì v1 và v2 gọi là lân cận của nhau (adjacent).

- Đường đi (path): Một đường đi từ đỉnh vp đến đỉnh vq trong đồ thị G là

1 2 4 3 Hình 7.1: Đồ thị định hướng 1 2 4 5 3 Hình 7.2: Đồ thị không định hướng (đồ thị vô hướng)

125

một dãy các đỉnh vp, vi0, vi1, ..., vin-1, vq mà (vp,vi0), (vi0,vi1),... ( vin-1,vq) là các cung trong E(G). Số lượng các cung trên đường đi ấy gọi là độ dài của đường đi

(path length).

Ví dụ: Hình 7.1: 1,3,4 là một đường đi từ đỉnh 1 đến đỉnh 4, nó có độ dài 2. Hình 7.2: Đường đi từ đỉnh 1 đến đỉnh 4 là 1, 3, 5, 2, 4 nó có độ dài bằng

4; hoặc 1, 2, 4 có độ dài là 2.

- Đường đi đơn (simple path): Là đường đi mà mọi đỉnh trên đó, trừ đỉnh

đầu tiên và đỉnh cuối cùng, đều khác nhau.

- Một chu trình (Cycle): Là một đường đi mà đỉnh đầu và đỉnh cuối trùng

với nhau (ví dụ : Hình 7.1 đường đi 1, 3, 4, 1 là một chu trình).

- Đối với đồ thị định hướng, để cho rõ, thường người ta thêm vào các từ “định hướng” sau các thuật ngữ trên (ví dụ: Đường đi định hướng từ vi tới vj).

- Liên thông: Trong đồ thị G hai đỉnh vi và vj gọi là liên thông nếu có một đường đi từ vi tới vj (dĩ nhiên với đồ thị không định hướng thì đồng thời cũng có đường đi từ vj tới vi).

1 2 4 5 3 Hình 7.3b: Đồ thị không định hướng, liên thông

1

2

4 5

3

Hình 7.3a: Đồ thị không định hướng, không liên thông

Hình 7.3d: Đồ thị định hướng, liên thông

Hình 7.3c: Đồ thị định hướng, Không liên thông

1 2 4 5 3 1 2 4 5 3

126

- Đồ thị có trọng số: Trong thực tế có rất nhiều ứng dụng của đồ thị đòi

hỏi phải có thông tin trên các cạnh (cung) của đồ thị để biểu thị khoảng cách, giá thành,... Thông tin đó là những con số và được gọi là trọng số, đồ thị này được gọi là đồ thị có trọng số. Ví dụ: Bản vẽ dự toán về chi phí cho tuyến đường cần xây dựng từ tỉnh A đến tỉnh D có đi qua các tỉnh B hoặc C được thể hiện như sau:

2. Biểu diễn đồ thị

2.1. Biểu diễn bằng ma trận kề

Dùng một ma trận có kiểu logic để biểu diễn các đỉnh và các cung của đồ thị

Giả sử ta có một đồ thị có hướng G=<V, E> gồm n đỉnh {v0, v1,…, vn-1}. Giá trị của ma trận Ai,j được xác định theo nguyên tắc sau:

ai,j= 1 nếu (vi, vj)  E: Nghĩa là có một cung nối từ vi đến vj

ai,j= 0 nếu (vi, vj)  E: Nghĩa là giữa hai đỉnh vi và vj không có cung nối.

A

C D

B

Hình 7.5: Ma trận kề của đồ thị vô hướng

v0=A v1=B v2=C v3=D A C D B Hình 7.6: Ma trận kề của đồ thị định hướng v0=A v1=B v2=C v3=D 85 km 75 km 75 km 100 km C Hình 7.4: Đồ thị có trọng số A B D

127 - Nhận xét:

• Ở đồ thị vô hướng thì ma trận kề biểu diễn nó có các phần tử đối xứng qua đường chéo chính, tức là Ai,j = Ạj,i

• Nhìn vào ma trận kề biểu diễn đồ thị định hướng ta có thể biết được các cung đi tới hoặc xuất phát từ một đỉnh cho trước. Ví dụ tại đỉnh v1=B ta biết chỉ có một cung đi từ đỉnh v1 đến đỉnh v3=D.

- Ưu điểm:

• Đơn giản, trực quan.

• Dễ dàng xác định được có hay không một cung đi từ đỉnh i đến đỉnh j.

• Dễ cài đặt trên máy tính. - Nhược điểm:

• Tốn bộ nhớ: Bất kể đồ thị có bao nhiêu cạnh, mỗi đồ thị cũng cần một ma trận vuông với kích thước n x n phần tử (ô nhớ). Tuy nhiên có thể khắc phục điều này bằng cách chỉ lưu trữ một nửa trên hoặc nửa dưới của ma trận nhưng chỉ với đồ thị vô hướng.

• Tốn thời gian: Với một đỉnh vi nhiều khi ta phải xét tất cả các đỉnh vj khác để tìm các đỉnh kề với nó.

- Ví dụ: Viết chương trình đưa ra màn hình tất cả các đỉnh kề với từng đỉnh trong một đồ thị bất kỳ. #include <conio.h> #include <stdio.h> const n=5; void main() { int i,j,k; clrscr(); int a[n][n];

printf("nhap ma tran ke tuong ung\n"); for ( i=0; i<n ;i++)

for (j=0; j<n; j++)

{printf("nhap a%d:",i);scanf("%d",&a[i][j]); } clrscr();

printf("cac dinh ke:\n "); for ( i=0; i<5 ;i++)

{

printf("\n dinh ke voi %d la: ",i); for ( j=0; j<5 ;j++)

128 if (a[i][j] == 1) printf("%3d;",j); } getch(); }

2.2. Biểu diễn đồ thị bằng danh sách kề.

Phương pháp này dùng n danh sách liên kết cho n đỉnh của đồ thị, mỗi danh sách liên kết của một đỉnh sẽ chứa tất cả các đỉnh khác kề với nó. Do đó các danh sách này còn được gọi là danh sách kề.

Như vậy để lưu trữ thông tin về một đồ thị có n đỉnh ta cần một mảng G gồm n phần tử, mỗi phần tử Gi là một con trỏ trỏ tới danh sách các đỉnh kề với đỉnh i, mỗi nút gồm 2 trường là Vertex chứa chỉ số của đỉnh kề với nó và trường Link chứa địa chỉ của nút tiếp theo trong danh sách.

V0 A B C V1 B A D V2 C A D V3 D B C V0 A B C V1 B D V2 C D V3 D 3. Các phép duyệt đồ thị

Tương tự như cấu trúc dữ liệu cây, khi xử lý bài toán đồ thị, ta cần thăm các đỉnh của đồ thị một cách có hệ thống để đảm bảo rằng mỗi đỉnh chỉ được thăm đúng một lần, việc này được gọi là duyệt đồ thị. Có hai phép duyệt đồ thị phổ biến đó là duyệt theo chiều sâu và duyệt theo chiều rộng.

Giả sử ta có đồ thị G=(V,E) và một đỉnh v trong V(G), ta cần thăm tất cả các đỉnh thuộc G mà có liên thông với G.

3.1. Duyệt theo chiều sâu (Depth First Search). 3.1.1. Phép duyệt. 3.1.1. Phép duyệt.

Hình 7.7: Ma trận danh sách kề của đồ thị vô hướng

A

C D

B

Hình 7.8: Ma trận danh sách kề của đồ thị định hướng

A

C D

129

Xuất phát từ một đỉnh v được thăm, tiếp theo đỉnh w chưa được thăm kề với v được chọn và một phép duyệt theo chiều sâu xuất phát từ w lại được thực hiện với các đỉnh w1 kề với w,… khi hết một nhánh thì được chuyển sang nhánh khác. Phép duyệt theo nguyên tắc này được gọi là duyệt theo chiều sâu.

Phép duyệt sẽ kết thúc khi không có một đỉnh nào kề với đỉnh đã được thăm mà chưa được thăm

Giả thiết, với đồ thị hình 7.9 và đỉnh xuất phát là v1, thì phép duyệt theo chiều sâu sẽ được một dãy các đỉnh sau:

v1, v2 (cũng có thể v3), v4 (cũng có thể v5), v5, v3, v7 do v7 không có đỉnh kề nào chưa được thăm nên phải quay lại v3 và cuối cùng là v6.

3.1.2. Giải thuật.

Để kiểm tra việc duyệt mỗi đỉnh đúng một lần ta dùng một mảng mart gồm n phần tử tương ứng với n đỉnh của đồ thị. Khởi đầu gán giá trị 0 cho tất cả các