首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假定用两个一维数L[N]和R[N]作为有N个结点l,2,…,N的二叉树的存储结构。L[i]和R[i]分别指示结点i的左儿子和右儿子;L[i]=0(R[i]=0)表示i的左(右)儿子为空。试写一个算法,由L和R建立一个一维数组T[n],使T[i]存放结点i的
假定用两个一维数L[N]和R[N]作为有N个结点l,2,…,N的二叉树的存储结构。L[i]和R[i]分别指示结点i的左儿子和右儿子;L[i]=0(R[i]=0)表示i的左(右)儿子为空。试写一个算法,由L和R建立一个一维数组T[n],使T[i]存放结点i的
admin
2019-08-15
93
问题
假定用两个一维数L[N]和R[N]作为有N个结点l,2,…,N的二叉树的存储结构。L
和R
分别指示结点i的左儿子和右儿子;L
=0(R
=0)表示i的左(右)儿子为空。试写一个算法,由L和R建立一个一维数组T[n],使T
存放结点i的父亲;然后再写一个判别结点U是否为结点V的后代的算法。
选项
答案
由指示结点i左儿子和右儿子的两个一维数组L[i]和R[i],很容易建立指示结点i的双亲的一维数组T[i],根据T数组,判断结点U是否是结点V后代的算法转为判断结点V是否是结点U的祖先的问题。 int Generation(int U,V,N,L[],R[],T[]){ //L[]和R[]是含有N个元素且指示二叉树结点i左儿子和右儿子的一维数组 //本算法据此建立结点i的双亲数组T,并判断结点U是否是结点V的后代 int i; for(i=1:i<=N;i++)T[i]:0; //T数组初始化 for(i=1;i<=N;i++) //根据L和R填写T if(L[i]!=0)T[L[i]]=i; //若结点i的左子女是L,则结点L的双亲是结点i for(i=1;i<=N;i++) if(R[i]!=0)T[R[i]]=i; //i的右子女是R,则R的双亲是i int parent=U; //判断U是否是V的后代 while (parent!=V&&parent!=0)parent=T[parent]; if(parent==V){printf(”结点u是结点V的后代”);return(1);} else{ printf(”结点U不是结点V的后代”);return(0);{ }//结束Generation
解析
转载请注明原文地址:https://kaotiyun.com/show/QcCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列哪两个国家是第二次工业革命的发源地和“中心”?
制瓷业是光彩夺目的一个手工业部门,北宋的制瓷业的重心在黄河流域和中原地区。回答问题:()创于唐,盛于北宋,以白瓷著名,为宋代印花白瓷的精品
关于一战后构筑的凡尔赛体系,说法不正确的是()。
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(logn)的算法,确定树中第k个结点的位置。
若有4个进程共享同一程序段,每次允许3个进程进入该程序段,用P、V操作作为同步机制,则信号量S的取值范围是()。
指令系统字长16位,每个地址码为6位,采用扩展操作码的方式,试设计14条二地址指令,100条一地址指令,100条零地址指令。(1)画出操作码的扩展形式。(2)下图为指令译码逻辑图,其中只给出了二地址指令的译码逻辑,试补全一地址指令和零地址指令的
设一段正文由字符集{A,B,C,D,E,F)中的字母组成,这6个字母在正文中出现的次数分别为{12,18,26,6,4,34)。(1)为这6个编码设计哈夫曼编码。(2)设每个字节由8位二进制位组成,试计算按哈夫曼编码压缩存储这段正文共需多少个字
有两部计算机M1和M2,指令系统相同。它们的操作频率频率分别是400MHz和200MHz。指令分成A、B和C三类,在M1上执行分别需4、6和8个周期;在M2上执行分别需2、4和3个周期。现有一程序在两机器上执行,其中A、B和C三类指令依次占30%、50
设一棵二叉树是由森林转换而来的,若森林中有n个非终端结点,则二叉树中无右孩子的结点个数为()。
假设程序PA和PB单独执行时所需的时间分别用TA和TB表示,并且假设TA=1h,TB=1.5h,其中处理器工作时间分别为TA=18min,TB=27min,如果采用多道程序设计方法,让PA和PB并行工作,假定处理器利用率达到50%,系统开销为15
随机试题
根据我国《民法通则》的规定,18周岁以上的公民是成年人,具有完全民事行为能力,可以独立进行民事活动,是()
“流行”散谈(其二)“流行”在运动的过程中,有时也会回过头来看一看。流行不是天降之物。流行的源头是传统。没有源头,哪来潮头?无“源”无“根”的事物不可能存在。流行是传统的变异。任何能够称为传统的事物,在时代的演变中都要经受现实的检验。经典传统在与时代
患者一侧瞳孔散大,最可能是【】
蛋白质的变性是由于
企业内部资源可以分为()资源。
防腐蚀涂层施工采用的刷涂是最简单的手工涂装方法,优点很多,但其缺点是劳动强度大、工作效率低和()。
根据《浙江省导游人员管理办法》规定,()导游证件的,责令改正,并可处1000元以上2000元以下的罚款。
一、注意事项1.本题本由给定资料与作答要求两部分构成,考试时限为150分钟。其中,阅读给定资料参考时限为40分钟,作答参考时限为110分钟。2.请在题本、答题卡指定位置上用黑色字迹的钢笔或签字笔填写自己的姓名和准考证号,并用2B铅笔在准
愚公移山:郑人买履
Whichofthefollowingbestexplainsthemeaningof"Shallwebuytheticketsfirst"?
最新回复
(
0
)