数据结构考研分类复习真题 第六章 答案 (五)[4]

．[题目分析]当森林（树）以孩子兄弟表示法存储时若结点没有孩子（fch=null）则它必是叶子总的叶子结点个数是孩子子树（fch）上的叶子数和兄弟（nsib）子树上叶结点个数之和

typedef struct node

{ElemType data;//数据域

struct node *fch *nsib;//孩子与兄弟域 }*Tree;

int Leaves (Tree t)

//计算以孩子兄弟表示法存储的森林的叶子数

{if(t)

if(t>fch==null) //若结点无孩子则该结点必是叶子

return(+Leaves(t>nsib)); //返回叶子结点和其兄弟子树中的叶子结点数

else return (Leaves(t>fch)+Leaves(t>nsib)); //孩子子树和兄弟子树中叶子数之和

}//结束Leaves

．[题目分析]由指示结点i 左儿子和右儿子的两个一维数组L[i]和R[i]很容易建立指示结点i 的双亲的一维数组T[i]根据T数组判断结点U是否是结点V后代的算法转为判断结点V是否是结点U的祖先的问题

int Generation (int UVNL[]R[]T[])

//L[]和R[]是含有N个元素且指示二叉树结点i左儿子和右儿子的一维数组

//本算法据此建立结点i的双亲数组T并判断结点U是否是结点V的后代

{for(i=;i<=N;i++) T[i]=; //T数组初始化

for (i=;i<=N;i++) //根据L和R填写T

if(L[i]!=) T[L[i]]=i; //若结点i的左子女是L则结点L的双亲是结点i

for(i=;i<=N;i++)

if (R[i]!=) T[R[i]]=i; //i的右子女是r则r的双亲是i

int parent=U; //判断U是否是V的后代

while (parent!=V && parent!=) parent=T[parent];

if (parent==V){printf(结点U是结点V的后代);return();}

else{ printf(结点U不是结点V 的后代);return();}

}结束Generation

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []