2014年贵州省数据概述加强(7)

2014年贵州省数据概述加强

序序列中查找根结点，然后，左右子女信息入队列
if (in[i]==level[0]) break;
if (i==0) //根结点无左子树，遍历序列的1—n-1是右子树
{p->lchild=null;
s.lvl=++R; s.l=i+1; s.h=n-1; s.f=p; s.lr=2; enqueue(Q,s);
}
else if (i==n-1) //根结点无右子树，遍历序列的1—n-1是左子树
{p->rchild=null;
s.lvl=++R; s.l=1; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);
}
else //根结点有左子树和右子树
{s.lvl=++R; s.l=0; s.h=i-1; s.f=p; s.lr=1;enqueue(Q,s);//左子树有关信息入队列
s.lvl=++R; s.l=i+1;s.h=n-1;s.f=p; s.lr=2;enqueue(Q,s);//右子树有关信息入队列
}
while (!empty(Q)) //当队列不空，进行循环，构造二叉树的左右子树
{ s=delqueue(Q); father=s.f;
for (i=s.l; i<=s.h; i++)
if (in[i]==level[s.lvl]) break;
p=(bitreptr)malloc(sizeof(binode)); //申请结点空间
p->data=level[s.lvl]; p->lchild=null; p->rchild=null; //填写该结点数据
if (s.lr==1) father->lchild=p;
else father->rchild=p； //让双亲的子女指针指向该结点
if (i==s.l)
{p->lchild=null; //处理无左子女
s.lvl=++R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s);
}
else if (i==s.h)
{p->rchild=null; //处理无右子女
s.lvl=++R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);
}
else{s.lvl=++R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);//左子树有关信息入队列
s.lvl=++R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); //右子树有关信息入队列
}
}//结束while (!empty(Q))
return(p);
}//算法结束

24、请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。 二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。
25、矩阵中元素按行和按列都已排序，要求查找时间复杂度为O（m+n），因此不能采用常规的二层循环的查找。可以先从右上角（i=a,j=d）元素与x比较，只有三种情况：一是A[i,j]>x， 这情况下向j 小的方向继续查找；二是A[i,j]<x，下步应向i大的方向查找；三是A[i,j]=x，查找成功。否则，若下标已超出范围，则查找失败。
void search(datatype A[ ][ ], int a,b,c,d, datatype x)
//n*m矩阵A,行下标从a到b,列下标从c到d,本算法查找x是否在矩阵A中.
{i=a; j=d; flag=0; //flag是成功查到x的标志
while(i<=b && j>=c)
if(A[i][j]==x) {flag=1;break;}
else if (A[i][j]>x) j--; else i++;
if(flag) printf(“A[%d][%d]=%d”,i,j,x); //假定x为整型.
else prin
tf(“矩阵A中无%d 元素”，x)；
}算法search结束。
[算法讨论]算法中查找x的路线从右上角开始，向下（当x>A[i,j]）或向左（当x<A[i,j]）。向下最多是m，向左最多是n。最佳情况是在右上角比较一次成功，最差是在左下角（A[b,c]），比较m+n次，