資料結構學習（二叉樹：四（中序周遊））

二叉樹周遊

中序周遊

所謂中序周遊就是先通路左孩子，再通路根節點，最後通路右孩子。

遞歸：

template <typename T, typename VST>
void travIn_R (BinNodePosi(T) x, VST& visit)
{//二叉樹中序周遊算法（遞歸版）
	if(!x) return;
	travIn_R(x -> lc, visit);
	visit(x -> data);
	travIn_R(x -> rc, visit);
}	
           

疊代：

template <typename T>//從目前節點出發，沿左分支不斷深入，直至沒有左分支的節點
static void goAlongLeftBranch(BinNodePosi(T) x, Stack<BinNodePosi(T)& S>)
{
	while(x) { S.push(x); x = x -> lc; }//目前節點入棧後随即項左側分支深入，疊代直到無左孩子
}

template <typename T, typename VST>//元素類型、操作器
void tracIn_I1(BinNodePosi(T) x, VST& visit)
{//二叉樹中序周遊算法（疊代版）
	Stack<BinNodePosi(T)> S;//輔助棧
	while(true)
	{
		goAlongLeftBranch(x, S);//從目前節點出發，逐批入棧
		if(S.empty()) break;//直至所有節點處理完畢
		x = S.pop(); visit(x -> data);//彈出棧頂節點并通路
		x = x -> rc;//轉向右子樹
	 }
}
           

以上算法再全樹及其中每一棵子樹的根節點處，該算法首先調用函數goAlongLeftBranch（），沿最左側通路自頂而下抵達末端節點。在此過程中，利用輔助棧逆序地記錄和儲存沿途經過的各個節點，以便确定自底而上各段周遊子序列最終在宏觀上的拼接次序。

複雜度：O（n）（雖然與遞歸版複雜度都是線性複雜度，但是疊代版的常系數為1，更加高效）