Cấu trúc dữ liệu và giải thuật - Chương IV: Cấu trúc Cây

Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 1 Cấu trúc dữ liệu và Giải thuật Chương IV: Cấu trúc Cây Đỗ Bích Diệp - Khoa CNTT Cấu trúc Cây z Nội dung 1. Các khái niệm 2. Cây tổng quát 1. ADT Cây 2. Biểu diễn cây tổng quát 3. Duyệt cây tổng quát 3. Cây nhị phân 1. Định nghĩa và tính chất 2. Duyệt cây nhị phân 3. Biểu diễn cây nhị phân 4. Ứng dụng của cấu trúc cây cho cây biểu thức Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 2 Đỗ Bích Diệp - Khoa CNTT Định nghĩa Cây − Cây là một cấu trúc phi tuyến, thiết lập trên một tập hữu hạn các “nút” – Tồn tại một nút đặc biệt gọi là “gốc” (root) – Giữa các nút tồn tại một quan hệ phân cấp hay gọi là quan hệ cha con – Một nút trừ nút gốc chỉ có một cha – Một nút có thể có từ 0 đến n con Đỗ Bích Diệp - Khoa CNTT Định nghĩa Cây z Định nghĩa đệ quy về Cây – Một nút tạo thành một cây. – Nếu có n cây T1, T2, , Tn tách biệt có các nút gốc lần lượt là r1, r2, , rn; r là một nút có quan hệ cha-con với r1, r2, , rn thì tồn tại một cây mới T nhận r làm gốc. r rnr2r1 T1 T2 Tn Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 3 Đỗ Bích Diệp - Khoa CNTT Ví dụ Cây Desktop My Documents My Network PlacesMy Computer CD Driver (D:) WindowsXP (C:)Floppy(A:) My Received FilesMy Pictures My Music Cây thư mục trong máy tính Đỗ Bích Diệp - Khoa CNTT Ví dụ Cây Cây phân cấp chức năng hệ thống thông tin Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 4 Đỗ Bích Diệp - Khoa CNTT Ví dụ Cây Cây mục lục Sách Đỗ Bích Diệp - Khoa CNTT Các thuật ngữ liên quan đến cây – Cấp (Degree) của một nút và của cây z Cấp của một nút là số các con của nút đó z Cấp của một cây là cấp cao nhất của một nút trên cây A JH DCB E F G I K L M N Degree 2 Degree 3 Degree 4 Degree 3 P Degree 1 Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 5 Đỗ Bích Diệp - Khoa CNTT Các thuật ngữ liên quan đến cây – Đường đi trên cây: z Dãy các nút n1, n2, .., nk trong đó ni là nút cha của ni+1 ( i = 1..k-1) là đường đi từ n1 đến nk A JH DCB E F G I K L M N Path from A to M Length = 3 P Đỗ Bích Diệp - Khoa CNTT Các thuật ngữ liên quan đến cây z Độ sâu hay mức (Depth – Level ) của nút – Độ dài đường đi từ gốc đến nút đó + 1 A JH DCB E F G I K L M N Depth 1 Depth 2 Depth 3 Depth 4P Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 6 Đỗ Bích Diệp - Khoa CNTT Các thuật ngữ liên quan đến cây z Độ cao (Height) của nút – Độ dài đường đi dài nhất từ nút đó đến 1 nút lá trong cây + 1 – Chiều cao của cây là chiều cao của nút gốc của cây đó A JH DCB E F G I K L M NP Height = 1 Height = 2 Height =3 Height =4 Đỗ Bích Diệp - Khoa CNTT Các thuật ngữ liên quan đến cây z Tổ tiên (Ancestor): A,C, G là tổ tiên của M z Hậu duệ (descendants): E, F, G, H, L,M đều là hậu duệ của A z Anh em (siblings): E, F là một cặp anh em ; L, N là một cặp anh em A JH DCB E F G I K L M NP Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 7 Đỗ Bích Diệp - Khoa CNTT Các thuật ngữ liên quan đến cây z Rừng là một tập hợp hữu hạn các cây phân biệt , không giao nhau JH DCB E F G I K L M N Đỗ Bích Diệp - Khoa CNTT Các thao tác cơ bản trên Cây – Các thao tác truy nhập cây z root() : trả ra nút gốc của cây z parent( Tree T, Node p): trả ra nút cha của nút p trong cây T z children(Tree T, Node p): trả ra danh sách các nút con của nút p trong cây T z left_most_child(Tree T, Node p) : trả ra nút con cực trái của nút p z right_most_child(Tree T, Node p) : trả ra nút con cực phải của nút p z left_sibling (Tree T, Node p) : trả ra nút anh em kề cận bên trái của nút p z right_sibling(Tree T, Node p) : trả ra nút anh em kề cận bên phải của nút p – Các thao tác khác z height (Tree T) z size(Tree T) z isRoot (Tree T, Node p); isLeaf (Tree T, Node p); isInternal (Tree T, Node p); Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 8 Đỗ Bích Diệp - Khoa CNTT Biểu diễn cây tổng quát – Dựa trên tham chiếu đến nút cha z Cây T có các nút được đánh số từ 1 đến n z Cây T được biểu diễn bằng một danh sách tuyến tính trong đó nút thứ i sẽ chứa một thành phần tham chiếu đến cha của nó z Nếu dùng mảng, A[i] = j nếu j là cha của nút i ; nếu i là gốc thì A[i] = 0; A H DCB E G L N 1 2 3 4 5 6 7 8 9 A[9]A[8]A[7]A[6]A[5]A[4]A[3]A[2]A[1] 663321110 Đỗ Bích Diệp - Khoa CNTT Biểu diễn cây tổng quát – Dựa trên danh sách các nút con z 1 nút trong cây có một danh sách các nút con z Danh sách các nút con thường là danh sách móc nối z Trong trường hợp sử dụng danh sách móc nối, các nút đầu danh sách được lưu trong một mảng Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 9 Đỗ Bích Diệp - Khoa CNTT Biểu diễn cây tổng quát – Dựa trên danh sách các nút con A H DCB E G L N 1 2 3 4 5 6 7 8 9 NULL NULL NULL 98 NULL NULL 76 5 432A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] Đỗ Bích Diệp - Khoa CNTT Biểu diễn cây tổng quát – Thông qua một cây cấp 2 z Với một nút trong cây , chỉ quan tâm tới 2 quan hệ – Quan hệ 1-1 giữa nút đó và nút con cực trái của nó (con cả) – Quan hệ 1-1 giữa nút đó và nút em kế cận bên phải của nó z Dựa vào nhận định này, người ta biểu diễn được một cây tổng quát dưới dạng một cây nhị phân gọi là cây nhị phân tương đương (equivalent binary tree) z Quy cách của 1 nút trên cây nhị phân tương đương sẽ như sau RSIBLINGINFOLCHILD Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 10 Đỗ Bích Diệp - Khoa CNTT Biểu diễn cây tổng quát z Ví dụ: – Cây tổng quát – Cây nhị phân tương đương A H DCB E F G I K A B E F C G D H I K Đỗ Bích Diệp - Khoa CNTT Duyệt cây theo thứ tự trước z Duyệt cây là thăm các nút trên cây theo một thứ tự nhất định, mỗi nút thăm 1 lần z Khi duyệt theo thứ tự trước, một nút sẽ được thăm trước các hậu duệ của nó z Ứng dụng: In ra các mục lục của một tài liệu I. A 1. B 3.D2. C 2.1 G 2.2 H1.1 E 1.2 F 2.3 I 1 3 5 4 6 7 8 9 Algorithm preOrder(v) visit(v) for each child w of v preOrder(w) 2 Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 11 Đỗ Bích Diệp - Khoa CNTT Duyệt cây theo thứ tự trước I. A 1. B 3. D2. C 2.1 G 2.2 H1.1 E 1.2 F 2.3 I 1 ⇒ z Duyệt cây là thăm các nút trên cây theo một thứ tự nhất định, mỗi nút thăm 1 lần z Khi duyệt theo thứ tự trước, một nút sẽ được thăm trước các hậu duệ của nó z Ứng dụng: In ra các mục lục của một tài liệu Algorithm preOrder(v) visit(v) for each child w of v preOrder(w) Đỗ Bích Diệp - Khoa CNTT Duyệt cây theo thứ tự trước I. A 1. B 3. D2. C 2.1 G 2.2 H1.1 E 1.2 F 2.3 I 1 ⇒ z Duyệt cây là thăm các nút trên cây theo một thứ tự nhất định, mỗi nút thăm 1 lần z Khi duyệt theo thứ tự trước, một nút sẽ được thăm trước các hậu duệ của nó z Ứng dụng: In ra các mục lục của một tài liệu Algorithm preOrder(v) visit(v) for each child w of v preOrder(w) Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 12 Đỗ Bích Diệp - Khoa CNTT Duyệt cây theo thứ tự trước ⇒ z Duyệt cây là thăm các nút trên cây theo một thứ tự nhất định, mỗi nút thăm 1 lần z Khi duyệt theo thứ tự trước, một nút sẽ được thăm trước các hậu duệ của nó z Ứng dụng: In ra các mục lục của một tài liệu Algorithm preOrder(v) visit(v) for each child w of v preOrder(w) I. A 1. B 3. D2. C 2.1 G 2.2 H1.1 E 1.2 F 2.3 I 1 2 Đỗ Bích Diệp - Khoa CNTT Duyệt cây theo thứ tự trước ⇒ z Duyệt cây là thăm các nút trên cây theo một thứ tự nhất định, mỗi nút thăm 1 lần z Khi duyệt theo thứ tự trước, một nút sẽ được thăm trước các hậu duệ của nó z Ứng dụng: In ra các mục lục của một tài liệu Algorithm preOrder(v) visit(v) for each child w of v preOrder(w) I. A 1. B 3. D2. C 2.1 G 2.2 H1.1 E 1.2 F 2.3 I 1 2 Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 13 Đỗ Bích Diệp - Khoa CNTT Duyệt cây theo thứ tự trước ⇒ z Duyệt cây là thăm các nút trên cây theo một thứ tự nhất định, mỗi nút thăm 1 lần z Khi duyệt theo thứ tự trước, một nút sẽ được thăm trước các hậu duệ của nó z Ứng dụng: In ra các mục lục của một tài liệu Algorithm preOrder(v) visit(v) for each child w of v preOrder(w) I. A 1. B 3. D2. C 2.1 G 2.2 H1.1 E 1.2 F 2.3 I 1 2 3 Đỗ Bích Diệp - Khoa CNTT Duyệt cây theo thứ tự trước Thăm nút con tiếp theo z Duyệt cây là thăm các nút trên cây theo một thứ tự nhất định, mỗi nút thăm 1 lần z Khi duyệt theo thứ tự trước, một nút sẽ được thăm trước các hậu duệ của nó z Ứng dụng: In ra các mục lục của một tài liệu Algorithm preOrder(v) visit(v) for each child w of v preOrder(w) I. A 1. B 3. D2. C 2.1 G 2.2 H1.1 E 1.2 F 2.3 I 1 2 3 Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 14 Đỗ Bích Diệp - Khoa CNTT Duyệt cây theo thứ tự trước ⇒ z Duyệt cây là thăm các nút trên cây theo một thứ tự nhất định, mỗi nút thăm 1 lần z Khi duyệt theo thứ tự trước, một nút sẽ được thăm trước các hậu duệ của nó z Ứng dụng: In ra các mục lục của một tài liệu Algorithm preOrder(v) visit(v) for each child w of v preOrder(w) I. A 1. B 3. D2. C 2.1 G 2.2 H1.1 E 1.2 F 2.3 I 1 2 3 Đỗ Bích Diệp - Khoa CNTT Duyệt cây theo thứ tự trước ⇒ z Duyệt cây là thăm các nút trên cây theo một thứ tự nhất định, mỗi nút thăm 1 lần z Khi duyệt theo thứ tự trước, một nút sẽ được thăm trước các hậu duệ của nó z Ứng dụng: In ra các mục lục của một tài liệu Algorithm preOrder(v) visit(v) for each child w of v preOrder(w) I. A 1. B 3. D2. C 2.1 G 2.2 H1.1 E 1.2 F 2.3 I 1 2 3 4 Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 15 Đỗ Bích Diệp - Khoa CNTT Duyệt cây theo thứ tự trước Không còn con Quay lại nút gốc z Duyệt cây là thăm các nút trên cây theo một thứ tự nhất định, mỗi nút thăm 1 lần z Khi duyệt theo thứ tự trước, một nút sẽ được thăm trước các hậu duệ của nó z Ứng dụng: In ra các mục lục của một tài liệu Algorithm preOrder(v) visit(v) for each child w of v preOrder(w) I. A 1. B 3. D2. C 2.1 G 2.2 H1.1 E 1.2 F 2.3 I 1 2 3 4 Đỗ Bích Diệp - Khoa CNTT Duyệt cây theo thứ tự trước z Duyệt cây là thăm các nút trên cây theo một thứ tự nhất định, mỗi nút thăm 1 lần z Khi duyệt theo thứ tự trước, một nút sẽ được thăm trước các hậu duệ của nó z Ứng dụng: In ra các mục lục của một tài liệu Algorithm preOrder(v) visit(v) for each child w of v preOrder(w) I. A 1. B 3. D2. C 2.1 G 2.2 H1.1 E 1.2 F 2.3 I 1 2 3 4 Thăm nút con tiếp theo của gốc Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 16 Đỗ Bích Diệp - Khoa CNTT Duyệt cây theo thứ tự trước z Duyệt cây là thăm các nút trên cây theo một thứ tự nhất định, mỗi nút thăm 1 lần z Khi duyệt theo thứ tự trước, một nút sẽ được thăm trước các hậu duệ của nó z Ứng dụng: In ra các mục lục của một tài liệu Algorithm preOrder(v) visit(v) for each child w of v preOrder(w) I. A 1. B 3. D2. C 2.1 G 2.2 H1.1 E 1.2 F 2.3 I 1 2 3 4 ⇒ Đỗ Bích Diệp - Khoa CNTT Duyệt cây theo thứ tự trước z Duyệt cây là thăm các nút trên cây theo một thứ tự nhất định, mỗi nút thăm 1 lần z Khi duyệt theo thứ tự trước, một nút sẽ được thăm trước các hậu duệ của nó z Ứng dụng: In ra các mục lục của một tài liệu Algorithm preOrder(v) visit(v) for each child w of v preOrder(w) I. A 1. B 3. D2. C 2.1 G 2.2 H1.1 E 1.2 F 2.3 I 1 2 3 4 ⇒ 5 Và tiếp tục như vậy . Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 17 Đỗ Bích Diệp - Khoa CNTT Duyệt cây theo thứ tự sau z Duyệt theo thứ tự sau thì một nút sẽ được thăm sau các hậu duệ của nó z Ứng dụng: Xác định kích thước của các tệp trong một thư mục và các thư mục con của Algorithm postOrder(v) for each child w of v postOrder(w) visit(v) cs16/ homeworks/ todo.txt1Kprograms/ DDR.java 10K Stocks.java 25K h1c.doc 3K h1nc.doc 2K Robot.java 20K 9 3 1 7 2 4 5 6 8 Đỗ Bích Diệp - Khoa CNTT Duyệt cây theo thứ tự giữa z Duyệt theo thứ tự giữa thì một nút sẽ được thăm sau các hậu duệ của nó trong cây con cực trái và trước các hậu duệ trong các cây con tiếp theo Algorithm inOrder(v) if (isLeaf(v)) then visit(v) else inOrder(left_most_child(v)) visit(v) for each child w of v (w is not the left most child) inOrder(w)cs16/ homeworks/ todo.txt1Kprograms/ DDR.java 10K Stocks.java 25K h1c.doc 3K h1nc.doc 2K Robot.java 20K 4 2 1 6 3 5 7 8 9 Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 18 Đỗ Bích Diệp - Khoa CNTT Cây nhị phân ( Binary Tree) – Là cây mà mọi nút trên cây chỉ có tối đa là 2 con. z Cây con của một nút cũng cần phải được phân biệt rõ ràng thành cây con trái (left subtree) và cây con phải (right subtree) A B C E FD G left-subtree right-subtree Đỗ Bích Diệp - Khoa CNTT Ví dụ cây nhị phân – Cây biểu thức số học với các phép toán 2 ngôi + - / x zx * 3 y Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 19 Đỗ Bích Diệp - Khoa CNTT Ví dụ cây nhị phân – Cây quyết định Want a fast meal? How about coffee? On expense account? Starbucks Spike’s Al Forno Café Paragon Yes No Yes No Yes No Đỗ Bích Diệp - Khoa CNTT Ví dụ cây nhị phân – Kết quả thi đấu một môn thể thao theo cặp tại nhiều vòng H A H H FA E C EA D B H G F Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 20 Đỗ Bích Diệp - Khoa CNTT Các dạng đặc biệt của cây nhị phân z Cây suy biến (degenerate binary tree) – Mỗi nút trong của cây có đúng 1 nút con A C F G A C F G A C F G A C G F (a) (b) (c) (d) Đỗ Bích Diệp - Khoa CNTT Các dạng đặc biệt của cây nhị phân z Cây nhị phân đầy đủ (full binary tree) – Mỗi nút trong của cây đều có đầy đủ 2 con z Cây nhị phân gần đầy – Ở mức cuối cùng không có đầy đủ các nút A B C E FD G A B C F GD K E IH J Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 21 Đỗ Bích Diệp - Khoa CNTT Các dạng đặc biệt của cây nhị phân z Cây nhị phân hoàn chỉnh – Là cây nhị phân gần đầy – Tất cả các nút ở mức cuối cùng đều lệch về bên trái nhất có thể z Cây nhị phân cân đối z Cây con trái và cây con phải lệch nhau không quá 1 đơn vị A B C F GD E IH JL K Đỗ Bích Diệp - Khoa CNTT Tính chất của Cây nhị phân 1. Số lượng tối đa của các nút ở mức i trên một cây nhị phân là 2i-1 (i >= 1) 2. Số lượng tối đa các nút trên một cây nhị phân có chiều cao là h là 2h – 1 (h >= 1) 3. Một cây nhị phân có n nút có chiều cao tối thiểu là 4. Một cây nhị phân đầy đủ có độ sâu n thì có 2n -1 nút 5. Một cây nhị phân hoàn chỉnh có chiều cao h có số lượng nút nằm trong khoảng 2h-1 đến 2h – 1 6. Trong một cây nhị phân có n0 nút lá và n2 nút cấp 2 thì ta có n0 = n2 + 1 ⎡ ⎤)1(log2 +n Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 22 Đỗ Bích Diệp - Khoa CNTT Biểu diễn cây nhị phân – Biểu diễn kế tiếp sử dụng mảng z Đánh số các nút trên cây theo trình tự từ mức 1, hết mức này đến mức khác, từ trái sang phải z Lưu trữ trong vector lưu trữ V theo nguyên tắc phần tử V[i] sẽ lưu thông tin của nút được đánh số i Đỗ Bích Diệp - Khoa CNTT Biểu diễn cây nhị phân – Ví dụ – Cây cho ở trên được lưu trữ trên vector lưu trữ V như sau A B C D E F G I K 1 2 3 4 5 6 7 8 9 V[9]V[8]V[7]V[6]V[5]V[4]V[3]V[2]V[1] KIGFEDCBA Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 23 Đỗ Bích Diệp - Khoa CNTT Biểu diễn cây nhị phân z Cách lưu trữ kế tiếp phù hợp để lưu trữ cây nhị phân gần đầy hoặc đầy đủ z Với các dạng khác có thể dẫn đến lãng phí bộ nhớ A C G F 1 2 4 8 V[8]V[7]V[6]V[5]V[4]V[3]V[2]V[1] 8FCA Đỗ Bích Diệp - Khoa CNTT Biểu diễn cây nhị phân z Biểu diễn móc nối sử dụng con trỏ – Mỗi nút trên cây được lưu trữ bởi một phần tử có quy cách như sau z INFO: chứa dữ liệu của nút z LPTR: chứa địa chỉ của nút gốc của cây con trái z RPTR: chứa địa chỉ của nút gốc của cây con phải – Cần nắm một con trỏ T trỏ tới nút gốc của cây. Nếu cây rỗng thì T = NULL RPTRINFOLPTR Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 24 Đỗ Bích Diệp - Khoa CNTT Biểu diễn cây nhị phân A B C D E F K A B C D E F K T Đỗ Bích Diệp - Khoa CNTT Biểu diễn cây nhị phân struct Tnode{ int info; struct Tnode * lptr; struct Tnode * rptr; } ; typedef struct Tnode TREENODE; typedef TREENODE *TREENODEPTR; Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 25 Đỗ Bích Diệp - Khoa CNTT Duyệt cây nhị phân – Phép duyệt cây nhị phân z Phép duyệt một cây là phép “thăm” lần lượt các nút trên cây đó sao cho mỗi nút chỉ được thăm một lần z Tồn tại 3 phép duyệt khác nhau đối với 1 cây nhị phân – 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: Đỗ Bích Diệp - Khoa CNTT Duyệt cây nhị phân – Ví dụ: Thực hiện duyệt cây z Duyệt theo thứ tự trước A B D H E I J C F G K z Duyệt theo thứ tự giữa H D B I E J A F C K G z Duyệt theo thứ tự sau H D I J E B F K G C A A B C F GD K E IH J Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 26 Đỗ Bích Diệp - Khoa CNTT Duyệt cây nhị phân theo thứ tự trước void PREORDER(TREENODEPTR tree) { if (tree != NULL) { printf(“%3d”, tree->info; PREORDER(tree->lptr); PREORDER(tree->rptr); } } Đỗ Bích Diệp - Khoa CNTT Duyệt cây nhị phân – Ví dụ 2: Cho cây nhị phân biểu diễn biểu thức số học sau, hãy đưa ra dãy các nút được thăm khi thực hiện các phép duyệt theo thứ tự trước, giữa và sau. Nhận xét về các dãy thu được + - ^ / 2x * 4 y y z Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 27 Đỗ Bích Diệp - Khoa CNTT Cây biểu thức – Bài toán 1: Dựng cây biểu diễn biểu thức số học: z Cho một biểu thức số học dưới dạng hậu tố, dựng cây biểu diễn biểu thức số học đó z Ví dụ: Cho biểu thức x 4 y * - y z / 2 ^ + . Dựng được cây biểu diễn biểu thức này như sau + - ^ / 2x * 4 y y z Đỗ Bích Diệp - Khoa CNTT Dựng cây biểu diễn biểu thức z Giải thuật Function BUILD_TREE_POSTFIX(TOKENS, n) {TOKENS : mang cac token cua xâu ký tự biểu diễn biểu thức ban đầu là biểu thức dưới dạng hậu tố, dưới dạng một mảng. n là số ký tự trong xâu} { S : Stack de chua du lieu tam thoi} Begin for i = 1 to n do Begin TK = TOKENS[i]; if isNumber(TK) | isChar(TK) Then begin Node = CreateTreeNode(TK); {tạo cây có một nút gốc là hạng tử } PUSH(S, Node); end; Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 28 Đỗ Bích Diệp - Khoa CNTT Dựng cây biểu diễn biểu thức z Giải thuật (tiếp) Else {TK la 1 toan tu} begin Right = POP(S); Left = POP(S); Node = CreateTreeNode(TK, Right, Left); {tao 1 cay gom 1 nut goc la toan tu TK va 2 nut con la 2 hang tu la right, left} PUSH(S,Node); end; end; T= POP(S); Return T; End; Đỗ Bích Diệp - Khoa CNTT Cây biểu thức – Bài toán 2: Tính giá trị của biểu thức số học biểu diễn bằng một cây nhị phân z Các nút lá biểu diễn các giá trị của các toán hạng z Các nút nhánh biểu diễn các dấu phép toán – Các dấu phép toán có thể sử dụng trong bài toán này là: +, - , *, /, ^ và teta (biểu diễn dấu âm ) – Qui ước là với nút nhánh là teta thì toán hạng của nó là con phải của nó Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 29 Đỗ Bích Diệp - Khoa CNTT Tính giá trị của biểu thức số học – Ví dụ + * ^ - teta 2 5 20 9 4 Đỗ Bích Diệp - Khoa CNTT Tính giá trị của biểu thức z Giải thuật tính giá trị biểu thức biểu diễn bằng cấu trúc cây Function COMPUTE_EXPRESSION(T) Begin IF IsLeaf(T) THEN Result := VAL(INFO(T)); ELSE BEGIN leftvalue := COMPUTE_EXPRESSION(LPTR(T)); rightvalue := COMPUTE_EXPRESSION(RPTR(T)); case (INFO(T)) '+' : Result = leftvalue + rightvalue; '-' : Result = leftvalue - rightvalue; '*' : Result = leftvalue * rightvalue; '/' : Result = leftvalue / rightvalue; ‘^' : Result = leftvalue ^ rightvalue; ‘teta' : Result = -( rightvalue); end case; END; return Result; End Cấu trúc dữ liệu và Giải thuật Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 30 Đỗ Bích Diệp - Khoa CNTT