问答题 假设一维数组研1:n]存放森林F的每个结点的地址,且序列H[1],H[2],…,H[n]正好是森林F在先根次序下结点地址的排列;E[1:n]是一维数组,且当1≤i≤n时,E[i]是H[i]所指结点的次数(即儿子结点的个数)。试给出一个算法,该算法计算森林F的树形个数,并计算森林F的最后一个树形的根结点地址。【吉林大学1995五(15分)】
【正确答案】正确答案:森林在先根次序遍历时,首先遍历第一棵子树的根,接着是第一棵子树的结点;之后是第二棵树,……,直到最后一棵树。前序序列中每棵树的结点连续存放,不会丢掉一个结点,也不会插入其他树上的一个结点。本题中E[i]是H[i]所指结点的次数,就是结点的分支个数B,而分支数B与树的结点数Ⅳ的关系是N=B+1(除根结点外,任何一个结点都有一个分支所指)。所以,从E[i]的第一个单元开始,将值累加,当累加到第i个单元,其值正好等于i一1时,就是第一棵树。接着,用相同方法,将其他树分开,进行到第n个单元,将所有树分开。例如,上面应用题第51题(2)的森林可按本题图示如下。从左往右将次数加到下标8(=B+1)时,正好结束第一棵树。
【答案解析】