Chương 4 Cây

Chương 4 CÂY Nội dung 4.1. Định nghĩa và cỏc khỏi niệm 4.2. Cõy nhị phõn 4.3. Cỏc ứng dụng 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 2 4.1. Định nghĩa và khỏi niệm 4.1.1. Định nghĩa 4.1.2. Cỏc thuật ngữ 4.1.3. Cõy cú thứ tự 4.1.4. Cõy cú nhón 4.1.5. ADT cõy 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 3 4.1.1. Định nghĩa cõy Cõy bao gồm cỏc nỳt, cú một nỳt đặc biệt được gọi là gốc (root) và cỏc cạnh nối cỏc nỳt. Cõy được định nghĩa đệ qui như sau: Định nghĩa cõy: Basic Step: Một nỳt r là cõy và r được gọi là gốc của cõy này. Recursive Step: Giả sử T1,T2,...,Tk là cỏc cõy với gốc là r1,r2,...,rk. Ta cú thể xõy dựng cõy mới bằng cỏch đặt r làm cha (parent) của cỏc nỳt r1,r2,..., rk . Trong cõy này r là gốc và T1, T2, . . . , Tk là cỏc cõy con của gốc r. Cỏc nỳt r1, r2, . . . , rk được gọi là con (children) của nỳt r. Chỳ ý: Nhiều khi để phự hợp ta cần định nghĩa cõy rỗng (null tree) là cõy khụng cú nỳt nào cả. 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 4 Cấu trỳc đệ qui của cõy r r1 rkr2 T1 T2 Tk 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 5 Cõy trong thực tế ứng dụng • Biểu đồ lịch thi đấu • Cõy gia phả • Biểu đồ phõn cấp quản lý hành chớnh. • Cõy thư mục • Cấu trỳc của một quyển sỏch • Cõy biểu thức • Cõy phõn hoạch tập hợp • ... 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 6 Cõy lịch thi đấu 1/28/2013 Trong đời thường cõy rất hay được sử dụng để diễn tả lịch thi đấu của cỏc giải thể thao theo thể thức đấu loại trực tiếp, chẳng hạn vũng 2 của World Cub Phỏp Tõy ban nha Brazin Anh Đức Ucrain Italia Ahentina Phỏp Brazin Đức Italia Phỏp Italia Italia CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 7 Cõy gia phả 1/28/2013 Cõy gia phả của cỏc nhà toỏn dũng họ Bernoulli Nikolaus 1623-1708 Johan I 1667-1748 Nikolaus 1662-1716 Jacob I 1654-1705 Nikolaus II 1695-1726 Daniel 1700-1782 Johan II 1710-1790 Nikolaus I 1687-1759 Jacob II 1759-1789 Johan III 1746-1807 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 8 Cõy phõn cấp quản lý hành chớnh Ban Giỏm đốc Phũng Tài vụ Phũng Tổ chức Phũng Hành chớnh Phũng Kinh doanh Phũng Kế hoạch Văn thưTP 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 9 Cõy thư mục 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 10 Cõy mục lục sỏch 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 11 Cõy gia phả ngược (Ancestor Tree) 1/28/2013 Cõy phả hệ ngược: mỗi người đều cú bố mẹ. Cõy này là cõy nhị phõn (binary tree). Thựy Hương Thỳy Cải Quang Dũng Bớch Liờn Trung Kiờn Hoàng Cỳc Quang Thỏi CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 12 Cõy biểu thức (Expression Tree) 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT / + / 1 3 * 6 7 4 1/3 + 6*7 / 4 13 Cõy phõn hoạch tập hợp 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} Tập con cỏc số lẻ: {1, 3, 5, 7, 9} Tập con cỏc số chẵn: { 2, 4, 6, 8, 10} Tập con cỏc số nguyờn tố: { 3, 5, 7 } {1, 9} Tập con số hoàn hảo: { 6 } { 2, 4, 8, 10} 14 4.1. Định nghĩa và khỏi niệm 4.1.1. Định nghĩa 4.1.2. Cỏc thuật ngữ 4.1.3. Cõy cú thứ tự 4.1.4. Cõy cú nhón 4.1.5. ADT cõy 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 15 4.1.2. Cỏc thuật ngữ chớnh • Nỳt - node • Gốc - root • Lỏ - leaf • Con - child • Cha - parent • Tổ tiờn - ancestors • Hậu duệ - descendants • Anh em - sibling • Nỳt trong - internal node • Chiều cao - hight • Chiều sõu - depth 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 16 Cỏc thuật ngữ chớnh • Nếu n1, n2, . . . , nk là dóy nỳt trờn cõy sao cho ni là cha của ni+1 với 1  i < k, thỡ dóy này được gọi là đường đi (path) từ nỳt n1 tới nỳt nk. Độ dài (length) của đường đi là bằng số lượng nỳt trờn đường đi trừ bớt 1. Như vậy đường đi độ dài 0 là đường đi từ một nỳt đến chớnh nú. • Nếu cú đường đi từ nỳt a tới nỳt b, thỡ a được gọi là tổ tiờn (ancestor) của b, cũn b được gọi là hậu duệ (descendant) của a. • Tổ tiờn (hậu duệ) của một nỳt khỏc với chớnh nú được gọi là tổ tiờn (hậu duệ) chớnh thường (proper). Trong cõy, gốc là nỳt khụng cú tổ tiờn chớnh thường và mọi nỳt khỏc trờn cõy đều là hậu duệ chớnh thường của nú. • Một nỳt khụng cú hậu duệ chớnh thường được gọi lỏ lỏ (leaf). • Cỏc nỳt cú cựng cha được gọi là anh em (sibling). • Cõy con (subtree) của một cõy là một nỳt cựng với tất cả cỏc hậu duệ của nú. • Chiều cao (height) của nỳt trờn cõy là bằng độ dài của đường đi dài nhất từ nỳt đú đến lỏ cộng 1. Chiều cao của cõy (height of a tree) là chiều cao của gốc. Độ sõu/mức (depth/level) của nỳt là bằng 1 cộng với độ dài của đường đi duy nhất từ gốc đến nú. 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 17 Thuật ngữ nỳt nodes 1/28/2013CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 18 Thuật ngữ Nỳt cha parent node 1/28/2013CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 19 Thuật ngữ con child cha parent 1/28/2013CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 20 Thuật ngữ concha 1/28/2013CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 21 Thuật ngữ gốc - root lỏ - leaf 1/28/2013CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 22 Thuật ngữ cõy con - subtree 1/28/2013CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 23 Thuật ngữ cõy con 1/28/2013CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 24 Thuật ngữ cõy con 1/28/2013CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 25 Cỏc thuật ngữ với cõy cú gốc a b d e f i j g h c k root, ancestor parent nỳt child child descendent leaf (khụng cú con) e, i, k, g, h là lỏ (leaves) internal node (khụng là lỏ) sibling 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 26 Đường đi trờn cõy a cb e f d g j ih Path 1 Path 2 Path 1: { a, b, f, j } Path 2: { d, i } Từ cha đến con và đến cỏc nỳt hậu duệ. Cú duy nhất 1 đường đi từ một nỳt đến một nỳt là hậu duệ của nú. 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 27 Độ cao (height) và độ sõu/mức (depth/level) 7 3 10 8 4 12 16 5 211 9 độ cao h = 5 độ sõu 1 độ sõu 2 độ sõu 3 độ sõu 4 độ sõu 5 độ cao = 4 độ cao = 3 độ cao h=1 h = 2 Độ cao của cõy là 5 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 28 How We View a Tree Nature Lovers View Computer Scientists View 1/28/2013CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 29 Bậc (Degree) 9 Số lượng con của nỳt x được gọi là bậc (degree) của x. degree = 3 7 3 10 8 4 12 16 5 211degree = 1 degree = 0 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 30 4.1. Định nghĩa và khỏi niệm 4.1.1. Định nghĩa 4.1.2. Cỏc thuật ngữ 4.1.3. Cõy cú thứ tự 4.1.4. Cõy cú nhón 4.1.5. ADT cõy 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 31 4.1.3. Cõy cú thứ tự - Ordered Tree • Thứ tự của cỏc nỳt • Cỏc con của một nỳt thường được xếp thứ tự từ trỏi sang phải. Như vậy hai cõy trong hỡnh sau đõy là khỏc nhau, bởi vỡ hai con của nỳt a xuất hiện trong hai cõy theo thứ tự khỏc nhau: • Cõy với cỏc nỳt được xếp thứ tự được gọi là cõy cú thứ tự. Ta sẽ xột chủ yếu là cõy cú thứ tự. Vỡ vậy, tiếp theo thuật ngữ cõy là để chỉ cõy cú thứ tự. Khi muốn khẳng định là khụng quan tõm đến thứ tự, ta sẽ phải núi rừ là cõy khụng cú thứ tự. a b c a c b 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 32 Xếp thứ tự cỏc nỳt • Ta cú thể xếp thứ tự cỏc nỳt của cõy theo nhiều cỏch. Cú ba thứ tự quan trọng nhất, đú là Thứ tự trước, Thứ tự sau và Thứ tự giữa (Preorder, Postorder, và Inorder) • Cỏc thứ tự này được định nghĩa một cỏch đệ qui như sau – Nếu cõy T là rỗng, thỡ danh sỏch rỗng là danh sỏch theo thứ tự trước, thứ tự sau và thứ tự giữa của cõy T. – Nếu cõy T cú một nỳt, thỡ nỳt đú chớnh là danh sỏch theo thứ tự trước, thứ tự sau và thứ tự giữa của cõy T. – Trỏi lại, giả sử T là cõy cú gốc r với cỏc cõy con là T1, T2,..., Tk. 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 33 Duyệt theo thứ tự trước - Preorder Traversal • Thứ tự trước (hay duyệt theo thứ tự trước - preorder traversal) của cỏc nỳt của T là: – Gốc r của T, – tiếp đến là cỏc nỳt của T1 theo thứ tự trước, – tiếp đến là cỏc nỳt của T2 theo thứ tự trước, – ... – và cuối cựng là cỏc nỳt của Tk theo thứ tự trước. r r1 rkr2 T1 T2 Tk 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 34 Duyệt theo thứ tự sau - Postorder Traversal • Thứ tự sau của cỏc nỳt của cõy T là: – Cỏc nỳt của T1 theo thứ tự sau, – tiếp đến là cỏc nỳt của T2 theo thứ tự sau, – ... – cỏc nỳt của Tk theo thứ tự sau, – sau cựng là nỳt gốc r. r r1 rkr2 T1 T2 Tk 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 35 Duyệt theo thứ tự giữa - Inorder Traversal • Thứ tự giữa của cỏc nỳt của cõy T là: – Cỏc nỳt của T1 theo thứ tự giữa, – tiếp đến là nỳt gốc r, – tiếp theo là cỏc nỳt của T2, . . . , Tk, mỗi nhúm nỳt được xếp theo thứ tự giữa. r r1 rkr2 T1 T2 Tk 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 36 Thuật toỏn duyệt theo thứ tự trước - Preorder Traversal void PREORDER ( nodeT r ) { (1) Đưa ra r; (2) for (mỗi con c của r, nếu cú, theo thứ tự từ trỏi sang) do PREORDER(c); } • Vớ dụ: Thứ tự trước của cỏc đỉnh của cõy trờn hỡnh vẽ là a, b, c, e, h, i, f, j, d, g a b c d f g ih e j 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 37 Thuật toỏn duyệt theo thứ tự sau - Postorder Traversal • Thuật toỏn duyệt theo thứ tự sau thu được bằng cỏch đảo ngược hai thao tỏc (1) và (2) trong PREORDER: void POSTORDER ( nodeT r ) { for (mỗi con c của r, nếu cú, theo thứ tự từ trỏi sang) do POSTORDER(c) Đưa ra r; } • Vớ dụ: Dóy cỏc đỉnh được liệt kờ theo thứ tự sau của cõy trong hỡnh vẽ là: b, h, i, e, j, f, c, g, d, a a b c d f g ih e j 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 38 Thuật toỏn duyệt theo thứ tự giữa - Inorder Traversal void INORDER (nodeT r ) { if ( r là lỏ ) Đưa ra r; else { INORDER(con trỏi nhất của r); Đưa ra r; for (mỗi con c của r, ngoại trừ con trỏi nhất, theo thứ tự từ trỏi sang) do INORDER(c); } } • Vớ dụ: Dóy cỏc đỉnh của cõy trong hỡnh vẽ được liệt kờ theo thứ tự giữa: b, a, h, e, i, c, j, f, g, d a b c d f g ih e j 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 39 Xếp thứ tự cỏc nỳt • Để nhớ cỏch đưa ra cỏc nỳt theo ba thứ tự vừa trỡnh bày hóy hỡnh dung là ta đi vũng quanh bờn ngoài cõy bắt đầu từ gốc, ngược chiều kim đồng hồ và sỏt theo cõy nhất. Chẳng hạn, đường đi đú đối với cõy trong cỏc vớ dụ đó xột trờn là như sau: a b c d f g ih e j • Đối với thứ tự trước, ta đưa ra nỳt mỗi khi đi qua nú. • Đối với thứ tự sau, ta đưa ra nỳt khi qua nú ở lần cuối trước khi quay về cha của nú. • Đối với thứ tự giữa, ta đưa ra lỏ ngay khi đi qua nú, cũn những nỳt trong được đưa ra khi lần thứ hai được đi qua. • Chỳ ý rằng cỏc lỏ được xếp thứ tự từ trỏi sang phải như nhau trong cả ba cỏch sắp xếp. 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 40 4.1.4. Cõy cú nhón (Labeled Tree) • Thụng thường người ta gỏn cho mỗi nỳt của cõy một nhón (label) hoặc một giỏ trị, cũng tương tự như chỳng ta đó gỏn mỗi nỳt của danh sỏch với một phần tử. Nghĩa là, nhón của nỳt khụng phải là tờn gọi của nỳt mà là giỏ trị được cất giữ trong nú. Trong một số ứng dụng ta cú thể thay đổi nhón của nỳt mà tờn của nú vẫn được giữ nguyờn. • Vớ dụ: Xột cõy cú 7 nỳt n1, ..., n7. Ta gỏn nhón cho cỏc nỳt như sau: – Nỳt n1 cú nhón *; – Nỳt n2 cú nhón +; – Nỳt n3 cú nhón -; – Nỳt n4 cú nhón a; – Nỳt n5 cú nhón b; – Nỳt n6 cú nhón a; – Nỳt n7 cú nhón c. 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT n1 * + - a n3 n6 n7n5n4 n2 b a c 41 Cõy biểu thức (Expression Tree) • Cõy trong vớ dụ vừa nờu cú tờn gọi là cõy biểu thức (a+b)*(a-c) • Qui tắc để cõy cú nhón biểu diễn một biểu thức là: – Mỗi nỳt lỏ cú nhón là toỏn hạng và chỉ gồm một toỏn hạng đú. Vớ dụ nỳt n4 biểu diễn biểu thức a. – Mỗi nỳt trong n được gỏn nhón là phộp toỏn. Giả sử n cú nhón là phộp toỏn hai ngụi q, như + hoặc *, và con trỏi biểu diễn biểu thức E1 và con phải biểu diễn biểu thức E2. Khi đú n biểu diễn biểu thức (E1) q (E2). Ta cú thể bỏ dấu ngoặc nếu như điều đú là khụng cần thiết. • Vớ dụ: – Nỳt n2 chứa toỏn hạng + và con trỏi và con phải của nú là a và b. Vỡ thế n2 biểu diễn (a) + (b), hay a+b. 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT n1 * + - a n3 n6 n7n5n4 n2 b a c 42 4.1. Định nghĩa và khỏi niệm 4.1.1. Định nghĩa 4.1.2. Cỏc thuật ngữ 4.1.3. Cõy cú thứ tự 4.1.4. Cõy cú nhón 4.1.5. ADT cõy 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 43 4.1.5. ADT Cõy • Trong chương này chỳng ta tỡm hiểu cõy vừa như là kiểu dữ liệu trừu tượng vừa như là kiểu dữ liệu. Một trong những ứng dụng quan trọng của cõy là nú được dựng để thiết kế và cài đặt nhiều kiểu dữ liệu trừu tượng quan trọng khỏc như "Cõy tỡm kiếm nhị phõn", "Tập hợp",.... • Cũng như danh sỏch, đối với cõy cũng cú thể xột rất nhiều phộp toỏn làm việc với nú. Dưới đõy ta chỉ kể ra một số phộp toỏn cơ bản. 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 44 4.1.5. ADT Cõy • parent(n, T). Hàm này trả lại cha của nỳt n trong cõy T. Nếu n là gốc (nú khụng cú cha), trả lại . Theo nghĩa này,  là nỳt rỗng ("null node") dựng để bỏo hiệu rằng chỳng ta sẽ dời khỏi cõy. • leftmost_child(n, T) trả lại con trỏi nhất của nỳt n trong cõy T, và trả lại  nếu n là lỏ (khụng cú con). • right_sibling(n, T) trả lại em bờn phải của nỳt n trong cõy T (được định nghĩa như là nỳt m cú cựng cha là p giống như n sao cho m nằm sỏt bờn phải của n trong danh sỏch sắp thứ tự cỏc con của p. – Vớ dụ, với cõy trong slide gần nhất: • leftmost_child(n2) = n4; • right_sibling(n4) = n5, và RIGHT_SIBLING (n5) = L. 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 45 4.1.5. ADT Cõy • label(n, T) trả lại nhón của nỳt n trong cõy T. Tuy nhiờn, ta khụng đũi hỏi cõy nào cũng cú nhón. • createi(v, T1, T2, . . . , Ti) là họ cỏc hàm, mỗi hàm cho một giỏ trị của i = 0, 1, 2, ... createi tạo một nỳt mới r với nhón v và gắn cho nú i con, với cỏc con là cỏc gốc của cõy T1, T2, ..., Ti, theo thứ tự từ trỏi sang. Trả lại cõy với gốc r. Chỳ ý, nếu i = 0, thỡ r vừa là lỏ vừa là gốc. • root(T) trả lại nỳt là gốc của cõy T, hoặc  nếu T là cõy rỗng. • makenull(T) biến T thành cõy rỗng. 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 46 Biểu diễn cõy • Cú nhiều cỏch biểu diễn cõy. Ta giới thiệu qua về ba cỏch biểu diễn cơ bản: – dựng mảng (Array Representation) – danh sỏch cỏc con (Lists of Children) – dựng con trỏi và em phải (The Leftmost-Child, Right- Sibling Representation) 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 47 Biểu diễn cõy dựng mảng • Giả sử T là cõy với cỏc nỳt đặt tờn là 1, 2, . . . , n. Cỏch đơn giản để biểu diễn T là hỗ trợ thao tỏc parent bởi danh sỏch tuyến tớnh A trong đú mỗi phần tử A[i] chứa con trỏ đến cha của nỳt i. Riờng gốc của T cú thể phõn biệt bởi con trỏ rỗng. • Khi dựng mảng, ta đặt A[i] = j nếu nỳt j là cha của nỳt i, và A[i] = 0 nếu nỳt i là gốc. • Cỏch biểu diễn này dựa trờn cơ sở là mỗi nỳt của cõy (ngoại trừ gốc) đều cú duy nhất một cha. Với cỏch biểu diễn này cha của một nỳt cú thể xỏc định trong thời gian hằng số. Đường đi từ một nỳt đến tổ tiờn của chỳng (kể cả đến gốc) cú thể xỏc định dễ dàng: n <- parent(n) <- parent(parent(n)) <- ... • Ta cũng cú thể đưa thờm vào mảng L[i] để hỗ trợ việc ghi nhận nhón cho cỏc nỳt, hoặc biến mỗi phần tử A[i] thành bản ghi gồm hai trường: biến nguyờn ghi nhận cha và nhón. 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 48 Biểu diễn cõy dựng mảng • Vớ dụ A • Hạn chế: Cỏch dựng con trỏ cha khụng thớch hợp cho cỏc thao tỏc với con. Cho nỳt n, ta sẽ mất nhiều thời gian để xỏc định cỏc con của n, hoặc chiều cao của n. Hơn nữa biểu diễn bởi con trỏ cha khụng cho ta thứ tự của cỏc nỳt con. Vỡ thế cỏc phộp toỏn như leftmost_child và right_sibling là khụng xỏc định được. Do đú cỏch biểu diễn này chỉ dựng trong một số trường hợp nhất định. 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 1 3 6 1054 2 97 8 0 1 1 2 2 3 6 6 6 3 49 Danh sỏch cỏc con (Lists of Children) • Trong cỏch biểu diễn này, với mỗi nỳt của cõy ta cất giữ một danh sỏch cỏc con của nú. • Danh sỏch con cú thể biểu diễn bởi một trong những cỏch biểu diễn danh sỏch đó trỡnh bày trong chương trước. • Tuy nhiờn, để ý rằng số lượng con của cỏc nỳt là rất khỏc nhau, nờn danh sỏch múc nối thường là lựa chọn thớch hợp nhất. 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 50 Danh sỏch cỏc con (Lists of Children) • Cú mảng con trỏ đến đầu cỏc danh sỏch con của cỏc nỳt 1, 2, . . . , 10: header[i] trỏ đến danh sỏch con của nỳt i. 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 1 3 6 1054 2 97 8 1 2 3 2 4 5 3 6 10 4  5  6 7 8 9 7  8  9  10  header 51 Danh sỏch cỏc con (Lists of Children) • Vớ dụ: Cú thể sử dụng mụ tả sau đõy để biểu diễn cõy typedef ? NodeT; /* dấu ? cần thay bởi định nghĩa kiểu phự hợp */ typedef ? ListT; /* dấu ? cần thay bởi định nghĩa kiểu danh sỏch phự hợp */ typedef ? position; typedef struct { ListT header[maxNodes]; labeltype labels[maxNodes]; NodeT root; } TreeT; • Ta giả thiết rằng gốc của cõy được cất giữ trong trường root và 0 để thể hiện nỳt rỗng. 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 52 Cài đặt leftmost_child • Dưới đõy là minh họa cài đặt phộp toỏn leftmost_child. Việc cài đặt cỏc phộp toỏn cũn lại được coi là bài tập. NodeT leftmost_child (NodeT n, TreeT T) /* trả lại con trỏi nhất của nỳt n trong cõy T */ { ListT L; /* danh sỏch cỏc con của n */ L = T.header[n]; if (empty(L)) /* n là lỏ */ return(0); else return(retrive ( first(L), L)); } 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 53 Dựng con trỏi và em kế cận phải (The Leftmost-Child, Right-Sibling Representation) • Rừ ràng, mỗi một nỳt của cõy chỉ cú thể cú: – hoặc là khụng cú con, hoặc cú đỳng một nỳt con cực trỏi (con cả); – hoặc là khụng cú em kế cận phải, hoặc cú đỳng một nỳt em kế cận phải (right-sibling). • Vỡ vậy để biểu diễn cõy ta cú thể lưu trữ thụng tin về con cực trỏi và em kế cận phải của mỗi nỳt. Ta cú thể sử dụng mụ tả sau: struct Tnode { char word[20]; // Dữ liệu cất giữ ở nỳt struct Tnode *leftmost_child; struct Tnode *right_sibling; }; typedef struct Tnode treeNode; treeNode Root; 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 54 Biểu diễn cõy bởi con trỏi và em kề cận phải 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT A A B DC JIH FE G K D FE H G B I C KJ 55 Biểu diễn cõy tổng quỏt bởi cõy nhị phõn (con trỏi và con phải=em kề cận phải) 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT A AB D C J I H F E G K D FE H G B I C KJ Cõy nhị phõn 56 Dựng con trỏi và em kế cận phải (The Leftmost-Child, Right-Sibling Representation) • Với cỏch biểu diễn này, cỏc thao tỏc cơ bản dễ dàng cài đặt. Duy chỉ cú thao tỏc parent là đũi hỏi phải duyệt danh sỏch nờn khụng hiệu quả. Trong trường hợp phộp toỏn này phải dựng thường xuyờn, người ta chấp nhận bổ sung thờm 1 trường nữa vào bản ghi để lưu cha của nỳt. 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 57 4.2. CÂY NHỊ PHÂN 4.2.1. Định nghĩa và tớnh chất 4.2.2. Biểu diễn cõy nhị phõn 4.2.3. Duyệt cõy nhị phõn 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 58 4.2.1. Định nghĩa cõy nhị phõn - Binary Tree • Định nghĩa. Cõy nhị phõn là cõy mà mỗi nỳt cú nhiều nhất là hai con. – Vỡ mỗi nỳt chỉ cú khụng quỏ hai con, nờn ta sẽ gọi chỳng là con trỏi và con phải (left and right child). – Như vậy mỗi nỳt của cõy nhị phõn hoặc là khụng cú con, hoặc chỉ cú con trỏi, hoặc chỉ cú con phải, hoặc cú cả con trỏi và con phải. 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT Con trỏi Con phải 59 Chỳ ý • Vỡ ta phõn biệt con trỏi và con phải, nờn khỏi niệm cõy nhị phõn là khụng trựng với cõy cú thứ tự định nghĩa ở 4.1. • Vớ dụ: • Vỡ thế, chỳng ta sẽ khụng so sỏnh cõy nhị phõn với cõy tổng quỏt 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT a a b b c cd d e a b c d e e Cõy nhị phõn T1 Cõy nhị phõn T2 Cõy tổng quỏt 60 Tớnh chất của cõy nhị phõn • Bổ đề 1. (i) Số đỉnh lớn nhất ở trờn mức i của cõy nhị phõn là 2i-1, i≥1. (ii) Một cõy nhị phõn với chiều cao k cú khụng quỏ 2k-1 nỳt, k ≥ 1. (iii) Một cõy nhị phõn cú n nỳt cú chiều cao tối thiểu là log2(n+1). • Chứng minh: • (i) Bằng qui nạp theo i. – Cơ sở: Gốc là nỳt duy nhất trờn mức i=1. Như vậy số đỉnh lớn nhất trờn mức i=1 là 20= 2i-1. – Chuyển qui nạp: Giả sử với mọi j, 1 ≤ j < i, số đỉnh lớn nhất trờn mức j là 2j-1. Do số đỉnh trờn mức i-1 là 2i -2, mặt khỏc theo định nghĩa mỗi đỉnh trờn cõy nhị phõn cú khụng quỏ 2 con, ta suy ra số lượng nỳt lớn nhất trờn mức i là khụng vượt quỏ 2 lần số lượng nỳt trờn mức i-1, nghĩa là khụng vượt quỏ 2*2i - 2= 2i-1 . 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 61 Tớnh chất của cõy nhị phõn • (ii) Số lượng nỳt lớn nhất của cõy nhị phõn chiều cao k là khụng vượt quỏ tổng số lượng nỳt lớn nhất trờn cỏc mức i = 1, 2, ..., k, theo bổ đề 1, số này là khụng vượt quỏ • (iii) Cõy nhị phõn n nỳt cú chiều cao thấp nhất k khi số lượng nỳt ở cỏc mức i =1, 2, ..., k đều là lớn nhất cú thể được. Từ đú ta cú: 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 1 1 2 2 1. k i k i     1 2 1 2 2 1, suy ra 2 1, hay log ( 1) . k i k k i n n k n           62 Cõy nhị phõn đầy đủ (full binary tree) Định nghĩa. Cõy nhị phõn đầy đủ (Full Binary Trees) là cõy nhị phõn thoả món – mỗi nỳt lỏ đều cú cựng độ sõu và – cỏc nỳt trong cú đỳng 2 con. Bổ đề. Cõy nhị phõn đầy đủ với độ sõu n cú 2n -1 nỳt. Chứng minh. Suy trực tiếp từ bổ đề 1. 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 63 Cõy nhị phõn hoàn chỉnh (Complete Binary Trees) • Định nghĩa. Cõy nhị phõn hoàn chỉnh (Complete Binary Trees): Cõy nhị phõn độ sõu n thoả món: – là cõy nhị phõn đầy đủ nếu khụng tớnh đến cỏc nỳt ở độ sõu n, và – tất cả cỏc nỳt ở độ sõu n là lệch sang trỏi nhất cú thể được. • Bổ đề 3. Cõy nhị phõn hoàn chỉnh độ sõu n cú số lượng nỳt nằm trong khoảng từ 2n-1 đến 2n - 1. • Chứng minh. Suy trực tiếp từ định nghĩa và bổ đề 1. Vớ dụ. Cõy nhị phõn hoàn chỉnh 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 64 Cõy nhị phõn cõn đối (balanced binary tree) • Định nghĩa. Cõy nhị phõn được gọi là cõn đối (balanced ) nếu chiều cao của cõy con trỏi và chiều cao của cõy con phải chờnh lờch nhau khụng quỏ 1 đơn vị. • Nhận xột: – Nếu cõy nhị phõn là đầy đủ thỡ nú là hoàn chỉnh – Nếu cõy nhị phõn là hoàn chỉnh thỡ nú là cõn đối Vớ dụ: 1. Cõy nào là đầy đủ? 2. Cõy nào là hoàn chỉnh? 3. Cõy nào là cõn đối? 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 65 4.2. CÂY NHỊ PHÂN 4.2.1. Định nghĩa và tớnh chất 4.2.2. Biểu diễn cõy nhị phõn 4.2.3. Duyệt cõy nhị phõn 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 66 4.2.2. Biểu diễn cõy nhị phõn • Ta xột hai phương phỏp: – Biểu diễn sử dụng mảng – Biểu diễn sử dụng con trỏ • Biểu diễn sử dụng mảng: Hoàn toàn tương tự như trong cỏch biểu diễn cõy tổng quỏt. Tuy nhiờn, trong trường hợp cõy nhị phõn hoàn chỉnh, sử dụng cỏch biểu diễn này ta cú thể cài đặt nhiều phộp toỏn với cõy rất hiệu quả. • Xột cõy nhị phõn hoàn chỉnh T cú n nỳt, trong đú mỗi nỳt chứa một giỏ trị. Gỏn tờn cho cỏc nỳt của cõy nhị phõn hoàn chỉnh T từ trờn xuống dưới và từ trỏi qua phải bằng cỏc số 1, 2,..., n. Đặt tương ứng cõy T với mảng A trong đú phần tử thứ i của A là giỏ trị cất giữ trong nỳt thứ i của cõy T, i = 1, 2, ..., n. 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 67 Biểu diễn mảng của cõy nhị phõn hoàn chỉnh Complete Binary Tree H D B K LJF ECA 1 2 3 4 5 6 7 8 9 10 Biểu diễn kế tiếp (dựng mảng) H D K B F J L A C E 0 1 8 9 106 74 52 3 1/28/2013CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 68 Cõy nhị phõn hoàn chỉnh - Complete Binary Tree H D K B F J L A C E 0 1 8 9 106 74 52 3 Để tỡm Sử dụng Hạn chế Con trỏi của A[i] A[2*i] 2*i <= n Con phải của A[i] A[2*i + 1] 2*i + 1 <= n Cha của A[i] A[i/2] i > 1 Gốc A[1] A khỏc rỗng Thử A[i] là lỏ? True 2*i > n 1/28/2013CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 69 Biểu diễn cõy nhị phõn dựng con trỏ Mỗi nỳt của cõy sẽ cú con trỏ đến con trỏi và con trỏ đến con phải: struct Tnode { DataType Item; // DataType - kiểu dữ liệu của phần tử struct Tnode *left; struct Tnode *right; }; typedef struct Tnode treeNode; key Trỏ đến con trỏi Trỏ đến con phải 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 70 Vớ dụ 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT A AB D C J I H F E G K D FE H G B I C KJ Cõy nhị phõn 71 Cỏc phộp toỏn cơ bản struct Tnode { char word[20]; // Dữ liệu của nỳt struct Tnode * left; struct Tnode *right; }; typedef struct Tnode treeNode; treeNode* makeTreeNode(char *word); treeNode *RandomInsert(treeNode* tree,char *word); void freeTree(treeNode *tree); void printPreorder(treeNode *tree); void printPostorder(treeNode *tree); void printInorder(treeNode *tree); int countNodes(treeNode *tree); int depth(treeNode *tree); 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 72 MakeNode • Thụng số: Dữ liệu của nỳt cần bổ sung • Cỏc bước: – phõn bổ bộ nhớ cho nỳt mới – kiểm tra cấp phỏt bộ nhớ cú thành cụng? – nếu đỳng, đưa item vào nỳt mới – đặt con trỏ trỏi và phải bằng NULL • trả lại: con trỏ đến (là địa chỉ của) nỳt mới 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 73 Cài đặt MakeNode treeNode* makeTreeNode(char *word) { treeNode* newNode = NULL; newNode = (treeNode*)malloc(sizeof(treeNode)); if (newNode == NULL){ printf("Out of memory\n"); exit(1); } else { newNode->left = NULL; newNode->right= NULL; strcpy(newNode->word,word); } return newNode; } 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 74 Cài đặt hàm tớnh số nỳt và độ sõu của cõy int countNodes(treeNode *tree) { /* the function counts the number of nodes of a tree*/ if( tree == NULL ) return 0; else { int ld = countNodes(tree->left); int rd = countNodes(tree->right); return 1+ld+rd; } } int depth(treeNode *tree) { /* the function computes the depth of a tree */ if( tree == NULL ) return 0; int ld = depth(tree->left); int rd = depth(tree->right); /* if (ld > rd) return 1+ld; else return 1+rd; */ return 1 + (ld > rd ? ld : rd); } 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 75 Loại bỏ cõy void freeTree(treeNode *tree) { if( tree == NULL ) return; freeTree(tree->left); freeTree(tree->right); free(tree); return; } 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 76 Duyệt cõy nhị phõn • Duyệt cõy nhị phõn là cỏch duyệt cú hệ thống cỏc nỳt của cõy. Tương tự cõy tổng quỏt, ta xột ba thứ tự duyệt cõy nhị phõn: • Thứ tự trước (Preorder) NLR – Thăm nỳt (Visit a node), – Thăm cõy con trỏi theo thứ tự trước (Visit left subtree), – Thăm cõy con phải theo thứ tự trước (Visit right subtree) • Thứ tự giữa (Inorder) LNR – Thăm cõy con trỏi theo thứ tự giữa (Visit left subtree), – Thăm nỳt (Visit a node), – Thăm cõy con phải theo thứ tự giữa (Visit right subtree) • Thứ tự sau (Postorder) LRN – Thăm cõy con trỏi theo thứ tự sau (Visit left subtree), – Thăm cõy con phải theo thứ tự sau (Visit right subtree) – Thăm nỳt (Visit a node), 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 77 Duyệt theo thứ tự trước - NLR Preorder Traversal • Thăm nỳt (Visit the node). • Duyệt cõy con trỏi (Traverse the left subtree). • Duyệt cõy con phải (Traverse the right subtree). void printPreorder(treeNode *tree) { if( tree != NULL ) { printf("%s\n", tree->word); printPreorder(tree->left); printPreorder(tree->right); } } 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 78 Preorder Traversal 2 4 7 5 8103 691 11 2, 4, 7, 1, 9, 3, 6, 5, 10, 8, 11 1/28/2013CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 79 Duyệt theo thứ tự giữa - LNR Inorder Traversal • Duyệt cõy con trỏi (Traverse the left subtree). • Thăm nỳt (Visit the node). • Duyệt cõy con phải (Traverse the right subtree). void printInorder(treeNode *tree) { if( tree != NULL ) { printInorder(tree->left); printf("%s\n", tree->word); printInorder(tree->right); } } 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 80 Inorder Traversal 2 4 7 5 8103 691 11 1, 7, 9, 4, 6, 3, 2, 10, 5, 11, 8 1/28/2013CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 81 Thứ tự giữa thu được bằng phộp chiếu Inorder By Projection a b c d e f g h i j g d h b e i a f j c 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 82 Duyệt theo thứ tự sau - LRN Postorder Traversal • Duyệt cõy con trỏi (Traverse the left subtree). • Duyệt cõy con phải (Traverse the right subtree). • Thăm nỳt (Visit the node). void printPostorder(treeNode *tree) { if( tree != NULL ) { printPostorder(tree->left); printPostorder(tree->right); printf("%s\n", tree->word); } } 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 83 Postorder Traversal 2 4 7 5 8103 691 11 1, 9, 7, 6, 3, 4, 10, 11, 8, 5, 2 1/28/2013CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 84 Vớ dụ: Duyệt cõy nhị phõn • Chỳ ý: Ta cú thể xõy dựng được cõy nhị phõn mà thứ tự trước và thứ tự giữa hoặc thứ tự sau và thứ tự giữa là như nhau; nhưng khụng thể cú cõy nhị phõn mà thứ tự trước và thứ tự sau là như nhau. 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 85 Chương trỡnh minh hoạ /* The program for testing binary tree traversal */ #include #include #include #include #include struct Tnode { char word[20]; struct Tnode * left; struct Tnode *right; }; typedef struct Tnode treeNode; treeNode* makeTreeNode(char *word); treeNode *RandomInsert(treeNode* tree,char *word); void freeTree(treeNode *tree); void printPreorder(treeNode *tree); void printPostorder(treeNode *tree); void printInorder(treeNode *tree); int countNodes(treeNode *tree); int depth(treeNode *tree); 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 86 Chương trỡnh minh hoạ int main() { treeNode *randomTree=NULL; char word[20] = "a"; while( strcmp(word,"~")!=0) { printf("\nEnter item (~ to finish): "); scanf("%s", word); if (strcmp(word,"~")==0) printf("Cham dut nhap thong tin nut... \n"); else randomTree=RandomInsert(randomTree,word); } printf("The tree in preorder:\n"); printPreorder(randomTree); printf("The tree in postorder:\n"); printPostorder(randomTree); printf("The tree in inorder:\n"); printInorder(randomTree); printf("The number of nodes is: %d\n",countNodes(randomTree)); printf("The depth of the tree is: %d\n", depth(randomTree)); freeTree(randomTree); getch(); return 0; } 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 87 Gắn ngẫu nhiờn nỳt mới vào cõy treeNode *RandomInsert(treeNode *tree,char *word){ treeNode *newNode, *p; newNode = makeTreeNode(word); if ( tree == NULL ) return newNode; if ( rand()%2 ==0 ){ p=tree; while (p->left !=NULL) p=p->left; p->left=newNode; printf("Node %s is left child of %s \n",word,(*p).word); } else { p=tree; while (p->right !=NULL) p=p->right; p->right=newNode; printf("Node %s is right child of %s \n",word,(*p).word); } return tree; } 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 88 Chương trỡnh minh hoạ /*********************************************** The program for testing binary tree traversal ************************************************/ #include #include #include #include #include struct Tnode { char word[20]; struct Tnode * left; struct Tnode *right; }; typedef struct Tnode treeNode; treeNode* makeTreeNode(char *word); treeNode *RandomInsert(treeNode* tree,char *word); void freeTree(treeNode *tree); void printPreorder(treeNode *tree); void printPostorder(treeNode *tree); void printInorder(treeNode *tree); int countNodes(treeNode *tree); int depth(treeNode *tree); int main() { treeNode *randomTree=NULL; char word[20] = "a"; while( strcmp(word,"~")!=0) { printf("\nEnter item (~ to finish): "); scanf("%s", word); if ( strcmp(word,"~")==0 ) printf("Cham dut nhap thong tin nut... \n"); else randomTree=RandomInsert(randomTree,word); } printf("The tree in preorder:\n"); printPreorder(randomTree); printf("***************************************************\n"); printf("The tree in postorder:\n"); printPostorder(randomTree); printf("***************************************************\n"); printf("The tree in inorder:\n"); printInorder(randomTree); printf("***************************************************\n"); printf("The number of nodes is: %d\n",countNodes(randomTree)); printf("The depth of the tree is: %d\n", depth(randomTree)); freeTree(randomTree); getch(); return 0; } 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 89 4.3. Cỏc vớ dụ ứng dụng 4.3.1. Cõy biểu thức 4.3.2. Cõy mó Huffman 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 90 4.3.1. Cõy biểu thức An application of binary trees: Binary Expression Trees 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 91 Khỏi niệm Cõy biểu thức là cõy nhị phõn trong đú: 1. Mỗi nỳt lỏ chứa một toỏn hạng 2. Mỗi nỳt trong chứa một phộp toỏn hai ngụi 3. Cỏc cõy con trỏi và phải của nỳt phộp toỏn biểu diễn cỏc biểu thức con (subexpressions) cần được thực hiện trước khi thực hiện phộp toỏn ở gốc của cỏc cõy con. 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 92 Vớ dụ: Cõy nhị phõn 4 mức ‘*’ ‘-’ ‘8’ ‘5’ ‘/’ ‘+’ ‘4’ ‘3’ ‘2’ 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 93 Cỏc mức thể hiện mức độ ưu tiờn • Mức (độ sõu) của cỏc nỳt trờn cõy cho biết trỡnh tự thực hiện chỳng (ta khụng cần sử dụng ngoặc để chỉ ra trỡnh tự). • Phộp toỏn tại mức cao hơn của cõy được thực hiện muộn hơn so với cỏc mức dưới chỳng. • Phộp toỏn ở gốc luụn được thực hiện sau cựng. 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 94 Vớ dụ: Xột Cõy biểu thức Cõy này cú giỏ trị nào? ( 4 + 2 ) * 3 = 18 ‘*’ ‘+’ ‘4’ ‘3’ ‘2’ 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 95 Infix: ( ( 8 - 5 ) * ( ( 4 + 2 ) / 3 ) ) Prefix: * - 8 5 / + 4 2 3 Postfix: 8 5 - 4 2 + 3 / * ‘*’ ‘-’ ‘8’ ‘5’ ‘/’ ‘+’ ‘4’ ‘3’ ‘2’ Sử dụng cõy biểu thức ta cú thể đưa ra biểu thức trong ký phỏp trung tố, tiền tố và hậu tố (infix, prefix, postfix) 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 96 Thứ tự giữa của cõy biểu thức Inorder Of Expression Tree + a b - c d + e f * / Cho ta biểu thức trung tố (thiếu dấu ngoặc)! ea + b * c d / + f- 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 97 Cỏc ký phỏp • Duyệt cõy biểu thức theo thứ tự trước (Preorder) – Cho ta ký phỏp tiền tố (Prefix Notation) • Duyệt cõy biểu thức theo thứ tự giữa (Inorder) – Cho ta ký phỏp trung tố (Infix Notation) • Duyệt cõy biểu thức theo thứ tự sau (Postorder) – Cho ta ký phỏp hậu tố (Postfix Notation) 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 98 Vớ dụ: Infix Notation / + / 1 3 * 6 7 4 1 / 3 + *6 7 / 4 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 99 7 / / 1 + / 3 * 6 4 Vớ dụ: Postfix Notation Cũn gọi là: Reverse Polish Notation 1 3 6 7 * 4 / + 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 100 /+ / 1 3 * 6 7 4 Vớ dụ: Prefix + / 1 3 / * 6 7 4 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 101 4.3. Cỏc vớ dụ ứng dụng 4.3.1. Cõy biểu thức 4.3.2. Cõy mó Huffman 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 102 4.3.3. Mó Huffman An application of binary trees: Huffman Code CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT1/28/2013 103 Mó Huffman • Giả sử cú một văn bản trờn bảng chữ cỏi C. Với mỗi chữ cỏi c  C ta biết tần suất xuất hiện của nú trong văn bản là f(c). Cần tỡm cỏch mó hoỏ văn bản sử dụng ớt bộ nhớ nhất. – Mã hoá với độ dài cố định (fixed length code). Dễ mã hoá cũng như dễ giải mã, nhưng lại đòi hỏi bộ nhớ lớn – Mã phi tiền tố (prefix free code) là cách mã hoá mỗi ký tự c bởi một xâu nhị phân code(c) sao cho mã của một ký tự bất kỳ không là đoạn đầu của bất cứ mã của ký tự nào trong số các ký tự còn lại. Tuy đòi hỏi việc mã hoá và giải mã phức tạp hơn nhưng thông thường tỏ ra đòi hỏi ít bộ nhớ hơn. David A. Huffman 1925-1999 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT1/28/2013 104 Mó hoỏ độ dài cố định • Để mó hoỏ 26 chữ cỏi tiếng Anh bởi mó nhị phõn độ dài cố định, độ dài của xõu tối thiểu là [log 26] =5 bit. • Cỏc xõu từ 11011 đến 11111 khụng sử dụng CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT1/28/2013 105 Cõy mó hoỏ độ dài cố định • Mó hoỏ độ dài cố định là mó phi tiền tố • Giải mó 0011101000  HI • Cỏc nỳt * khụng sử dụng CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT1/28/2013 106 Morse Code • Căn cứ vào thống kờ tần suất của cỏc chữ cỏi trong tiếng Anh • Morse đề xuất cỏch mó hoỏ: CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT1/28/2013 107 Cõy mó hoỏ Morse • Mó hoỏ Morse khụng là phi tiền tố • Giải mó “....-” ??? Chịu chết? • Phải cú dấu phõn biệt cỏc chữ cỏi: “..#..-”  IU • Cõy khụng đầy đủ CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT1/28/2013 108 Mó Huffman • Mỗi mó phi tiền tố cú thể biểu diễn bởi một cõy nhị phõn T mà mỗi lỏ cuả nú tương ứng với một chữ cỏi và cạnh của nú được gỏn cho một trong hai số 0 hoặc 1. • Mó của một chữ cỏi c là 1 dóy nhị phõn gồm cỏc số gỏn cho cỏc cạnh trờn đường đi từ gốc đến lỏ tương ứng với c. CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT1/28/2013 109 Mó Huffman • Bài toỏn: Tỡm cỏch mó hoỏ tối ưu, tức là tỡm cõy nhị phõn T làm tối thiểu hoỏ tổng độ dài cú trọng số trong đú depth(c) là độ dài đường đi từ gốc đến lỏ tương ứng với ký tự c.    Cc cdepthcfTB )()()( CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT1/28/2013 110 Mó Huffman • í tưởng thuật toỏn: • Chữ cỏi cú tần suất nhỏ hơn cần được gỏn cho lỏ cú khoảng cỏch đến gốc là lớn hơn; chữ cỏi cú tần suất xuất hiện lớn hơn cần được gỏn cho nỳt gần gốc hơn CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT1/28/2013 111 Mó Huffman: Thuật toỏn procedure Huffman(C, f); begin n  |C|; Q  C; for i:=1 to n-1 do begin x, y  2 chữ cỏi cú tần suất nhỏ nhất trong Q; (* Thao tỏc 1 *) Tạo nỳt p với hai con x, y; f(p) := f(x) + f(y); Q  Q \ {x, y}  {p} (* Thao tỏc 2 *) end; end; • Mã xây dựng theo thuật toán Huffman thường được gọi là mã Huffman (Huffman Code). • Cú thể cài đặt với thời gian O(n log n) sử dụng priority queue CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT1/28/2013 112 Xây dựng mã Huffman • Tần suất của cỏc ký tự trong văn bản. 125 Freq 93 80 76 72 71 61 55 41 40 E Char T A O I N R H L D 31 27 C U 65S CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT1/28/2013 113 Xây dựng mã Huffman R S N I E H C U 31 27 5571 7361 65 125 40 T D L 41 93 A O 80 76 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT1/28/2013 114 Xây dựng mã Huffman R S N I E H C U 58 D L A O T 31 27 5571 7361 65 125 40 41 9380 76 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT1/28/2013 115 Xây dựng mã Huffman R S N I E H C U 58 D L 81 A O T 31 27 5571 7361 65 125 40 41 9380 76 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT1/28/2013 116 Xây dựng mã Huffman R S N I E H C U 58 113 D L 81 A O T 31 27 5571 7361 65 125 40 41 9380 76 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT1/28/2013 117 Xây dựng mã Huffman R S N I E H C U 58 113126 D L 81 A O T 31 27 5571 7361 65 125 40 41 9380 76 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT1/28/2013 118 Xây dựng mã Huffman R S N I E H C U 58 113144126 D L 81 A O T 31 27 5571 7361 65 125 40 41 9380 76 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT1/28/2013 119 Xây dựng mã Huffman R S N I E H C U 58 113144126 D L 81 156 A O T 31 27 5571 7361 65 125 40 41 9380 76 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT1/28/2013 120 Xây dựng mã Huffman R S N I E H C U 58 113144126 D L 81 156 174 A O T 31 27 5571 7361 65 125 40 41 9380 76 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT1/28/2013 121 Xây dựng mã Huffman R S N I E H C U 58 113144126 238 T D L 81 156 174 A O CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT1/28/2013 122 Xây dựng mã Huffman R S N I E H C U 58 113144126 238270 T D L 81 156 174 A O 31 27 5571 7361 65 125 40 41 9380 76 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT1/28/2013 123 Xây dựng mã Huffman R S N I E H C U 58 113144126 238270 330 T D L 81 156 174 A O 31 27 5571 7361 65 125 40 41 9380 76 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT1/28/2013 124 Xây dựng mã Huffman R S N I E H C U 58 113144126 238270 330 508 T D L 81 156 174 A O 31 27 5571 7361 65 125 40 41 9380 76 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT1/28/2013 125 Xây dựng mã Huffman R S N I E H C U 58 113144126 238270 330 508 838 T D L 81 156 174 A O 31 27 5571 7361 65 125 40 41 9380 76 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT1/28/2013 126 Xây dựng mã Huffman 125 Freq 93 80 76 73 71 61 55 41 40 E Char T A O I N R H L D 31 27 C U 65S 0000 Fixed 0001 0010 0011 0100 0101 0111 1000 1001 1010 1011 1100 0110 110 Huff 011 000 001 1011 1010 1000 1111 0101 0100 11100 11101 1001 838Tổng 303633521/28/2013 127 Mó Huffman: Giải mó procedure Huffman_Decode(B); (* B là xâu mã hóa văn bản theo mã hoá Huffman. *) begin While do begin x  bit tiếp theo trong xâu B; If x = 0 then P  Con trái của P Else P  Con phải của P If (P là nút lá ) then begin end; end end; CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT1/28/2013 128 QUESTIONS? 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁNNGUYỄN ĐƯC NGHĨA - Bộ mụn KHMT 129