首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假设二叉树采用二叉链表存储结构存储,设计一个算法,求先序遍历序列中第k(1≤k≤二叉树中结点个数)个结点的值,要求: 根据设计思想,采用C或C++语言描述算法,关键之处给出注释。
假设二叉树采用二叉链表存储结构存储,设计一个算法,求先序遍历序列中第k(1≤k≤二叉树中结点个数)个结点的值,要求: 根据设计思想,采用C或C++语言描述算法,关键之处给出注释。
admin
2018-07-17
31
问题
假设二叉树采用二叉链表存储结构存储,设计一个算法,求先序遍历序列中第k(1≤k≤二叉树中结点个数)个结点的值,要求:
根据设计思想,采用C或C++语言描述算法,关键之处给出注释。
选项
答案
算法的设计如下: int n=1; ElemType PreNode(BTNode *b,int k)( ElemType ch; if(b==NULL) return ’ ’; if(n==k) return b—>data; ++n; ch=PreNode(b—>ichild,k); if(ch!=’ ’) return ch; ch=PreNOde(b—>rchiid,k); return ch; } 若对递归不熟悉的同学也可以在二叉树的非递归先序遍历算法模型上进行修改,考虑到非递归算法的复杂性,考场上并不推荐使用非递归算法,既耗时又容易出错。相比之下,递归算法不仅简单,代码数量也较短,适宜在考场上使用。学有余力的同学可以自己再用非递归算法把这题再做一遍。 下面给出非递归算法的代码: #define MaxSize 100 int n=1; ElemType PreNode(BTNode *b,int k){ BTNode *st[MaxSize],*p; if(b!=NULL){ st[++top]=b; while(top>—1){ p=st[top一一]; ++n; if(n==k)return P—>data; if(p—>rchild)st[++top]=p—>rchild; //右子树进栈 if (p—>lchild)st[r++top]=p—>lchild; //左子树进栈 } } return’ ’; } 在统考中,二叉树的算法大多会围绕遍历这个知识点进行出题,考生务必掌握好三种遍历算法,并在基本算法的基础上学会简单的修改进而解决问题。
解析
转载请注明原文地址:https://kaotiyun.com/show/3yRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
战国初期,上党地区在下列哪一个国家的控制范围之内?()
《和平大使》一书中评述说:“英国的根本利益在于防止德国的崩溃,只要德国是一个统一的整体,欧洲就能或多或少地保持均势。”英国在下列哪些事件中的态度体现了上述原则()。①巴黎和会②国联成立③华盛顿会议
以下选项不属于希腊城邦的形成方式和途径的是()。
新文化运动中,把斗争矛头指向孔孟儒学的直接原因是()。
西汉末年,()对太初历作了系统的解释,并调整为三统历。这是中国第一部记载完整的历法。
宁夏回族自治区的设立时间是()。
巴黎和会上,英美主张把原德国在山东的权利转让给日本,华盛顿会议又表示支持中国让日本归还山东的要求,英美态度发生变化的根本原因是()。
中共中央在进行战略决战时,首先将矛头指向()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
在二叉树的顺序存储中,每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系,因此可与三叉链表对应。若某二叉树共有n个结点,采用三叉链表存储时,每个结点的数据域需要d个字节,每个指针域占用4个字节,若采用顺序存储,最后一个结点下标为k(起
随机试题
润滑油着火时宜用高压柱状水扑救,不可用砂土、酸碱、泡沫干粉及1211灭火器扑救。
催化以RNA为模板合成DNA的酶是催化以DNA为模板合成RNA的酶是
甲公司为从事石油化工及投资的大型企业。甲公司下属子公司乙公司于2007年在香港成功发行股票并上市。2010年9月乙公司购入总部位于英国的丙公司4.2%的股份。经过与丙公司的接触,乙公司认为,全面收购丙公司符合其长远发展目标。丙公司在尼日利亚的全资子公司是
儿童和青少年的健康成长离不开德育。()
【2015年辽宁特岗.单选】多元智能理论的提出者是()。
村里有两家因为宅基地问题发生械斗事件,你是村支书,如何处理?
Theriseofmultinationalcorporations(跨国公司),globalmarketing,newcommunicationstechnologies,andshrinkingculturaldifferen
温饱工程
实现程序可将磁盘中的一个文件复制到另一个文件中,两个文件的文件名在可执行命令的命令行中(相当于copy命令),假定文件在当前目录下。请补全程序。#include<stdio.h>voidmain(intargc,char*argv[])
Alllivingcreaturespassoninheritedtraitsfromonegenerationtoother.
最新回复
(
0
)