備注：本文使用的範例代碼來自《系統設計師教程》（王春森主編），本文性質屬于我的對引用代碼的注釋和分析，是以并非原創。本文的部分先發表于中國程式設計論壇。
（一）用棧前序周遊樹
對這篇文章的來源性說明：理論和代碼來源，《系統設計師教程》（王春森主編），文章内容來自我對書中代碼的分析和手工注釋。
（ 本文獻給小師妹：littlehead（我是大好人））
名詞：棧，周遊，前序周遊，樹。
（1）準備：樹的定義省略。但是由于數的定義屬于遞歸型定義，即樹的每個子節點又是一棵樹，是以這個遞歸型的定義使對樹的很多操作通常都可以用遞歸算法來實作。對數節點的定義，一個節點含有一個資料，這裡以一個字元資料作為示範，假設一個節點最多含有M個子節點（M成為樹的次數），則節點定義為：
typedef struct tnode
{
char data;
struct tnode *child[M];
} TNODE;
我們對用根節點指針來持有和處理一棵樹：即：
TNODE *root;
前序周遊和後序周遊：周遊值得是依次輸出所有節點資料。前序後序中的序指的是本節點和其子節點之間的輸出順序關系。對于普通樹來說存在前序，後序兩種周遊。對二叉樹來說又有中序周遊。
（2）我們先給出前序周遊的僞碼為：
void pre_order(TNODE *t, int m) //m為數次數
if(t!=NULL) 列印t； //先輸出本節點
for(i=0;i<m;i++)
pre_order(t->child[i],m); //前序輸出所有子節點
}
/*--------------------------------
root-> 1
/ | \
2 3 4
/ \ |
5 6 7
/ \
8 9
----------------------------------*/
對于圖1所示的樹，則其前序周遊和後序周遊如下：
前序：1，2，5，6，3，4，7，8，9；
後序：5，6，2，3，8，9，7，4，1；
（3）采用棧來代替遞歸函數的方法如下：
方法：每出棧一個節點，列印該節點，然後則将其所有子節點逆序（從右到左）入棧。
初始棧狀态：根節點入棧。棧中僅有根節點。棧頂指針top=1；
結束條件：棧為空。即棧頂指針top=0；
其相關代碼如下 ：
Code_使用棧前序周遊樹
/*使用棧前序周遊樹*/
#define M 10 /*樹的次/度：最大子節點數*/
#define SN 100 /*棧最大深度*/
typedef struct tnode
char data;
struct tnode *child[M];
}TNODE;
/*t-root; m-度*/
void pre_order(TNODE *t,int m)
TNODE *s[SN];/*定義棧*/
int top=0,i;/*top-棧頂指針；*/
if(t==NULL)
return;
s[top++]=t;/*根節點入棧*/
while(top>0) /*當棧不為空時：*/
{
t=s[--top];/*取出棧頂節點并列印輸出該節點*/
printf("%c ",t->data);
/*将目前節點的子節點按逆序入棧*/
for(i=m-1;i>=0;i--)
{
if(t->child[i])
s[top++]=t->child[i];
}
}
周遊時的棧中節點狀态如圖2所示（藍色箭頭表示棧頂，每一行表示棧在目前的一個狀态）。
（二）用隊列按層次周遊樹
（1）按層次周遊樹。層次，即相當于資料總管的檔案夾深度，見前文圖1中的縱坐标。由于在示例樹中的節點編号就是按照層次來給出的，是以按層次周遊這棵樹的結果就是：1，2，3，4，5，6，7，8，9。
由于我們在周遊過程中處于樹的某個局部，是以我們需要引入一個輔助資料結構來幫助我們完成周遊。考慮到層次周遊的特點是，每一層次的所有子節點應該集中在一起，當通路某個節點時，其下一層次的子節點應該處于等待被通路的狀态。是以我們應該引入隊列作為輔助存儲。
方法如下：
Title
算法：每次取出隊首節點，列印該節點，隊首指針向後移動一格，然後将其所有子節點順序進入列尾部，隊尾指針相應向後移動。
初始隊列狀态：根節點入隊列，隊列中僅有根節點。head=0，tail=1；
結束條件：隊列為空。即隊列的兩個指針重合，head==tail；
隊列我們同樣用一個數組來模拟，并且需要兩個變量head和tail來辨別隊列的有效區間，隊列的特點是FIFO（先入先出），是以，子序列入隊是順序入隊（和前文中用棧前序不同，由于棧的特點是FILO或者LIFO，是以子節點是逆序入棧的）。有效隊列在數組中處于移動狀态，在head，tail在移動到數組末尾時，重新指向數組前部，是以代碼中這裡有個索引自增後對隊列長度取餘的運算，是以實際上這裡的隊列在邏輯上是環形的，也就是數組的首尾相接，是以隻有向隊首或者向隊尾兩種移動方向的差別，而隊列位于數組的什麼位置并不重要（比如隊列可能會一部分位于數組末端，一部分位于數組起始處，在記憶體視角上看不是連續的，但在邏輯上依然是連續的）。
下面我們看相關的代碼：
Code_層次周遊
/* 用隊列（queue）來層次周遊一顆普通樹*/
#define QN 100 /*隊列最大長度*/
int lev_order(TNODE *t, int m)
TNODE *q[QN];/* queue */
TNODE *p;
int head=0, tail=0, i;/*隊列的頭，尾索引*/
q[tail++]=t; /*根節點入列*/
while(head!=tail)/* 當隊列不為空（首尾相遇時為空） */
p=q[head];/*從隊首出列一個節點*/
head=(head+1)%QN; /* head向後（隊尾方向）移動一格 */
printf("%c ",t->data);/*列印該節點*/
for(i=0;i<m;i++) /* 出列節點的所有子節點按順序入列（進入隊列尾部） */
if(p->child[i])
{
if((tail+1)%QN==head) /*如果隊列已經滿了，傳回0表示失敗 */
return 0;
q[tail]=p->child[i]; /*子節點入列*/
tail=(tail+1)%QN; /* tail向後移動一格 */
}
return 1; /*周遊結束，傳回1表示成功*/
（2）關于樹的少許補充：
2.1 二叉查找樹和堆的結構看起來一樣，但是差別是，二叉查找樹：左子<=根<=右子； 而堆是：子節點<=根。另外，堆在邏輯上是樹形，但存儲是用數組存儲的（節點按層次連續存入數組）。
2.2 中序周遊二叉查找樹，輸出的一個有序結果。
2.3 用作圖法按前序，後序周遊樹的規律：
假設我們把二叉樹的一個節點提取出來，我們看出，從節點中心垂直向上定義為0度角，逆時針正向，則節點的左右子樹分支分别為120度（左子樹）和240（右子樹）。則我們可以用作圖法得到各種序周遊的節點輸出角度：從根節點上方向左下方畫一條線外圍住所有節點直到傳回根節點，當線條經曆到節點的以下角度時輸出該節點（如圖3所示，前序輸出為1，2，4，5，3，6）：
前序輸出角度：60度；
中序（僅針對二叉樹）：180度；
後序：300度。
（三）圖的周遊
圖是一種複雜資料結構，圖需要存儲節點與節點之間的關聯關系，主要有矩陣和連結清單兩種存儲方法。這裡采用連結清單，針對每個節點都存儲一個連結清單，連結清單中表示的是所有和該節點有連結的其他節點号。是以我們需要一個指針數組來存儲所有連結清單。代碼如下：
Code_圖周遊
/*深度周遊和廣度周遊圖，圖采用一組連結清單存儲*/
#include <stdio.h>
#define N 30 /*最大節點數*/
typedef struct node
int vno;
struct node *next;
} edgeNode;
typedef edgeNode* Graph[N];
/*建立一張圖。每輸入一條邊，與之聯系的節點插入到該節點連結清單的頭部*/
int create_list(Graph g)
int vn, en, k, i, j;
edgeNode *p;
printf("\ninput count of nodes:\n");
scanf("%d", &vn);
printf("input count of edges:\n");
scanf("%d",&en);
for(k=0; k<N; k++)
g[k]=NULL;
for(k=0; k<en; k++)
printf("input the edge[%d](i,j):\n", k);
scanf("%d,%d",&i,&j);
p=(edgeNode*)malloc(sizeof(edgeNode));
p->vno=j;
p->next = g[i];
g[i]=p;
p->vno=i;
p->next = g[j];
g[j]=p;
/*傳回圖中節點數*/
return vn;
/*列印輸出所有節點連結清單*/
void print_list(Graph g)
int i;
edgeNode *p=NULL;
printf("\nGraph g:\n");
for(i=0; i<N; i++)
if(g[i]==NULL)
continue;
printf("g[%d]: ",i);
p=g[i]; /* p = head*/
while(p!=NULL)
printf("%d - ",p->vno);
p = p->next;
printf("NULL\n");
/*------------------------遞歸，深度周遊-------------------------*/
/*存儲節點狀态，是否被周遊*/
int visited[N];
void clearflags()
visited[i]=0;
/*深度優先周遊，采用遞歸函數*/
void dfs(Graph g, int i)
edgeNode *t;
printf("%4d,", i);
visited[i] = 1;
t=g[i];
while(t!=NULL)
if(visited[t->vno]==0)
dfs(g,t->vno);
t=t->next;
/*------------------------隊列，廣度周遊------------------------*/
#define M (2*N)
int queue[M];
/*廣度優先周遊*/
void bfs(Graph g, int s)
int i, v, w, head, tail;
head=tail=0;
/*通路該節點，并且該節點進隊*/
printf("%4d,", s);
visited[s]=1;
queue[tail++]=s;
while(head != tail) /*當隊列不為空時*/
v = queue[head]; /*隊列首節點出列*/
head = (head+1)%M; /*head指針向右方移動*/
for(t=g[v]; t!=NULL; t=t->next)
w = t->vno;
if(visited[w]==0)
printf("%4d,", w);
visited[w] = 1;
if((tail+1)%M == head)
{
printf("queue's size is too small! !");
return;
}
queue[tail] = w; /*頂點w進隊*/
tail = (tail+1)%M;
/*
0---1
|\ /|
| 4 |
|/ \|
3---2
*/
void main()
Graph g;
int i,vn;
vn = create_list(g);
printf("g has %d nodes\n",vn);
/*深度周遊*/
printf("\n dfs: ");
clearflags();
dfs(g,0);
/*廣度周遊*/
printf("\n bfs: ");
bfs(g,0);
print_list(g);
getch();
針對下面這張圖：
程式的輸出如下：
dfs: 0, 4, 3, 2, 1, （深度優先周遊）
bfs: 0, 4, 3, 1, 2, （廣度優先周遊）
Graph g: （圖g的所有節點連結清單）
g[0]: 4 - 3 - 1 - NULL
g[1]: 4 - 2 - 0 - NULL
g[2]: 4 - 3 - 1 - NULL
g[3]: 4 - 0 - 2 - NULL
g[4]: 3 - 2 - 1 - 0 - NULL