2. 考研
  3. 假定用两个一维数组L[N]和R[N]作为有N个结点1，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个结点1，2，…，N的二叉树的存储结构。L[i]和R[i]分别指示结点i的左儿子和右儿子；L[i]=0(R[i]=0)表示i的左(右)儿子为空。试写一个算法，由L和R建立一个一维数组T[n]，使T[i]存放结点i

admin2019-01-16  103
问题 假定用两个一维数组L[N]和R[N]作为有N个结点1，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 Gener|ation(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/kiRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)