1、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。
当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。
设当n=m-1时结论成立，现证明当n=m时结论成立。
设中序序列为S1，S2，?，Sm,后序序列是P1,P2,?，Pm。因后序序列最后一个元素Pm是根，则在中序序列中可找到与Pm相等的结点（设二叉树中各结点互不相同）Si(1≤i≤m)，因中序序列是由中序遍历而得，所以Si是根结点，S1，S2，?，Si-1是左子树的中序序列，而Si+1,Si+2,?,Sm是右子树的中序序列。
若i=1，则S1是根，这时二叉树的左子树为空，右子树的结点数是m-1,则{S2，S3，?，Sm}和{P1，P2，?，Pm-1}可以唯一确定右子树，从而也确定了二叉树。
若i=m,则Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则{S1，S2，?，Sm-1}和{P1，P2，?，Pm-1}唯一确定左子树，从而也确定了二叉树。
最后，当1<i<m时，Si把中序序列分成{S1，S2，?，Si-1}和{Si+1,Si+2,?，Sm}。由于后序遍历是“左子树—右子树—根结点”，所以{P1,P2,?,Pi-1}和{Pi,Pi+1,?Pm-1}是二叉树的左子树和右子树的后序遍历序列。因而由{S1，S2，?，Si-1}和{P1，P2，?，Pi-1} 可唯一确定二叉树的左子树，由{Si+1,Si+2,?，Sm}和
{Pi,Pi+1,?，Pm-1}可唯一确定二叉树的右子树。
2、冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。
48.有n个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向起泡排序即相邻两趟排序向相反方向起泡）
3、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。（注：图中不存在顶点到自己的弧）
有向图判断回路要比无向图复杂。利用深度优先遍历，将顶点分成三类：未访问；已访问但其邻接点未访问完;已访问且其邻接点已访问完。下面用0，1，2表示这三种状态。前面已提到，若dfs（v）结束前出现顶点u到v的回边，则图中必有包含顶点v和u的回路。对应程序中v的状态为1，而u是正访问的顶点，若我们找出u的下一邻接点的状态为1，就可以输出回路了。
void Print(int v,int start ) //输出从顶点start开始的回路。
{for(i=1;i<=n;i++)
if(g[v][i]!=0 && visited[i]==1 ) //若存在边（v,i），且顶点i的状态为1。 {printf(“%d”,v);
if(i==start) printf(“\\n”); else Print(i,start);break;}//if
void dfs(int v)
{visited[v]=1;
for(j=1;j<=n;j++ )
if (g[v][j]!=0) //存在边(v,j)
if (visited[j]!=1) {if (!visited[j]) dfs(j); }//if
else {cycle=1; Print(j,j);}
visited[v]=2;
}//dfs
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库2012西藏自治区JAVA版本加强在线全文阅读。
相关推荐：