admin管理员组

文章数量:1531282

2024年7月25日发(作者：)

1、 二叉树的层次遍历序列的第一个结点是二叉树的根。实际上，层次

遍历序列中的每个结点都是“局部根”。确定根后，到二叉树的中序序

列中，查到该结点，该结点将二叉树分为“左根右”三部分。若左、右

子树均有，则层次序列根结点的后面应是左右子树的根；若中序序列中

只有左子树或只有右子树，则在层次序列的根结点后也只有左子树的根

或右子树的根。这样，定义一个全局变量指针R，指向层次序列待处理

元素。算法中先处理根结点，将根结点和左右子女的信息入队列。然

后，在队列不空的条件下，循环处理二叉树的结点。队列中元素的数据

结构定义如下：

typedef struct

{ int lvl; //层次序列指针，总是指向当前“根结点”在层

次序列中的位置

int l,h; //中序序列的下上界

int f; //层次序列中当前“根结点”的双亲结点的指针

int lr; // 1—双亲的左子树 2—双亲的右子树

}qnode;

BiTree Creat(datatype in[],level[],int n)

//由二叉树的层次序列level[n]和中序序列in[n]生成二叉树。 n是二

叉树的结点数

{if (n<1) {printf(“参数错误n”); exit(0);}

qnode s,Q[]; //Q是元素为qnode类型的队列，容量足够大

init(Q); int R=0; //R是层次序列指针，指向当前待处理的结点

BiTree p=(BiTree)malloc(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;

=++R; s.l=i+1; s.h=n-1; s.f=p; =2; enqueue(Q,s);

}

else if (i==n-1) //根结点无右子树，遍历序列的1—n-1是左子树

{p->rchild=null;

=++R; s.l=1; s.h=i-1; s.f=p; =1; enqueue(Q,s);

}

else //根结点有左子树和右子树

{=++R; s.l=0; s.h=i-1; s.f=p; =1;enqueue(Q,s);//左子

树有关信息入队列

=++R; s.l=i+1;s.h=n-1;s.f=p; =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[]) break;

p=(bitreptr)malloc(sizeof(binode)); //申请

结点空间

p->data=level[]; p->lchild=null; p->rchild=null; //

填写该结点数据

if (==1) father->lchild=p;

else father->rchild=p； //让双亲的子女指针指向该结点

if (i==s.l)

{p->lchild=null; //处理无左子女

=++R; s.l=i+1; s.f=p; =2; enqueue(Q,s);

}

else if (i==s.h)

{p->rchild=null; //处理无右子女

=++R; s.h=i-1; s.f=p; =1; enqueue(Q,s);

}

else{=++R; s.h=i-1; s.f=p; =1;

enqueue(Q,s);//左子树有关信息入队列

=++R; s.l=i+1; s.f=p; =2; enqueue(Q,s); //右子

树有关信息入队列

}

}//结束while (!empty(Q))

return(p);

}//算法结束

2、冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的

元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算

法。

48.有n个记录存储在带头结点的双向链表中，现用双向起泡排序法对其

按上升序进行排序，请写出这种排序的算法。（注：双向起泡排序即相

邻两趟排序向相反方向起泡）

本文标签： 结点序列队列二叉树

版权声明：本文标题：2013年贵州省JAVA最新版本章程 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/xitong/1721914320a904790.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。