首页 > 2013年甘肃省数据概述入门

2013年甘肃省数据概述入门

发布时间：来源：文档文库

小中大

字号：

手机查看

1、请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink-rlink法存储。2、根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre（初值为null）和全局变量flag，初值为true。若非二叉排序树，则置flag为false。#definetrue1#definefalse0typedefstructnode
{datatypedata;structnode*llink,*rlink;}*BTree;voidJudgeBST（BTreet,intflag）
//判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。{if（t!=null&&flag）
{Judgebst（t->llink,flag）；//中序遍历左子树
if（pre==null）pre=t；//中序遍历的第一个结点不必判断
elseif（pre->datadata）pre=t；//前驱指针指向当前结点else{flag=flase；}//不是完全二叉树Judgebst（t->rlink,flag）；//中序遍历右子树}//JudgeBST算法结束
3、二叉树的层次遍历序列的第一个结点是二叉树的根。实际上，层次遍历序列中的每个结点都是“局部根”。确定根后，到二叉树的中序序列中，查到该结点，该结点将二叉树分为“左根右”三部分。若左、右子树均有，则层次序列根结点的后面应是左右子树的根；若中序序列中只有左子树或只有右子树，则在层次序列的根结点后也只有左子树的根或右子树的根。这样，定义一个全局变量指针R，指向层次序列待处理元素。算法中先处理根结点，将根结点和左右子女的信息入队列。然后，在队列不空的条件下，循环处理二叉树的结点。队列中元素的数据结构定义如下：typedefstruct
{intlvl;//层次序列指针，总是指向当前“根结点”在层次序列中的位置intl,h;//中序序列的下上界
intf;//层次序列中当前“根结点”的双亲结点的指针intlr;//1—双亲的左子树2—双亲的右子树}qnode;
BiTreeCreat(datatypein[],level[],intn
//由二叉树的层次序列level[n]和中序序列in[n]生成二叉树。n是二叉树的结点数{if(n<1{printf(“参数错误\n”;exit(0;}
qnodes,Q[];//Q是元素为qnode类型的队列，容量足够大init(Q;intR=0;//R是层次序列指针，指向当前待处理的结点BiTreep=(BiTreemalloc(sizeof(BiNode;//生成根结点p->data=level[0];p->lchild=null;p->rchild=null;//填写该结点数据
for(i=0;i在中序序列中查找根结点，然后，左右子女信息入队列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;

}
elseif(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=(bitreptrmalloc(sizeof(binode;//申请结点空间
p->data=level[s.lvl];p->lchild=null;p->rchild=null;//填写该结点数据if(s.lr==1father->lchild=p;
elsefather->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;}
elseif(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(Qreturn(p;}//算法结束

本文来源：https://www.2haoxitong.net/k/doc/2e1f4ca0eff9aef8941e06cb.html