最近写一个矩阵连乘的问题，在打印括号的时候遇到了难题，不知道括号和序列怎么输出才能得到标准的加括号序列，在网上查到了一个博客发现是对的，在此记录一下，顺便和floyed打印路径的方式作对比，以此来加深对二叉树遍历的理解。
首先上矩阵连乘的图和代码
void Traceback(vector<int>p,int m,int n) //表示的是矩阵的值，这里好像没什么用，因为实际上用的是s矩阵
{
if (m == n) {
cout << "A"<<m; return;
}
cout << "(";
Traceback(p, m, s[m][n]);
Traceback(p, s[m][n]+1, n);
cout << ")";
}
这里的s数组就是指在哪个地方加上括号。画个图来方便理解:
两个问题：一是遇到叶结点直接返回，只要输出值即可。
二是左括号和右括号的时机，分别是在第一次遇到结点，和离开结点的时候加上。类似先序和后序遍历。
em,想了半天也不知道啥时候该输出值，啥时候该输出括号。记住遇到叶结点的时候直接返回了，不会深入叶结点的空间，而且每个叶结点只遇见一次，所以在叶节点打印值是最合理的。
对于每一个开裂的非叶子空间就要在进入空间时加左括号，离开时加右括号。这个确实不知道怎么切入。
void Traceback(vector<int>p,int m,int n)
{
if (m == n) {
cout << "A"<<m; return;
}
cout << "(";
Traceback(p, m, s[m][n]);
cout << ")";
cout << "(";
Traceback(p, s[m][n]+1, n);
cout << ")";
}
这里给每个中序的地方加上了左括号和右括号，也是对的，但是出现了很多的冗余，因为即使有一个元素也被加上了括号。
结果如下：
两相对比，就发现这个加括号在我看来很古怪。你想啊，就单从函数本身来看，在两个递归之间断开加上括号不是很合理吗，s[m][n]也确实是其中的一个分割点。但是这么加就会有很多冗余，反而不如第一种标准的加法，虽然用二叉树的遍历方式可以理解，但是在自己思考的时候还是觉得递归可读性可理解性确实差。
Floyd算法代码：
void floyed(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
p[i][j]=k; //记录插点
}
}
}
}
//打印路径的代码
void path(int i,int j)
{
if(p[i][j]==0) return ; //没有插点就返回
int k=p[i][j];
path(i,k); //打印插点
cout<<"->"<<k<<"->";
path(k,j);
}
int main()
{
cout<<a<<"->"; 。//第一个点和最后一个点是不会被输出的，记得加上
path(a,b);
cout<<b;
}
这里的输出路径就是递归搜索两个点之间的插点，也就是中序遍历了，看下面的图也可以理解。
总结一下，这种递归二叉树的遍历最好还是画个图理解一下，搞清楚在叶结点和非叶子结点分别要干什么事，其实也不是很难（ 不难才怪 ···）