假定用两个一维数组L[N]和R[N]作为有N个结点1 2 … N的二元树的存储结构。L[i]和R[i]分别指示结点i
结点,数组,假定
已帮助 人
假定用两个一维数组L[N]和R[N]作为有N个结点1，2，…，N的二元树的存储结构。L[i]和R[i]分别指示结点i的左儿子和右儿子；L[i]=O(R[i]=0)表示i的左(右)儿子为空。试写一个算法，由L和R建立一个一维数组T[b]，使T[i]存放结点i的父亲；然后再写一个判别结点U是否为结点V的后代的算法。【哈尔滨工业大学1999七(14分)】【华南师范大学2000六(17分)】
请帮忙给出正确答案和分析，谢谢！
热搜：古诺模型n个企业均衡
-
正确答案：由指示结点i左儿子和右儿子的两个一维数组L[i]和R[i]建立指示结点i的双亲的一维数组T[i]根据T数组判断结点U是否是结点V后代的算法转为判断结点V是否是结点U的祖先的问题。核心语句段如下： for(i=i ； i<=N； i++)T[i]=0； ／／T数组初始化 for(i=1；i<=N；i++) if(L[i]!=0)T[L[i]]=i ； ／／结点i的左子女是L则结点L的双亲是结点i for(i=1i<=N；i++) if(R Ci]!=0
由指示结点i左儿子和右儿子的两个一维数组L[i]和R[i],建立指示结点i的双亲的一维数组T[i],根据T数组,判断结点U是否是结点V后代的算法,转为判断结点V是否是结点U的祖先的问题。核心语句段如下：for(i=i；i<=N；i++)T[i]=0；／／T数组初始化for(i=1；i<=N；i++)if(L[i]!=0)T[L[i]]=i；／／结点i的左子女是L,则结点L的双亲是结点ifor(i=1,i<=N；i++)if(RCi]!=0