二叉樹的周遊，就是指按某條搜尋路徑通路樹中的每個結點，使得每個結點均被通路一次，而且僅被通路一次。
周遊一棵二叉樹便要決定對根結點N，左子樹L和右子樹R的通路順序。按照先周遊左子樹再周遊右子樹的原則，常見的周遊次序有先序(NLR)、中序(LNR)、後序(LRN)三種周遊算法，其中的序是指根結點在何時被通路。
一、先序周遊
先序周遊(PreOrder)的操作過程如下：
若二叉樹為空，則什麼也不做；否則：
1）通路根結點；
2）先序周遊左子樹；
3）先序周遊右子樹。
對應的遞歸算法如下：
void PreOrder(BiTree T)
{
if(T!=NULL)
{
visit(T); //通路根結點
PreOrder(T->lchild); //遞歸周遊左子樹
PreOrder(T->rchild); //遞歸周遊右子樹
}
}
上圖先序周遊得到的結果為1,2,4,6,3,5。
注意：這裡提供的是僞代碼的形式，主要是明白周遊思想，具體要結合實際問題實際分析，下同。
二、中序周遊
中序周遊(InOrder)的操作過程如下：
若二叉樹為空，則什麼也不做；否則，
1）中序周遊左子樹；
2）通路根結點；
3）中序周遊右子樹。
對應的遞歸算法如下：
void InOrder(BiTree T)
{
if(T!=NULL)
{
InOrder(T->lchild); //遞歸周遊左子樹
visit(T); //通路根結點
InOrder(T->rchild); //遞歸周遊右子樹
}
}
又是這個圖，其中序周遊得到的結果為2,6,4,1,3,5。
這裡可能不太好了解，分步列一下：
（1）進入結點1左子樹；
（2）進入結點2左子樹，為空，結點2左子樹通路完畢，傳回結點2；
（3）通路結點2，通路順序為2；
（4）進入結點2右子樹；
（5）進入結點4左子樹；
（6）進入結點6左子樹，為空，傳回結點6；
（7）通路結點6，通路順序為2,6；
（8）進入結點6右子樹，為空，傳回結點6，結點4左子樹通路完畢，傳回結點4；
（9）通路結點4，通路順序為2,6,4；
（10）進入結點4右子樹，為空，傳回結點4，結點2右子樹通路完畢，傳回結點1；
（11）通路根結點1，通路順序為2,6,4,1；
右子樹的通路思路同上。
三、後序周遊
後序周遊(PostOrder)的操作過程如下：
若二叉樹為空，則什麼也不做；否則，
1）後序周遊左子樹；
2）後序周遊右子樹；
3）通路根結點。
對應的遞歸算法如下：
void PostOrder(BiTree T)
{
if(T!=NULL)
{
PostOrder(T->lchild); //遞歸周遊左子樹
PostOrder(T->rchild); //遞歸周遊右子樹
visit(T); //通路根結點
}
}
還是這個圖，後序周遊得到的結果為6,4,2,5,3,1
這個應該還是比較好了解的。
三種周遊算法中，遞歸周遊左、右子樹的順序都是固定的，隻是通路根結點的順序不同。不管采用哪種周遊算法，每個結點都通路一次且僅通路一次，故時間複雜度都是O(n)。
四、遞歸算法和非遞歸算法的轉換
借助棧，我們可以将二叉樹的遞歸周遊算法轉換為非遞歸算法。以中序周遊為例，先掃描根結點的所有左結點并将它們一一進棧，然後出棧一個結點*p，通路它，然後掃描該結點的右孩子結點，将其進棧，再掃描該右孩子結點的所有左結點并一一進棧，如此繼續，直到棧空為止。
中序周遊的非遞歸算法如下：
void InOrder2(BiTree T)
{ //二叉樹中序周遊的非遞歸算法需要借助一個棧
InitStack(S);
BiTree p=T; //初始化棧；p是周遊指針
while(p||!IsEmpty(S)) //棧不空或p不空時循環
{
if(P) //根指針進棧，周遊左子樹
{
Push(S,p); //每遇到非空二叉樹先向左走
p=p->lchild;
}
else //根指針退棧，通路根結點，周遊右子樹
{
Pop(S,p); //退棧，通路根結點
visit(p);
p=p->rchild; //再向右子樹走
}
}
}
非遞歸算法的效率肯定比遞歸算法的效率高滴！
五、層次周遊
層次周遊顧名思義就是對每一層都進行周遊，如下圖所示：
要進行層次周遊需要一個隊列。先将二叉樹根結點入隊，然後出隊，通路該結點，若它有左子樹，則将左子樹根結點入隊；若它有右子樹，則将右子樹根結點入隊。然後出隊，對出隊結點通路，如此反複，直到隊列空。
二叉樹層次周遊算法如下：
void LevelOrder(BiTree T)
{
InitQueue(Q); //初始化輔助隊列
BiTree p;
EnQueue(Q,T); //将根結點入隊
while(!IsEmpty(Q)) //隊列不空循環
{
DeQueue(Q,p); //隊頭元素出隊
visit(p); //通路目前p所指向結點
if(p->lchild!=NULL)
EnQueue(Q,p->lchild); //左子樹不空，則左子樹入隊列
if(p->rchild!=NULL)
EnQueue(Q,p->rchild); //右子樹不空，則右子樹入隊列
}
}
六、由周遊序列構造二叉樹
由二叉樹的先序序列和中序序列可以唯一地确定一棵二叉樹。
由二叉樹的後序序列和中序序列也可以唯一地确定一棵二叉樹。
由二叉樹的層次序列和中序序列也可以唯一地确定一棵二叉樹。
這告訴我們一個道理：想要利用周遊序列構造二叉樹，中序序列必不可少！！