在電腦科學裏,樹的走訪(也稱為樹的遍歷或樹的搜尋)是一種圖的遍歷,指的是按照某種規則,不重複地訪問某種樹的所有節點的過程。具體的訪問操作可能是檢查節點的值、更新節點的值等。不同的走訪方式,其訪問節點的順序是不一樣的。以下雖然描述的是二叉樹的走訪演算法,但它們也適用於其他樹形結構。
此條目需要擴充。 (2010年10月3日) |
走訪的種類
與那些基本上都有標準走訪方式(通常是按線性順序)的線性數據結構(如鏈結串列、一維陣列)所不同的是,樹結構有多種不同的走訪方式。從二叉樹的根節點出發,節點的走訪分為三個主要步驟:對當前節點進行操作(稱為「訪問」節點)、走訪左邊子節點、走訪右邊子節點。這三個步驟的先後順序也是不同走訪方式的根本區別。
由於從給定的某個節點出發,有多個可以前往的下一個節點(樹不是線性數據結構),所以在順序計算(即非平行計算)的情況下,只能推遲對某些節點的訪問——即以某種方式儲存起來以便稍後再訪問。常見的做法是採用堆疊(LIFO)或佇列(FIFO)。由於樹本身是一種自我參照(即遞歸定義)的數據結構,因此很自然也可以用遞歸方式,或者更準確地說,用共遞歸,來實現延遲節點的儲存。這時(採用遞歸的情況)這些節點被儲存在呼叫堆疊中。
走訪方式的命名,源於其訪問節點的順序。最簡單的劃分:是深度優先(先訪問子節點,再訪問父節點,最後是第二個子節點)?還是廣度優先(先訪問第一個子節點,再訪問第二個子節點,最後訪問父節點)? 深度優先可進一步按照根節點相對於左右子節點的訪問先後來劃分。如果把左節點和右節點的位置固定不動,那麼根節點放在左節點的左邊,稱為前序(pre-order)、根節點放在左節點和右節點的中間,稱為中序(in-order)、根節點放在右節點的右邊,稱為後序(post-order)。對廣度優先而言,走訪沒有前序中序後序之分:給定一組已排序的子節點,其「廣度優先」的走訪只有一種唯一的結果。
![Thumb](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d4/Sorted_binary_tree_preorder.svg/320px-Sorted_binary_tree_preorder.svg.png)
F, B, A, D, C, E, G, I, H.
前序走訪(Pre-Order Traversal)是依序以根節點、左節點、右節點為順序走訪的方式。 其遍歷順序是:
1 |
| ||||||||||||
void pre_order_traversal(TreeNode *root) {
// Do Something with root
if (root->lchild != NULL) //若其中一側的子樹非空則會讀取其子樹
pre_order_traversal(root->lchild);
if (root->rchild != NULL) //另一側的子樹也做相同事
pre_order_traversal(root->rchild);
}
![Thumb](http://upload.wikimedia.org/wikipedia/commons/thumb/7/77/Sorted_binary_tree_inorder.svg/320px-Sorted_binary_tree_inorder.svg.png)
A, B, C, D, E, F, G, H, I.
中序走訪(In-Order Traversal)是依序以左節點、根節點、右節點為順序走訪的方式。 其遍歷順序是:
4 |
| ||||||||||||
void in_order_traversal(TreeNode *root) {
if (root->lchild != NULL) //若其中一側的子樹非空則會讀取其子樹
in_order_traversal(root->lchild);
// Do Something with root
if (root->rchild != NULL) //另一側的子樹也做相同事
in_order_traversal(root->rchild);
}
![Thumb](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9d/Sorted_binary_tree_postorder.svg/320px-Sorted_binary_tree_postorder.svg.png)
A, C, E, D, B, H, I, G, F.
後序走訪(Post-Order Traversal)是依序以左節點、右節點、根節點為順序走訪的方式。 其遍歷順序是:
5 |
| ||||||||||||
void post_order_traversal(TreeNode *root) {
if (root->lchild != NULL) //若其中一側的子樹非空則會讀取其子樹
post_order_traversal(root->lchild);
if (root->rchild != NULL) //另一側的子樹也做相同事
post_order_traversal(root->rchild);
// Do Something with root
}
和深度優先走訪不同,廣度優先走訪會先訪問離根節點最近的節點。二叉樹的廣度優先走訪又稱按層次走訪。演算法藉助佇列實現。 其遍歷順序是:
1 |
| ||||||||||||
![Thumb](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d1/Sorted_binary_tree_breadth-first_traversal.svg/220px-Sorted_binary_tree_breadth-first_traversal.svg.png)
F, B, G, A, D, I, C, E, H.
void level(TreeNode *node)
{
Queue *queue = initQueue();
enQueue(queue, node);
while (!isQueueEmpty(queue))
{
TreeNode *curr = deQueue(queue);
// Do Something with curr
if (curr->lchild != NULL)
enQueue(queue, curr->lchild);
if (curr->rchild != NULL)
enQueue(queue, curr->rchild);
}
}
多叉樹的走訪
先訪問根結點,後選擇一子結點訪問並訪問該節點的子結點,持續深入後再依序訪問其他子樹,可以輕易用遞歸或棧的方式實現。
void travel(treenode* nd){
for(treenode* nex : nd->childs){ //childs存放指向其每個子結點的指標
travel(nex);
}
return;
}
參見
參考資料
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.