樹的走訪

在計算機科學裡，樹的遍歷（也稱為樹的遍歷或樹的搜索）是一種圖的遍歷，指的是按照某種規則，不重複地訪問某種樹的所有節點的過程。具體的訪問操作可能是檢查節點的值、更新節點的值等。不同的遍歷方式，其訪問節點的順序是不一樣的。以下雖然描述的是二叉樹的遍歷算法，但它們也適用於其他樹形結構。

遍歷的種類

與那些基本上都有標準遍歷方式（通常是按線性順序）的線性數據結構（如鍊表、一維數組）所不同的是，樹結構有多種不同的遍歷方式。從二叉樹的根節點出發，節點的遍歷分為三個主要步驟：對當前節點進行操作（稱為「訪問」節點）、遍歷左邊子節點、遍歷右邊子節點。這三個步驟的先後順序也是不同遍歷方式的根本區別。

由於從給定的某個節點出發，有多個可以前往的下一個節點（樹不是線性數據結構），所以在順序計算（即非並行計算）的情況下，只能推遲對某些節點的訪問——即以某種方式保存起來以便稍後再訪問。常見的做法是採用堆棧（LIFO）或隊列（FIFO）。由於樹本身是一種自我引用（即遞歸定義）的數據結構，因此很自然也可以用遞歸方式，或者更準確地說，用共遞歸，來實現延遲節點的保存。這時（採用遞歸的情況）這些節點被保存在呼叫堆疊中。

遍歷方式的命名，源於其訪問節點的順序。最簡單的劃分：是深度優先（先訪問子節點，再訪問父節點，最後是第二個子節點）？還是廣度優先（先訪問第一個子節點，再訪問第二個子節點，最後訪問父節點）？深度優先可進一步按照根節點相對於左右子節點的訪問先後來劃分。如果把左節點和右節點的位置固定不動，那麼根節點放在左節點的左邊，稱為前序（pre-order）、根節點放在左節點和右節點的中間，稱為中序（in-order）、根節點放在右節點的右邊，稱為後序（post-order）。對廣度優先而言，遍歷沒有前序中序後序之分：給定一組已排序的子節點，其「廣度優先」的遍歷只有一種唯一的結果。

深度優先遍歷

分作前序走訪、中序走訪、後序走訪，前、中、後代表根節點在走訪時的位置。以下透過C語言實作，並均使用遞歸方法。

前序遍歷

前序遍歷（Pre-Order Traversal）是依序以根節點、左節點、右節點為順序走訪的方式。其遍歷順序是：

1

2

	3

	4

5

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);
}

中序遍歷

中序遍歷（In-Order Traversal）是依序以左節點、根節點、右節點為順序走訪的方式。其遍歷順序是：

4

2

	1

	3

5

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);
}

後序遍歷

後序遍歷（Post-Order Traversal）是依序以左節點、右節點、根節點為順序走訪的方式。其遍歷順序是：

5

3

	1

	2

4

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

2

	4

	5

3

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!

樹的走訪