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

[题目分析]森林在先根次序遍历时首先遍历第一棵子树的根接着是第一棵子树的结点之后是第二棵树……最后一棵树本题中E[i]是H[i]所指结点的次数次数就是结点的分支个数B而分支数B与树的结点数N的关系是N=B+（除根结点外任何一个结点都有一个分支所指）所以从E[i]的第一个单元开始将值累加当累加到第i个单元其值正好等于i时就是第一棵树接着用相同方法将其它树分开进行到第n个单元将所有树分开例如上面应用题第题()的森林可按本题图示如下从左往右将次数加到下标（=B+）时正好结束第一棵树

void Forest(ElemType H[]int E[]intn)

// H[i]是森林F在先根次序下结点的地址排列E[i]是H[i]所指结点的次数本算法计算森林

//F的树形个数并计算森林F的最后一个树形的根结点地址

{int i=sum=j=m=; //sum记一棵树的分支数j记树的棵数m记一棵树的结点数

int tree[]; //tree记每棵树先序遍历最后一个结点在H[i]中的地址

while (i<=n) //n是森林中结点个数题目已给出

{sum+=E[i]; m++;

if (sum+==m && i<=n) //记树先序最后结点的地址为下步初始化

{sum=; m=; tree[++j]=i;}

i++;

}//while

if (j==)return (); //只有一棵树时第一个结点是根

else return(tree[j]+)

}//forest

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