樹の走訪是什麼?要怎麼做?

樹的走訪是一種用來儲存樹裡面資料方式

樹的追蹤有哪些

理論上有4種，但實際上比較常用到的只有2種

分別是Depth-First Search(DFS)=>by stack、Breathe-First-Search(BFS)=>by queue

DFS、BFS到時候談到圖(graph)的走訪再更進一步描述。

Preorder Traversal 前序遍歷

走訪的方式是->DLR
DLR的意思就是先走訪:根(D)，再走訪左子樹(L)，再走訪右子樹(R)
基本上跟跟Depth-first Search一樣。

Inorder Traversal 中序遍歷

走訪的方式是->LDR
舉例:LDR，D在中間代表為中序遍歷。
實際上是採用Depth-first Search，但輸出順序有一點不同。

Postorder Traversal 後序遍歷

走訪的方式是->LRD

實際上是採用Depth-first Search，但輸出順序有一點不同。

Level-order Traversal 層序遍歷

跟Breadth-first Search一模一樣。

樹的追蹤演算法?

DFS:

bool adj[9][9];     // adjacency matrix
int parent[9];      // DFS tree

void DFS(int x)
{
    for (int y=0; y<9; ++y)
        if (adj[x][y])
            if (y != parent[x]) // 避免走回頭路
            {
                parent[y] = x;
                DFS(y);
            }
}

二元樹的追蹤演算法

首先要先知道BT的資料結構:

再了解指標的寫法:

最後演算法:

Precodure Preorder (Node* X)
{
printf(X->data);-------------D
Preorder(X->left);----------L
Preorder(X->right);----------R
}