text:
Duyệt cây
Trong khoa học máy tính, duyệt cây là việc lần lượt viếng thăm các đỉnh của cây theo một thứ tự nào đó. Các cây nói trong bài này là cây có gốc.
Dưới đây trình bày một số thuật toán duyệt cây thông dụng.
Mục lục
- 1 Duyệt cây nhị phân
- 2 Ví dụ
- 3 Duyệt cây tổng quát
- 4 Duyệt theo mức
- 5 Giả mã
- 6 Cây nhị phân tương đương
- 7 Tham khảo
- 8 Liên kết ngoài
Duyệt cây nhị phân[sửa | sửa mã nguồn]
Khi xét một cây nhị phân, mỗi đỉnh cùng với các đỉnh đứng sau nó là gốc của một cây con. Ta xét một đỉnh A là đỉnh trong của cây nhị phân. Theo thứ tự người ta xem xét thứ tự thăm đỉnh A so với việc thăm hai con của nó là thăm A trước rồi 2 con sau, thăm A xen giữa việc thăm hai con, thăm A sau thi thăm hai con:
- A, con trái, con phải
- Con trái, A, con phải
- Con trái, con phải, A
Tất nhiên nút không có con nào thì việc thăm con không diễn ra. Còn nếu con L hoặc con R của A lại là gốc của một cây con, thì việc thăm thay bằng việc duyệt cây con có gốc tại đó.
Từ đó có các phương pháp duyệt tiền thứ tự, trung thứ tự, hậu thứ tự đối với cây nhị phân có gốc tại đỉnh A như sau
Duyệt tiền thứ tự cây con gốc A[sửa | sửa mã nguồn]
- Nếu Cây là rỗng Return
- Thăm A
- Duyệt tiền thứ tự cây con gốc L
- Duyệt tiền thứ tự cây con gốc R
Duyệt trung thứ tự cây con gốc A[sửa | sửa mã nguồn]
- Nếu Cây là rỗng Return
- Duyệt trung thứ tự cây con gốc L
- Thăm A
- Duyệt trung thứ tự cây con gốc R
Duyệt hậu thứ tự cây con gốc A[sửa | sửa mã nguồn]
- Nếu Cây là rỗng Return
- Duyệt hậu thứ tự cây con gốc L
- Duyệt hậu thứ tự cây con gốc R
- Thăm A
Ví dụ[sửa | sửa mã nguồn]
Giả sử có cây nhị phân sau
A / \ B C / \ / \ D E F G
- Duyệt tiền thứ tự với cây này diễn ra tuần tự như sau
- Thăm A, Duyệt cây gốc B, Duyệt cây gốc C
- Thăm A, Thăm B, Thăm D, Thăm E, Thăm C, Thăm F, Thăm G
- Duyệt trung thứ tự với cây này diễn ra tuần tự như sau
- Duyệt cây gốc B, Thăm A, Duyệt cây gốc C
- Thăm D, Thăm B, Thăm E, Thăm A, Thăm F, Thăm C, Thăm G
- Duyệt hậu thứ tự với cây này diễn ra tuần tự như sau
- Duyệt cây gốc B, Duyệt cây gốc C, Thăm A
- Thăm D, Thăm E, Thăm B, Thăm F, Thăm G, Thăm C, Thăm A
Duyệt cây tổng quát[sửa | sửa mã nguồn]
Nếu tại gốc A của cây có các con từ trái sang phải là thì quá trình duyệt tiền thứ tự, trung và hậu thứ tự như sau
Duyệt tiền thứ tự[sửa | sửa mã nguồn]
- Thăm A
- Lần lượt duyệt các cây con gốc
Duyệt trung thứ tự[sửa | sửa mã nguồn]
- Duyệt cây con gốc
- Thăm A
- Lần lượt duyệt các cây con gốc
Duyệt hậu thứ tự[sửa | sửa mã nguồn]
- Lần lượt duyệt các cây con gốc
- Thăm A
Tuy nhiên người ta ít xem xét việc duyệt trung thứ tự của cây tổng quát
Duyệt theo mức[sửa | sửa mã nguồn]
Một phương pháp duyệt cây khác là duyệt theo mức. Bắt đầu duyệt từ gốc (đỉnh mức 0), rồi duyệt các con của gốc từ trái sang phải (các đỉnh mức 1), tiếp đến là các đỉnh mức 2,...
Giả mã[sửa | sửa mã nguồn]
Giả sử có một cây nhị phân mà cấu trúc mỗi nút của nó chứa một giá trị
value và các tham chiếu
left và
right trỏ tới hai con của nút đó. Ta có thể viết các hàm sau:
Duyệt tiền thứ tự[sửa | sửa mã nguồn]
(pre-order (prefix) traversal)
visit(node) print node.value if node.left != null then visit(node.left) if node.right != null then visit(node.right)
Duyệt hậu thứ tự[sửa | sửa mã nguồn]
(post-order (postfix) traversal)
visit(node) if node.left != null then visit(node.left) if node.right != null then visit(node.right) print node.value
Duyệt trung thứ tự[sửa | sửa mã nguồn]
(in-order (infix) traversal)
visit(node) if node.left != null then visit(node.left) print node.value if node.right != null then visit(node.right)
Cây nhị phân tương đương[sửa | sửa mã nguồn]
Lưu trữ cấu trúc cây nhị phân[sửa | sửa mã nguồn]
Để biểu diễn cây nhị phân ta dùng cấu trúc Nút (Node). Mỗi Nút là một đỉnh của cây, gồm ba trường, một trường chứa thông tin về nút đó. Hai trường và trỏ tới các nút con của đỉnh đó. Ngoài ra còn một con trỏ là trỏ tới nút gốc.
Cây nhị phân ở trong bài có thể biểu diễn như sau:
Root=A A.Value="A",A.Left=B;A.Right=C B.Value="B",B.Left=D;B.Right=E C.Value="C",C.Left=F;C.Right=G D.Value="D",D.Left=Null;D.Right=Null E.Value="E",E.Left=Null;E.Right=Null F.Value="F",F.Left=Null;F.Right=Null G.Value="G",G.Left=Null;G.Right=Null
Chú ý: Phân biệt kí hiệu A, B,... chỉ nút và "A","B",... chỉ giá trị nút
Lưu trữ cấu trúc cây tổng quát[sửa | sửa mã nguồn]
Khi biểu diễn cấu trúc cây tổng quát, vì mỗi nút có thể có nhiều con, số con có thể khác nhau, nên ta không dùng cho mỗi nút con một liên kết đến nút cha mà với mỗi nút vẫn chỉ dành hai liên kết, một liên kết (trường ) trỏ đến nút con đầu bên trái của nó, một liên kết (trường )trỏ đến nút cùng cha kề bên phải nó. Nếu coi liên kết trường như liên kết , liên kết như liên kết ta có một cây nhị phân tương đương với cây tổng quát.
Ví dụ[sửa | sửa mã nguồn]
- Cây tổng quát
A / | \ B C D / \ | E F G
- Cây nhị phân tương đương
A / B / \ E C \ \ F D / G
- Lưu trữ của cây tổng quát như sau
Root=A A.Value="A",A.Child=B,A.Next=Null B.Value="B",B.Child=E,B.Next=C C.Value="C",C.Child=Null,C.Next=D D.Value="D",D.Child=G,D.Next=Null E.Value="E",E.Null,E.Next=F F.Value="F",F.Child=Null,F.Next=Null G.Value="G",D.Child=Null,G.Next=Null
Tham khảo[sửa | sửa mã nguồn]
Liên kết ngoài[sửa | sửa mã nguồn]
Tiếng Anh:
- The Adjacency List Model for Processing Trees with SQL
- Storing Hierarchical Data in a Database with traversal examples in PHP
- Managing Hierarchical Data in MySQL

markdown:
# Duyệt cây
Trong
[khoa học máy tính](/wiki/Khoa_h%E1%BB%8Dc_m%C3%A1y_t%C3%ADnh), **duyệt cây** là việc lần lượt viếng thăm các [đỉnh](/wiki/%C4%90%E1%BB%93_th%E1%BB%8B_(l%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%93_th%E1%BB%8B)) của [cây](/wiki/C%C3%A2y_(l%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%93_th%E1%BB%8B)) theo một thứ tự nào đó. Các [cây](/wiki/C%C3%A2y_(l%C3%BD_thuy%E1%BA%BFt_%C4%91%E1%BB%93_th%E1%BB%8B)) nói trong bài này là [cây có gốc](/w/index.php?title=C%C3%A2y_c%C3%B3_g%E1%BB%91c&action=edit&redlink=1).
Dưới đây trình bày một số thuật toán duyệt cây thông dụng.
## Mục lục
[1 Duyệt cây nhị phân](#Duy.E1.BB.87t_c.C3.A2y_nh.E1.BB.8B_ph.C3.A2n) [2 Ví dụ](#V.C3.AD_d.E1.BB.A5) [3 Duyệt cây tổng quát](#Duy.E1.BB.87t_c.C3.A2y_t.E1.BB.95ng_qu.C3.A1t) [4 Duyệt theo mức](#Duy.E1.BB.87t_theo_m.E1.BB.A9c) [5 Giả mã](#Gi.E1.BA.A3_m.C3.A3) [6 Cây nhị phân tương đương](#C.C3.A2y_nh.E1.BB.8B_ph.C3.A2n_t.C6.B0.C6.A1ng_.C4.91.C6.B0.C6.A1ng) [7 Tham khảo](#Tham_kh.E1.BA.A3o) [8 Liên kết ngoài](#Li.C3.AAn_k.E1.BA.BFt_ngo.C3.A0i)
## Duyệt cây nhị phân[
[sửa](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&veaction=edit&vesection=1) | [sửa mã nguồn](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&action=edit§ion=1)]
Khi xét một cây nhị phân, mỗi đỉnh cùng với các đỉnh đứng sau nó là gốc của một cây con. Ta xét một đỉnh A là đỉnh trong của cây nhị phân. Theo thứ tự người ta xem xét thứ tự thăm đỉnh A so với việc thăm hai con của nó là thăm A trước rồi 2 con sau, thăm A xen giữa việc thăm hai con, thăm A sau thi thăm hai con:
- A, con trái, con phải
- Con trái, A, con phải
- Con trái, con phải, A
Tất nhiên nút không có con nào thì việc thăm con không diễn ra. Còn nếu con L hoặc con R của A lại là gốc của một cây con, thì việc thăm thay bằng việc duyệt cây con có gốc tại đó.
Từ đó có các phương pháp duyệt tiền thứ tự, trung thứ tự, hậu thứ tự đối với cây nhị phân có gốc tại đỉnh A như sau
### Duyệt tiền thứ tự cây con gốc A[
[sửa](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&veaction=edit&vesection=2) | [sửa mã nguồn](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&action=edit§ion=2)]
- Nếu Cây là rỗng Return
- Thăm A
- Duyệt tiền thứ tự cây con gốc L
- Duyệt tiền thứ tự cây con gốc R
### Duyệt trung thứ tự cây con gốc A[
[sửa](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&veaction=edit&vesection=3) | [sửa mã nguồn](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&action=edit§ion=3)]
- Nếu Cây là rỗng Return
- Duyệt trung thứ tự cây con gốc L
- Thăm A
- Duyệt trung thứ tự cây con gốc R
### Duyệt hậu thứ tự cây con gốc A[
[sửa](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&veaction=edit&vesection=4) | [sửa mã nguồn](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&action=edit§ion=4)]
- Nếu Cây là rỗng Return
- Duyệt hậu thứ tự cây con gốc L
- Duyệt hậu thứ tự cây con gốc R
- Thăm A
## Ví dụ[
[sửa](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&veaction=edit&vesection=5) | [sửa mã nguồn](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&action=edit§ion=5)]
Giả sử có cây nhị phân sau
A / \ B C / \ / \ D E F G
- Duyệt tiền thứ tự với cây này diễn ra tuần tự như sau
- Thăm A, Duyệt cây gốc B, Duyệt cây gốc C
- Thăm A, Thăm B, Thăm D, Thăm E, Thăm C, Thăm F, Thăm G
- Duyệt trung thứ tự với cây này diễn ra tuần tự như sau
- Duyệt cây gốc B, Thăm A, Duyệt cây gốc C
- Thăm D, Thăm B, Thăm E, Thăm A, Thăm F, Thăm C, Thăm G
- Duyệt hậu thứ tự với cây này diễn ra tuần tự như sau
- Duyệt cây gốc B, Duyệt cây gốc C, Thăm A
- Thăm D, Thăm E, Thăm B, Thăm F, Thăm G, Thăm C, Thăm A
## Duyệt cây tổng quát[
[sửa](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&veaction=edit&vesection=6) | [sửa mã nguồn](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&action=edit§ion=6)]
Nếu tại gốc A của cây có các con từ trái sang phải là thì quá trình duyệt tiền thứ tự, trung và hậu thứ tự như sau
### Duyệt tiền thứ tự[
[sửa](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&veaction=edit&vesection=7) | [sửa mã nguồn](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&action=edit§ion=7)]
- Thăm A
- Lần lượt duyệt các cây con gốc
### Duyệt trung thứ tự[
[sửa](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&veaction=edit&vesection=8) | [sửa mã nguồn](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&action=edit§ion=8)]
- Duyệt cây con gốc
- Thăm A
- Lần lượt duyệt các cây con gốc
### Duyệt hậu thứ tự[
[sửa](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&veaction=edit&vesection=9) | [sửa mã nguồn](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&action=edit§ion=9)]
- Lần lượt duyệt các cây con gốc
- Thăm A
Tuy nhiên người ta ít xem xét việc duyệt trung thứ tự của cây tổng quát
## Duyệt theo mức[
[sửa](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&veaction=edit&vesection=10) | [sửa mã nguồn](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&action=edit§ion=10)]
Một phương pháp duyệt cây khác là duyệt theo mức. Bắt đầu duyệt từ gốc (đỉnh mức 0), rồi duyệt các con của gốc từ trái sang phải (các đỉnh mức 1), tiếp đến là các đỉnh mức 2,...
## Giả mã[
[sửa](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&veaction=edit&vesection=11) | [sửa mã nguồn](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&action=edit§ion=11)]
Giả sử có một cây nhị phân mà cấu trúc mỗi nút của nó chứa một giá trị
value và các tham chiếu
left và
right trỏ tới hai con của nút đó. Ta có thể viết các hàm sau:
### Duyệt tiền thứ tự[
[sửa](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&veaction=edit&vesection=12) | [sửa mã nguồn](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&action=edit§ion=12)]
(
**pre-order (prefix) traversal**)
visit(node) print node.value if node.left != null then visit(node.left) if node.right != null then visit(node.right)
### Duyệt hậu thứ tự[
[sửa](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&veaction=edit&vesection=13) | [sửa mã nguồn](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&action=edit§ion=13)]
(
**post-order (postfix) traversal**)
visit(node) if node.left != null then visit(node.left) if node.right != null then visit(node.right) print node.value
### Duyệt trung thứ tự[
[sửa](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&veaction=edit&vesection=14) | [sửa mã nguồn](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&action=edit§ion=14)]
(
**in-order (infix) traversal**)
visit(node) if node.left != null then visit(node.left) print node.value if node.right != null then visit(node.right)
## Cây nhị phân tương đương[
[sửa](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&veaction=edit&vesection=15) | [sửa mã nguồn](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&action=edit§ion=15)]
### Lưu trữ cấu trúc cây nhị phân[
[sửa](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&veaction=edit&vesection=16) | [sửa mã nguồn](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&action=edit§ion=16)]
Để biểu diễn cây nhị phân ta dùng cấu trúc Nút (
*Node*). Mỗi Nút là một đỉnh của cây, gồm ba trường, một trường chứa thông tin về nút đó. Hai trường và trỏ tới các nút con của đỉnh đó. Ngoài ra còn một con trỏ là trỏ tới nút gốc.
Cây nhị phân ở trong bài có thể biểu diễn như sau:
Root=A A.Value="A",A.Left=B;A.Right=C B.Value="B",B.Left=D;B.Right=E C.Value="C",C.Left=F;C.Right=G D.Value="D",D.Left=Null;D.Right=Null E.Value="E",E.Left=Null;E.Right=Null F.Value="F",F.Left=Null;F.Right=Null G.Value="G",G.Left=Null;G.Right=Null
Chú ý: Phân biệt kí hiệu A, B,... chỉ nút và "A","B",... chỉ giá trị nút
### Lưu trữ cấu trúc cây tổng quát[
[sửa](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&veaction=edit&vesection=17) | [sửa mã nguồn](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&action=edit§ion=17)]
Khi biểu diễn cấu trúc cây tổng quát, vì mỗi nút có thể có nhiều con, số con có thể khác nhau, nên ta không dùng cho mỗi nút con một liên kết đến nút cha mà với mỗi nút vẫn chỉ dành hai liên kết, một liên kết (trường ) trỏ đến nút con đầu bên trái của nó, một liên kết (trường )trỏ đến nút cùng cha kề bên phải nó. Nếu coi liên kết trường như liên kết , liên kết như liên kết ta có một cây nhị phân tương đương với cây tổng quát.
### Ví dụ[
[sửa](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&veaction=edit&vesection=18) | [sửa mã nguồn](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&action=edit§ion=18)]
- Cây tổng quát
A / | \ B C D / \ | E F G
- Cây nhị phân tương đương
A / B / \ E C \ \ F D / G
- Lưu trữ của cây tổng quát như sau
Root=A A.Value="A",A.Child=B,A.Next=Null B.Value="B",B.Child=E,B.Next=C C.Value="C",C.Child=Null,C.Next=D D.Value="D",D.Child=G,D.Next=Null E.Value="E",E.Null,E.Next=F F.Value="F",F.Child=Null,F.Next=Null G.Value="G",D.Child=Null,G.Next=Null
## Tham khảo[
[sửa](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&veaction=edit&vesection=19) | [sửa mã nguồn](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&action=edit§ion=19)]
## Liên kết ngoài[
[sửa](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&veaction=edit&vesection=20) | [sửa mã nguồn](/w/index.php?title=Duy%E1%BB%87t_c%C3%A2y&action=edit§ion=20)]
Tiếng Anh:
[The Adjacency List Model for Processing Trees with SQL](http://www.SQLSummit.com/AdjacencyList.htm) [Storing Hierarchical Data in a Database](http://www.sitepoint.com/article/hierarchical-data-database)with traversal examples in PHP [Managing Hierarchical Data in MySQL](http://dev.mysql.com/tech-resources/articles/hierarchical-data.html)

WARC-Type: response

Content-Type: application/http; msgtype=response

Connection: close

X-Content-Type-Options: nosniff

X-Cache: cp1055 miss, cp1067 miss

Accept-Ranges: bytes

Content-Type: text/html; charset=UTF-8