2013年全国数据整理加强

1、设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。
2、对一般二叉树，仅根据一个先序、中序、后序遍历，不能确定另一个遍历序列。但对于满二叉树，任一结点的左右子树均含有数量相等的结点，根据此性质，可将任一遍历序列转为另一遍历序列（即任一遍历序列均可确定一棵二叉树）。
void PreToPost(ElemType pre[] ,post[],int l1,h1,l2,h2)
//将满二叉树的先序序列转为后序序列，l1,h1,l2,h2是序列初始和最后结点的下标。
{if(h1>=l1)
{post[h2]=pre[l1]; //根结点
half=(h1-l1)/2; //左或右子树的结点数
PreToPost(pre,post,l1+1,l1+half,l2,l2+half-1) //将左子树先序序列转为后序序列
PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1) //将右子树先序序列转为后序序列
} }//PreToPost
32. .叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。
LinkedList head,pre=null; //全局变量
LinkedList InOrder(BiTree bt)
//中序遍历二叉树bt，将叶子结点从左到右链成一个单链表，表头指针为head
{if(bt){InOrder(bt->lchild); //中序遍历左子树
if(bt->lchild==null && bt->rchild==null) //叶子结点
if(pre==null) {head=bt; pre=bt;} //处理第一个叶子结点
else{pre->rchild=bt; pre=bt; } //将叶子结点链入链表
InOrder(bt->rchild); //中序遍历左子树
pre->rchild=null; //设置链表尾
}
return(head); } //InOrder
时间复杂度为O(n),辅助变量使用head和pre,栈空间复杂度O(n)

3、题目中要求矩阵两行元素的平均值按递增顺序排序，由于每行元素个数相等，按平均值排列与按每行元素之和排列是一个意思。所以应先求出各行元素之和，放入一维数组中，然后选择一种排序方法，对该数组进行排序，注意在排序时若有元素移动，则与之相应的行中各元素也必须做相应变动。
void Translation（float *matrix，int n）
//本算法对n×n的矩阵matrix，通过行变换，使其各行元素的平均值按递增排列。
{int i,j,k,l；
float sum，min； //sum暂存各行元素之和
float *p, *pi, *pk;
for(i=0; i<n; i++)
{sum=0.0; pk=matrix+i*n; //pk指向矩阵各行第1个元素.
for (j=0; j<n; j++){sum+=*(pk); pk++;} //求一行元素之和.
*(p+i)=sum; //将一行元素之和存入一维数组.
}//for i
for(i=0; i<n-1; i
++) //用选择法对数组p进行排序
{min=*(p+i); k=i; //初始设第i行元素之和最小.
for(j=i+1;j<n;j++) if(p[j]<min) {k=j; min=p[j];} //记新的最小值及行号.
if(i!=k)