数据结构学习（二叉树：四（中序遍历））

二叉树遍历

中序遍历

所谓中序遍历就是先访问左孩子，再访问根节点，最后访问右孩子。

递归：

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，更加高效）