Bài giảng Cấu trúc dữ liệu

rear:=Q.rear^.next; Q.rear^.element:=x; Q.rear^.next:=nil; End; Xóa một phần tử trong hàng Thực chất là xoá phần tử nằm ở đầu hàng. Ta chỉ cần cho front trỏ tới vị trí kế tiếp nó trong danh sách. Procedure Remove(var Q:queue); var temp:celltype; Begin if not IsEmpty(Q) then Begin temp:=Q.front; Q.front:=Q.front^.next; dispose(temp); End Else writeln('Lỗi: hàng rỗng'); End; 4. Một số ứng dụng của hàng đợi Hàng đợi là một cấu trúc dữ liệu được dùng khá phổ biến trong thiết kế giải thuật. Bất kỳ nơi nào ta cần quản lí dữ liệu, quá trình... theo kiểu vào trước-ra trước đều có thể ứng dụng hàng đợi. Ví dụ rất dễ thấy là quản lí in trên mạng, nhiều máy tính yêu cầu in đồng thời và ngay cả một máy tính cũng yêu cầu in nhiều lần. Nói chung có nhiều yêu cầu in dữ liệu, nhưng máy in không thể đáp ứng tức thời tất cả các yêu cầu đó nên chương trình quản lí in sẽ thiết lập một hàng đợi để quản lí các yêu cầu. Yêu cầu nào mà chương trình quản lí in nhận trước nó sẽ giải quyết trước. Một ví dụ khác là duyệt cây theo mức được trình bày chi tiết trong chương sau. Các giải thuật duyệt theo chiều rộng một đồ thị có hướng hoặc vô hướng cũng dùng hàng đợi để quản lí các nút đồ thị. Chương 6. Cấu trúc dữ liệu bảng băm (Hash Table) 1. Định nghĩa Bảng băm là một cấu trúc dữ liệu dùng để lưu trữ các phần tử của một tập hợp với các phép toán Insert (chèn một phần tử vào tập hợp), Delete (xoá một phần tử khỏi tập hợp) và Member (tìm phần tử thuộc một tập hợp). Các phần tử của tập hợp được lưu trữ trong bảng băm dựa vào giá trị băm của phần tử và một hàm băm, bảng băm thường cài đặt bằng mảng. Giả sử ta có một mảng gồm B phần tử được đánh số 0..B-1 và một tập hợp A muốn lưu trữ vào trong mảng này. Với mỗi phần tử x єA ta phải dựa vào khoá của nó để suy ra một giá trị số nguyên thuộc khoảng 0..B- 1 là vị trí cất giữ khoá này. Hàm biến đổi giá trị khoá thành một số nguyên được gọi là hàm băm. Giả sử h là một hàm băm, ta có: h: A    ®    0..B-1 x     ®    h(x) Khi đó h(x) là vị trí lưu giữ phần tử x trong mảng. Do vậy khi cần tìm kiếm phần tử x ta chỉ cần tính h(x). Giá trị h(x) gọi là giá trị băm của khoá x Nói chung sẽ có nhiều khoá có cùng giá trị băm. Tức là với hai khoá x,y khác nhau nhưng h(x)=h(y) vậy x,y có cùng một vị trí trong mảng, trường hợp này ta gọi là đụng độ (collision). Như vậy để áp dụng phương pháp băm ta cần chọn hàm h sao cho ít xảy ra đụng độ hay h có thể "rải đều" các khoá vào trong mảng. Hơn nữa ta phải có cách giải quyết khi đụng độ xảy ra. Ví dụ: Hàm h dưới đây biến đổi một chuỗi các ký tự thành số nguyên thuộc đoạn 0..B-1. const B=...; {số nguyên chỉ độ dài bảng băm} type index = 0..B-1; ElementType = string[10] function h(x: ElementType): index var i,sum:integer; begin sum:=0; for i:=1 to length(x) do sum:=sum+ord(x[i]); h:=sum mod B; end; Chẳng hạn với B=11 ta có: h('WINDOW')=10 h('EXCEL')=6 h('FOXPRO')=5 h('QUATTRO')=10 h('VENTURA')=10 2. Bảng băm mở Bảng băm mở lưu trữ các phần tử có cùng giá trị băm trong một danh sách (thường là danh sách liên kết). Giả sử A là một bảng băm, các phần tử được đánh số từ 0.. B-1 và h là hàm băm thì lớp thứ k là một danh sách gồm tất cả các phần tử x sao cho h(x)=k. Danh sách các phần tử có giá trị băm là k được quản lý bởi con trỏ A[k]. Dưới đây là các thủ tục cài đặt từ điển bằng bảng băm mở với giả thiết rằng các phần tử trong từ điển có kiểu ElementType và hàm băm là h. const B= ...; { số nguyên thích hợp chỉ độ dài bảng băm} Type Item=...;{kiểu các phần tử} Cell=^CellType; CellType= record element:ElementType; next:Cell; end; DICTIONARY= array[0..B-1] of Cell; Khởi tạo cấu trúc rỗng Lúc này tất cả các bucket là rỗng nên ta gán tất cả các con trỏ trỏ đến đầu các danh sách trong mỗi bucket là nil. Procedure MAKENULL(var A: DICTIONARY); var i:integer; begin for i:=0 to B-1 do A[i]:=nil; end; Kiểm tra một thành viên trong từ điển được cài bằng bảng băm mở Ðể kiểm tra xem một khoá x nào đó có trong từ điển hay không, ta tính địa chỉ của nó trong bảng băm. Theo cấu trúc của bảng băm thì khoá x sẽ nằm trong danh sách được trỏ bởi A[h(x)], với h(x) là hàm băm. Như vậy để tìm khoá x trước hết ta phải tính h(x) sau đó duyệt danh sách được trỏ bởi A[h(x)]. Giải thuật như sau: Function MEMBER(x:Item; var A:DICTIONARY):Boolean; var p:Cell; found:boolean; begin p:= A[h(x)];{current trỏ tới danh sách thứ h(x)} found:=false; while (pnil) and (not found) do if p^.element=x then found:=true else p:=p^.next; Member:=found; end; Thêm một phần tử vào từ điển được cài bằng bảng băm mở Ðể thêm một phần tử có khoá x vào từ điển ta phải tính h(x). Phần tử có khoá x sẽ được thêm vào danh sách được trỏ bởi A[h(x)]. Vì ta không quan tâm đến thứ tự các phần tử trong mỗi bucket nên ta có thể thêm phần tử mới ngay đầu danh sách này. Giải thuật như sau: procedure INSERT (x:Item; var A:DICTIONARY); var k:integer; OldHeader:cell; begin if not MEMBER(x,A) then begin k:=h(x); OldHeader:=A[k]; {giữ lại con trỏ đầu danh sách } New(A[k]); {cấp phát một ô mới làm đầu danh sách} A[k]^.Element:=x; {gán phần tử vào ô mới} A[k]^.Next:=OldHeader; {trỏ đến danh sách cũ} end; end; Xoá một phần tử trong từ điển được cài bằng bảng băm mở Xoá một phần tử có khoá x trong tự điển bao gồm việc tìm ô chứa khoá và xoá ô này. Phần tử x, nếu có trong tự điển, sẽ nằm ở danh sách được chỉ bởi A[h(x)]. Có hai trường hợp cần phân biệt. Nếu x nằm ngay đầu bucket, sau khi xoá x thì phần tử kế tiếp sau x trong danh sách sẽ trở thành đầu danh sách. Nếu x không nằm ở đầu danh sách thì ta duyệt danh sách này để tìm và xoá x. Trong trường hợp này ta phải định vị con trỏ duyệt tại “ô trước“ ô chứa x để cập nhật lại con trỏ Next của ô này. Giải thuật như sau: procedure DELETE(x:Item; Var A: DICTIONARY); var p,temp: cell; k: integer; done:boolean; begin k:=h(x); if A[k]nil then begin {x nằm ngay đầu danh sách} if A[k]^.Element=x then begin temp:=a[k]; a[k]:=a[k]^.next; dispose(temp); end else begin done:=false; p:=a[k]; temp:=p^.next; while (tempnil) and (not done) do if temp^.element=x then begin p^.next:=temp^.next; dispose(temp); done:=true; end else begin p:=p^.next; temp:=temp^.next; end; end; end; end; 3. Bảng băm đóng Bảng băm đóng lưu giữ các phần tử của tập hợp ngay trong mảng, phần tử có giá trị băm là i được lưu trữ tại vị trí thứ i của mảng. Khi xảy ra đụng độ (hai phần tử có cùng giá trị băm) ta sử dụng chiến lược băm lại. Chiến lược băm lại là chọn tuần tự các vị trí h1,..., hk theo một cách nào đó cho tới khi gặp một vị trí trống để đặt x vào. Dãy h1,...,hk gọi là dãy các phép thử. Một chiến lược đơn giản là băm lại tuyến tính, trong đó dãy các phép thử có dạng : hi(x)=(h(x)+i) mod B Ví dụ, Cho S là tập gồm 4 phần tử {a, b, c, d} và B=8. Các phần tử của S có giá trị băm lần lượt là: h(a)=3, h(b)=0, h(c)=4, h(d)=3. Ta muốn đưa các phần tử này lần lượt vào bảng băm. Khởi đầu bảng băm là rỗng, có thể coi mỗi vị trí chứa một giá trị đặc biệt Empty, Empty khác với tất cả các phần tử của tập hợp. Ta đặt a vào vị trí 3, b vào vị trí 0, c vào vị trí 4. Xét phần tử d, d có h(d)=3 nhưng vị trí 3 đã bị a chiếm ta tìm vị trí h1(x)= (h(x)+1) mod B = 4, vị trí này cũng đã bị c chiếm, tiếp tục tìm sang vị trí h2 (x)= (h(x)+2) mod B= 5 đây là một vị trí rỗng ta đặt d vào. Trong bảng băm đóng, phép kiểm tra một thành viên (thủ tục MEMBER (x,A)) phải xét dãy các vị trí h(x), h1(x), h2(x),... cho đến khi tìm thấy x hoặc tìm thấy một vị trí trống. Nếu bảng băm chưa bị xoá một phần tử nào thì khi gặp vị trí trống đầu tiên ta có thể kết luận được phần tử x không có trong bảng băm. Tuy nhiên, nếu thực hiện phép xoá thì chúng ta qui ước rằng phần tử bị xóa sẽ được thay bởi một giá trị đặc biệt, gọi là Deleted, giá trị Deleted không bằng với bất kỳ một phần tử nào trong tập hợp đang xét vào nó cũng phải khác giá trị Empty. Ví dụ - Tìm phần tử e trong bảng băm trên, giả sử h(e)=4. Chúng ta tìm kiếm e tại các vị trí 4,5,6. Vị trí 6 là chứa Empty, vậy không có e trong bảng băm. - Tìm d, vì h(d)=3 ta khởi đầu tại vị trí này và duyệt qua các vị trí 4,5. Phần tử d được tìm thấy tại vị trí 5. Khai báo cấu trúc dữ liệu Ðể dễ dàng minh hoạ các giá trị Deleted và Empty, giả sử rằng ta cần cài đặt từ điển gồm các chuỗi 10 kí tự. Ta có thể qui ước: Empty là chuỗi 10 dấu + và Deleted là chuỗi 10 dấu *. Const Empty ='++++++++++'; Deleted='**********''; B=19 ; {giá trị thích hợp cho độ dài bảng băm} Type Item= string[10]; DICTIONARY= array[0..B-1] of Item; procedure MAKENULL(var A:DICTIONARY); var i:integer; begin for i:=0 to B-1 do A[i]:=Empty; end; function LOCATE(x:Item; A:DICTIONARY):integer; {duyệt từ điển từ vị trí H(x) cho đến khi tìm thấy x hoặc tìm thấy Empty đầu tiên. Nó trả về chỉ số của mảng tại chổ dừng } var init,i :integer; begin init:=h(x); i:=0; while (ix) and (A[(init+i) mod B] Empty) do i:=i+1; LOCATE:=(init+i) MOD B; end; function LOCATE1(x:Item; A:DICTIONARY):integer; {duyệt từ điển từ vị trí H(x) cho đến khi tìm thấy x hoặc tìm thấy Empty hay Deleted đầu tiên. Nó trả về chỉ số của mảng tại chỗ dừng } var init,i :integer; begin init:=h(x); i:=0; while (ix) and ( a[(init+i) mod B] Empty) and (a[(init+i) mod B] Deleted) do i:=i+1; LOCATE1:=(init+i) MOD B ; end; function MEMBER(x:Item; A: DICTIONARY):Boolean; begin MEMBER:=(A[locate(x,A)]=x); end; procedure INSERT(x:Item; Var A:DICTIONARY); var k:integer; begin if A[locate(x,A)]x then begin {chưa có x trong bảng} k:= locate1(x,A); if (A[k]=Empty) or (A[k]=Deleted) then A[k]:=x else Writeln('Lỗi: bảng băm đầy'); end; end; procedure DELETE(x:Item; Var A:DICTIONARY); var k:integer; begin k:=locate(x,A); if a[k]=x then a[k]:=deleted; end; 4. Phân tích tính hiệu quả của bảng băm Giả sử bảng băm có B vị trí và có N phần tử được lưu trong bảng băm thì trung bình mỗi danh sách có N/B phần tử. Khi đó các phép toán INSERT, DELETE và MEMBER mất khoảng 1+N/B bước. Hằng số 1 biểu diễn cho thời gian tìm kiếm danh sách còn N/B là thời gian duyệt trên danh sách. Nếu chọn B bằng N thì thời gian này là hằng số. Như vậy thời gian để thêm, xoá, hoặc kiểm tra thành viên trong trường hợp các danh sách có độ dài bằng nhau là một hằng số độc lập với N. Sự phân tích ở trên dựa vào giả thiết các danh sách có độ dài như nhau, nghĩa là hàm băm "rải đều" các phần tử vào bảng băm. Như vậy, khi cài đặt ta chọn hàm băm có sự rải đều các phần tử vào bảng băm là tốt nhất. 5. Các phương pháp thiết kế hàm băm. Việc thiết kế hàm băm dựa trên những tính toán số học để cho các kết quả ngẫu nhiên, hàm băm càng ngẫu nhiên thì nó càng có khả năng rải đều các phần tử vào bảng băm. Mặt khác hàm băm còn phải đơn giản, vì nếu một hàm băm quá phức tạp thì thời gian phải trả cho hàm băm này để băm một khoá là lớn, đều này ảnh hưởng lớn đến hiệu quả chung của phương pháp. Dưới đây là một số phương pháp thiết kế hàm băm thường gặp là: 5.1. Phương pháp chia "Lấy phần dư của giá trị khoá khi chia cho số vị trí lưu trữ trong bảng băm" . Tức là hàm băm có dạng: H(x)= x mod B Phương pháp này rõ ràng là rất đơn giản nhưng nó có thể không cho kết quả ngẫu nhiên lắm. Chẳng hạn B=1000 thì H(x) chỉ phụ thuộc vào ba số cuối cùng của khoá mà không phụ thuộc vào các số đứng trước. Kết quả có thể ngẫu nhiên hơn nếu B là một số nguyên tố. 5.2. Phương pháp nhân "Lấy khoá nhân với chính nó rồi chọn một số chữ số ở giữa làm kết quả của hàm băm". Ví dụ x x2 h(x) gồm 3 số ở giữa 5402 29181604 181 hoặc 816 0367 00134689 134 346 1246 01552516 552 525 2983 08898289 898 982 Vì các chữ số ở giữa phụ thuộc vào tất cả các chữ số có mặt trong khoá do vậy các khoá có khác nhau đôi chút thì hàm băm cho kết quả khác nhau. 5.3. Phương pháp phân đoạn Ðối với các khoá dài và kích thước thay đổi người ta thường dùng phương pháp phân đoạn, tức là phân khoá ra thành nhiều đoạn có kích thước bằng nhau từ một đầu (trừ đoạn tại đầu cuối ), nói chung mỗi đoạn có độ dài bằng độ dài của kết quả hàm băm. Phân đoạn có thể là tách hoặc gấp: a. Tách: tách khóa ra từng đoạn rồi xếp các đoạn thành hàng được canh thẳng một đầu rồi có thể cộng chúng lại rồi áp dụng phương pháp chia để có kết quả băm. ví dụ: khoá 17046329 tách thành 329 046 017 cộng lại ta được 392. 392 mod 1000 = 392 là kết quả băm khoá đã cho. b. Gấp: gấp khoá lại theo một cách nào đó, có thể tương tự như gấp giấy, các chữ số cùng nằm tại một vị trí sau khi gấp dược xếp lại thẳng hàng với nhau rồi có thể cộng lại rồi áp dụng phương pháp chia (mod) để cho kết quả băm Ví dụ: khoá 17046329 gấp hai biên vào ta có 932 046 710 Cộng lại ta có 1679. 1679 mod 1000= 679 là kết quả băm khoá đã cho. Chương 7. Cấu trúc dữ liệu cây 1. Các định nghĩa Cây là một tập hợp các phần tử gọi là nút (node) trong đó có một nút được gọi là nút gốc (root). Trên tập hợp các nút này tồn tại một quan hệ, gọi là mối quan hệ cha - con, xác định hệ thống cấu trúc trên các nút. Mỗi nút, trừ nút gốc, có duy nhất một nút cha. Một nút có thể có nhiều nút con hoặc không có nút con nào. Mỗi nút biểu diễn một phần tử trong tập hợp đang xét và nó có thể có một kiểu nào đó bất kỳ, thường ta biểu diễn nút bằng một kí tự, một chuỗi hoặc một số ghi trong vòng tròn. Mối quan hệ cha con được biễu diễn theo qui ước nút cha ở dòng trên nút con ở dòng dưới và được nối bởi một đoạn thẳng. Một cách hình thức ta có thể định nghĩa cây một cách đệ qui như sau: Cây Một nút đơn độc là một cây. Nút này cũng chính là nút gốc của cây. Giả sử ta có n là một nút đơn độc và k cây T1,.., Tk với các nút gốc tương ứng là n1,.., nk thì có thể xây dựng một cây mới bằng cách cho nút n là cha của các nút n1,.., nk. Cây mới này có nút gốc là nút n và các cây T1,.., Tk được gọi là các cây con. Tập rỗng cũng được coi là một cây và gọi là cây rỗng kí hiệu ^. Ví dụ: xét mục lục của một quyển sách. Mục lục này có thể xem là một cây Nút gốc là sách, nó có ba cây con có gốc là C1, C2, C3. Cây con thứ 3 có gốc C3 là một nút đơn độc trong khi đó hai cây con kia (gốc C1 và C2) có các nút con. Đường đi: đường đi là một dãy các nút n1, n2 .., nk, trong đó ni là nút cha của nút ni+1, với i = 1..k-1. Ðộ dài đường đi bằng số đỉnh trên đường đi đó trừ 1. Độ dài đường đi từ một nút đến chính nó bằng không. Sach, C1, 1.1 là một đường đi trong cây mục lục ở trên Bậc (Cấp): bậc của một nút là số con trực tiếp của nút đó. Nút có bậc bằng 0 gọi là lá hay nút tận cùng, nút khác nút lá gọi là nút nhánh. Bậc của cây là bậc của nút cao nhất trong cây. Mức: mức của một nút được định nghĩa như sau: mức của nút gốc bằng 1. Nếu đỉnh cha có mức là i thì đỉnh con có mức là (i + 1). Tiền thân và hậu thế Nếu có đường đi từ nút a đến nút b thì a được gọi là tiền thân của b, còn b gọi là hậu thế của nút a. Một nút vừa là tiền thân và là hậu thế của chính nó. Tiền thân hoặc hậu thế của một nút khác với chính nó gọi là tiền thân và hậu thế thực sự. Trong một cây, nút gốc không có tiền thân thực sự, nút lá không có hậu thế thực sự. Nút khác nút lá gọi là nút trung gian. Cây con của một cây là một nút cùng với tất cả các hậu thế của nó. Chiều cao của một nút là độ dài đường đi lớn nhất từ nút đó tới lá. Chiều cao của cây là chiều cao của nút gốc. Ðộ sâu của một nút là độ dài đường đi từ nút gốc đến nút đó. Các nút có cùng một độ sâu i ta gọi là các nút có cùng một mức i. Theo định nghĩa này thì nút gốc ở mức 0, các nút con của nút gốc ở mức 1. Ví dụ: với cây mục lục ở trên thì nút C2 có chiều cao 2. Cây có chiều cao 3. nút C3 có chiều cao 0. Nút 2.1 có độ sâu 2. Các nút C1, C2, C3 cùng mức 1. Cây có thứ tự Cây có phân biệt các nút được gọi là cây có thứ tự, thứ tự của cây được quy ước từ trái qua phải. Như vậy, nếu kể thứ tự thì hai cây sau là hai cây khác nhau: Khi ta không phân biệt thứ tự các nút thì cây không có thứ tự. Các nút con cùng một nút cha gọi là các nút anh em (siblings). Nếu a, b là hai nút anh em và a bên trái b thì các hậu thế của a là "bên trái" mọi hậu thế của b. Các phép toán trên cây (1). Hàm PARENT(n,T) cho nút cha của nút n trên cây T, nếu n là nút gốc thì hàm cho giá trị NULL. (2). Hàm LEFTMOST_CHILD(n,T) cho nút con trái nhất của nút n trên cây T, nếu n là lá thì hàm cho giá trị NULL. (3). Hàm RIGHT_SIBLING(n,T) cho nút anh em ruột phải nút n trên cây T, nếu n không có anh em ruột phải thì hàm cho giá trị NULL. (4). Hàm LABEL_NODE(n,T) cho nhãn tại nút n của cây T. (5). ROOT(T) trả ra nút gốc của cây T. Nếu Cây T rỗng thì hàm trả về NULL. (6).CREATEi(v,T1,T2,..,Ti),với i=0..n, thủ tục tạo cây mới có nút gốc là n được gán nhãn v và có i cây con T1,..,Ti. Nếu n= 0 thì thủ tục tạo cây mới chỉ gồm có 1 nút đơn độc là n có nhãn v. Chẳng hạn, giả sử ta có hai cây con T1 và T2, ta muốn thiết lập cây mới với nút gốc có nhãn là v thì lời gọi thủ tục sẽ là CREATE2(v,T1,T2). 3. Duyệt cây Duyệt cây là một qui tắc cho phép đi qua lần lượt tất cả các nút của cây mỗi nút đúng một lần, danh sách các nút được liệt kê (tên nút hoặc giá trị chứa bên trong nút) theo thứ tự đi qua gọi là danh sách duyệt cây. Đối với kiểu dữ liệu cây người ta quan tâm đến 3 cách duyệt cây sau: (1). Duyệt cây theo thứ tự trước (preorder), hay duyệt tiền tự. (2). Duyệt cây theo thứ tự giữa (inorder), hạy duyệt trung tự. (3). Duyệt cây theo thứ tự sau (posorder), hạy duyệt hậu tự. Phép duyệt cây tổng quát được định nghĩa đệ quy như sau: (1). Cây rỗng thì danh sách duyệt cây là rỗng và nó được coi là biểu thức duyệt tiền tự, trung tự và hậu tự của cây. (2). Cây chỉ có một nút thì danh sách duyệt cây gồm chỉ một nút đó và nó được coi là biểu thức duyệt tiền tự, trung tự, hậu tự của cây. (3). Giả sử cây T có nút gốc là n và có các cây con là T1,..,Tn thì: (3.1). Biểu thức duyệt cây theo thứ tự trước của cây T là liệt kê nút n kế tiếp là biểu thức duyệt cây theo thứ tự trước của các cây T1, T2, .., Tn theo thứ tự đó. (3.2). Biểu thức duyệt cây theo thứ tự giữa của cây T là biểu thức duyệt cây theo thứ tự giữa của cây T1 kế tiếp là nút n rồi đến biểu thức duyệt trung tự của các cây T2,.., Tn theo thứ tự đó. (3.3). Biểu thức duyệt cây theo thứ tự sau của cây T là biểu thức duyệt cây theo thứ tự sau của các cây T1, T2,.., Tn theo thứ tự đó rồi đến nút n. Ví dụ, với cây được cho như trong hình vẽ Biểu thức duyệt cây tiền tự là: A B C D E F H K L Biểu thức duyệt cây trung tự là: C B E D F A K H L Biểu thức duyệt cây hậu tự là: C E F D B K L H A Thuật toán duyệt cây có thể được đinh nghĩa như sau: {Duyệt cây theo thứ tự trước} Procedure PREORDER(n:node); Var a:node; begin If n Null then Begin Visit(n); a:= LeftMost_Child(n); While (aNull) do Begin Preoder(a); a:= Right_Sibling(a); End; End; end; {Duyệt cây theo thứ tự giữa} Procedure Inoder(n:node); Var a:node; begin If n Null then Begin a:= LeftMost_Child(n); Inoder(a); Visit(n); a:= Right_Sibling(a); While (aNull) do Begin Inoder(a); a:= Right_Sibling(a); End; End; end; {Duyệt cây theo thứ tự sau} Procedure Postoder(n:node); Var a:node; begin If n Null then Begin a:= LeftMost_Child(n); While (aNull) do Begin PostOder(a); a:= Right_Sibling(a); End; Visit(n); End; end; Duyệt cây theo chiều rộng Giả sử ta đang ở một nút nào đó trên cây, thăm đỉnh đó và đi theo chiều ngang sang bên phải để thăm các em liền kề của đỉnh đó. Nếu x là đỉnh ngoài cùng bên phải, ta đi xuống mức dưới để thăm đỉnh ngoài cùng bên trái rồi lại tiếp tục đi theo chiều ngang sang bên phải. Thuật toán: B1. - Ban đầu các đỉnh được đánh dấu là chưa thăm, trừ đỉnh gốc. - Dùng một hàng đợi để chứa các đỉnh đã được thăm. Ban đầu hàng đợi chỉ chứa một đỉnh là gốc. B2. Lặp lại các bước sau cho đến khi hàng đợi rỗng: - Lấy một đỉnh v ra khỏi hàng đợi. - Thăm các đỉnh con của v theo thứ tự từ trái qua phải, với mỗi đỉnh u là con của v ta thực hiện: + Đánh dấu đỉnh u đã thăm. + Đưa u vào hàng đợi. Thủ tục duyệt cây theo chiều rộng được viết như sau: { Hàm tìm cây con bên phải của nút n} Procedure BFS(n:node):node; var a:node; Q:Queue ; Begin MakeNull(Q); Visit(a); Add(a,Q); While (Not IsEmpty(Q))do Begin a:= Front(Q); Remove(Q); a:= LeftMost_Child(a); While(aNull) do Begin Visit(a); Add(a,Q); a:=Right_Sibling(a); End; End; End; 4. Cài đặt cây 4.1. Một cách cài đặt bằng mảng a. Mô tả Giả sử cây T có n đỉnh, ta đánh số các đỉnh của T từ trên xuống dưới và từ trái qua phải bắt đầu từ gốc, đỉnh gốc được đánh số 1. Sử dụng mảng một chiều A để lưu trữ các đỉnh của cây theo quy tắc A[i] = j nếu đỉnh j là cha của đỉnh i. Nếu i là đỉnh gốc ta gán A[i] = 0; Ví dụ: cho cây T như hình vẽ Mảng biểu diễn cây có dạng sau: b. Khai báo cấu trúc dữ liệu Const Max=...; {độ dài của mảng} type node=integer; {kiểu của một nút, tree= array[1..max] of node; var maxnode:integer; { số nút đang có trên cây } T:Tree; c. Cài đặt các phép toán Các phép toán được cài đặt như sau: { Tìm cha của một nút} Function Parent(n:node;T:Tree) :Node ; Begin Parent:=T[n]; End ; { Hàm tìm cây con bên trái nhất của nút n} Function LeftMost_Child(n:node;T:Tree):Node Var i:Integer; Begin For i:=1 to MaxNode do If T[i] = n then Begin LeftMost_Child:=i; Exit; End; LeftMost_Child:=0; End; { Hàm tìm cây con bên phải của nút n} function RIGHT_SIBLING(n:node;T:tree):node; var i,p:node; begin p:=Parent(n,T); For i:=n+1 to MaxNode do if T[i]:=p then begin RIGHT_SIBLING:=i; Exit; End; RIGHT_SIBLING:=0; end; 4.2. Biểu diễn cây bằng danh sách các con a. Mô tả Ta biết rằng mỗi đỉnh trong cây gồm một danh sách các đỉnh con, vì số các đỉnh con của một đỉnh là không biết trước cho nên danh sách đỉnh con của một đỉnh sẽ được cài đặt bằng một danh sách liên kết. Dùng một mảng H gồm các con trỏ để quản lý danh sách các đỉnh con của một đỉnh với H[i] là một con trỏ chỉ đến danh sách các đỉnh con của đỉnh thứ i. Nếu đỉnh j không có đỉnh con thì H[j] = Nil; Ví dụ, với cây cho bởi hình vẽ dưới đây Có thể biểu diễn bằng danh sách các đỉnh con như sau: b. Khai báo cấu trúc dữ liệu Type List = ... {kiểu danh sách liên kết} Tree= record H: array[1..maxlength] of List; root:node; maxnode: integer; end; c. Cài đặt các phép toán { Hàm tìm cây con bên trái nhất của nút n} procedure LEFTMOST_CHILD(n:node;T:tree):node; var L:List; begin L:=T.H[n]; if not IsEMPTY(L) then LEFTMOST_CHILD:=RETRIEVE(FIRST(L),L) else LEFTMOST_CHILD:=NULL; end; Có thể nhận xét rằng các hàm đòi hỏi thông tin về các con làm việc rất thuận lợi, nhưng hàm PARENT lại không làm việc tốt. Chẳng hạn tìm nút cha của nút 8 đòi hỏi ta phải duyệt tất cả các danh sách chứa các nút con. 4.3. Biểu diễn con trái nhất - em ruột phải Các cấu trúc đã dùng để mô tả cây ở trên có một số nhược điểm, nó không trợ giúp phép tạo một cây lớn từ các cây nhỏ hơn, nghĩa là ta khó có thể cài đặt phép toán CREATEi bởi vì mỗi cây con đều có một mảng chứa các header riêng. Chẳng hạn CREATE2(v,T1,T2) chúng ta phải chép hai cây T1, T2 vào mảng thứ ba rồi thêm một nút n có nhãn v và hai nút con là gốc của T1 và T2. Vì vậy nếu chúng ta muốn thiết lập một cấu trúc dữ liệu trợ giúp tốt cho phép toán này thì tất cả các nút của các cây con phải ở trong cùng một vùng (một mảng). a. Mô tả Trong cách cài đặt này mỗi đỉnh trong cây được đặc trưng bởi 4 tham số: LABELS, PARENT, LEFTMOST_CHILD, RIGHT_SIBLING. Trong đó LABELS giữ nhãn của nút, LEFTMOST_CHILD là một con trỏ chỉ đến con trái nhất của nút, còn RIGHT_SIBLING là con trỏ chỉ đến nút anh ruột phải, PARENT là con trỏ chỉ đến đỉnh cha. Dùng một mảng để chứa toàn bộ đỉnh của tất cả các cây. b. khai báo cấu trúc dữ liệu Const maxnodes=....; {độ dài của mảng} var CELLSPACE: array[1..maxnodes] of record LABELS: LabelType; LEFTMOST_CHILD: integer; RIGHT_SIBLING:integer; PARENT: integer; end; Các nút trống trong mảng được quản lý bởi một danh sách liên kết và được quản lý bởi một biến Availlable chỉ đến đầu danh sách. Ở đây mỗi ô chứa 3 con nháy nên ta chỉ cần chọn 1 để trỏ đến ô kế tiếp trong danh sách, chẳng hạn ta chọn con nháy Right_sibling. Ví dụ {Thủ tục CREATE2 tạo cây mới từ hai cây con} function CREATE2(v:LabelType; T1,T2: integer):integer; {T1, T2 là hai con nháy trỏ tới hai nút gốc của hai cây con, Hàm trả ra con nháy trỏ tới nút gốc mới} var temp:integer; begin {lấy ô đầu danh sách available để tạo một nút mới trên cây} temp:=AVAILABLE; {available là một biến toàn cục} AVAILABLE:= CellSpace[AVAILABLE].right_sibling; {cập nhật các giá trị cho nút mới} CellSpace[temp].LeftMost_child:=T1; CellSpace[temp].Labels:=v; CellSpace[temp].Right_sibling:=0; CellSpace[T1].Right_sibling:=T2; { cập nhật lại parent cho T1 và T2} CellSpace[T1].Parent := temp; CellSpace[T2].Parent := temp; {trả ra giá trị nút gốc của cây mới} CREATE2:=temp; end; 4.4. Cài đặt bằng con trỏ Hoàn toàn tương tự như cài đặt ở trên nhưng các con nháy Leftmost_child, Right_sibling và Parent được thay bằng các con trỏ. Ta có khai báo cài đặt như sau: Node = ^CELL; CELL = record value: LabelType; leftmost_child,right_sibling: node; parent: node; end; Với cấu