2011年贵州省数据整理要领
更新时间:2023-05-17 20:16:01 阅读量: 实用文档 文档下载
- 贵州省大数据推荐度:
- 相关推荐
2011年贵州省数据整理要领
1、请设计一个算法,要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表,表头指针为head。 二叉树按二叉链表方式存储,链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。
2、给出折半查找的递归算法,并给出算法时间复杂度性分析。
3、请设计一个算法,要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表,表头指针为head。 二叉树按二叉链表方式存储,链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。
4、 二叉树的层次遍历序列的第一个结点是二叉树的根。实际上,层次遍历序列中的每个结点都是“局部根”。确定根后,到二叉树的中序序列中,查到该结点,该结点将二叉树分为“左根右”三部分。若左、右子树均有,则层次序列根结点的后面应是左右子树的根;若中序序列中只有左子树或只有右子树,则在层次序列的根结点后也只有左子树的根或右子树的根。这样,定义一个全局变量指针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<n; 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);
}
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++)
2011年贵州省数据整理要领
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);
}//算法结束
正在阅读:
2011年贵州省数据整理要领05-17
公治853号 公安部《行政主管部门移送适用行政拘留环境违法案件暂行办法》12-09
《公路工程计量与计价》课程设计大纲、任务书和指导书01-14
亨通集团公司精益变革案例分享(文章)06-10
大浪知识12-19
领导干部年度考核工作总结范文202208-02
湿地实习报告06-28
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- 贵州省
- 要领
- 整理
- 数据
- 2011
- Oracle_Cloud_Computing_甲骨文云计算讨论
- 2015公务员考试逻辑判断习题精解(6)
- 民营中小企业内部会计控制刍议
- 附录1 论文格式示例(20150316)
- 2012年全国各地中考数学解析汇编16 平面直角坐标系
- 3333A2N连续流双泥系统反硝化除磷脱氮试验研究
- 初发2型糖尿病胰岛素泵强化治疗的观察及护理
- 惠州一中2013-2014学年度七年级下学期期中考试数学试卷
- 敬老院之暑期实践活动总结
- 我国中小板上市公司高管薪酬影响因素的实证研究
- 全国各区划分及地级市
- 青岛市(高压电工)培训和考核大纲
- 第3章 五笔字型输入法基础
- 医疗检验委托协议书
- 小型局域网组建毕业论文
- 关于开展尊老敬老活动的倡议书
- 北京地铁八号线二期工程鼓楼大街站主体结构
- 消息类新闻分析《新闻30分》
- “失眠”抑郁症治疗方法
- IT企业销售管理制度