【题09】按照先根次序和后根次序遍历普遍有序树--试题解析

《【题09】按照先根次序和后根次序遍历普遍有序树--试题解析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、【题9】按照先根次序和后根次序遍历普遍有序树输入一棵普通有序树，输出该树的先根次序和后根次序。输入：顶点个数n（1≤n≤200）以下含n行，其中第i行（1≤i≤n）的元素依次为结点i的数据值ai。以后各元素为结点i的儿子序列，以0结束。若ai后仅含一个0，则说明结点i为叶子。例如对于下图（ａ）的多叉树对应的输入信息为18’r’2340’a’560’b’70’c’89100’w’0’x’11120’f’0’s’13140’t’000’u’0’’d’150’e’0’i’1617180’j’0’h’0’m’0

2、’o’0’h’0输出：两行，分别为普通有序树的先根次序和后根次序分析：“四、树或森林转换成二叉树”一节中介绍了普通有序树转换成二叉树的规则。我们在输入普通有序树的同时，按照规则进行转换：fillchar（tree，sizeof（tree），0）；{二叉树初始化}readln(n)；{读入普通有序树的结点个数}fori←1tondo{依次读入普通有序树中每个结点的信息}beginread(tree[i]．data)；　read(j)；{读结点i的第一个儿子序号j}　ifj<>0then{若结点j非叶子}b

3、egintree[i]．lch←j；tree[j]．prt←i；{结点j作为结点i的左儿子}p←j；{从结点j出发转换其它兄弟结点}repeat　read(j)；{读结点i的下一个儿子序号j}ifj<>0thenbegintree[p]．rch←j；tree[j]．prt←p；{结点j作为结点p的右儿子}p←j；end；{then}untilj=0；{直至处理完结点i的所有儿子信息}end；{then}writeln；{准备输入结点i+1的儿子信息}end；{for}上述转换算法的时间复杂度为W（n2）

4、。例如下图图（ａ）的普通有序树经转换运算后得出的tree数组如下Dataprtlchrch1’r’0202’a’1533’b’2744’c’3805’w’2066’x’51107’f’3008’s’4099’t’801010’u’90011’d’6151212’e’110013’i’8161414’j’130015’h’110016’m’1301717’o’1601818’n’1700该数组正好对应图（b）的二叉树。在得出二叉树tree后，我们分别调用过程preorder(1)和过程inorder(1)

5、，对其进行前序遍历和中序遍历，得出普通有序树的先根次序和后根次序。由此得出主程序输入普通有序树并转换成二叉树tree；preorder(1)；{对二叉树tree进行前序遍历}inorder(1)；{对二叉树tree进行中序遍历}