首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
假定用两个一维数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
45
问题
假定用两个一维数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
学硕统考专业
相关试题推荐
近现代以来,国际关系中先后出现了维也纳体系、凡尔赛一华盛顿体系和雅尔塔体系。关于这三个体系共同点的表述不正确的是()。
制瓷业是光彩夺目的一个手工业部门,北宋的制瓷业的重心在黄河流域和中原地区。回答问题:()创于唐,盛于北宋,以白瓷著名,为宋代印花白瓷的精品
明清时期专制主义空前加强,据此回答问题:清代在散文方面,声势最大、影响最广的是桐城派,不属于该派的是()
试编写一个非递归算法,实现求以二叉链表存储的二叉树中q结点的祖先。
分时系统里,在条件相同的情况下,通常KLT(内核级线程)比ULT(用户级线程)得到更多的CPU时间,请简要解释之。
荷兰国旗问题:设有一个仅红、白、蓝三种颜色的条块组成的条块序列,请编写一个时间复杂度为O(n)的算法,使得这些条块按红、白、蓝的顺序排好,即排成荷兰国旗图案。
若线性表最常用的运算是查找第i个元素及其前驱的值,则采用()存储方式节省时间。
已知在二叉树中,T为根结点,*p和*q为二叉树中两个结点,试编写求距离它们最近的共同祖先的算法。
测量控制系统中的数据采集任务把所采集的数据送一个单缓冲区,计算任务从该单缓冲区中取出数据进行计算。试写出利用信号量机制实现两者共享单缓冲区的同步算法。
某多道程序设计系统配有一台处理器和两台外设IO1、IO2,现有3个优先级由高到低的J1、J2、J3都已装入了主存,它们使用资源的先后顺序和占用时间分别是:J1:IO2(30ms),CPU(10ms);IO1(30ms),CPU(10ms)
随机试题
Heknowslittleofmathematics,and______ofchemistry.
下列哪种细菌不是引起全身性感染常见的致病菌()
A.卵巢B.肝C.输尿管D.子宫E.胆囊属于腹膜外位器官的是
甲长期贩卖毒品,乙经常吸食毒品。乙经常从甲处购买毒品以供自己吸食。现有如下事实:事实一:甲将自己购进的毒品以低于成本的价格卖给乙,乙购买后在家中吸食,由于吸食过量而死亡:事实二:乙以低于成本价的价格从甲处购买了大量毒品(1公斤海洛因)供
干作业成孔灌注桩的孔底虚土层厚度,相关规范标准规定为()。
对于严格控制火源和各种易燃、易爆物品的管理正确的是()。
评析义和团运动失败的原因及其历史意义。
设二元函数f(x,y)=|x-y|φ(x,y),其中φ(x,y)在点(0,0)处的某邻域内连续.证明:函数f(x,y)在点(0,0)处可微的充分必要条件是φ(0,0)=0.
IP地址块202.113.79.128/27、202.113.79.160/27和202.113.79.192/27经过聚合后可用的地址数为()。
Christmasisthetimetomakethebelovedonesfeelspecial.Ahugandakisswouldprobablybemorethanenoughbutgiftsare
最新回复
(
0
)