《【题09】按照先根次序和后根次序遍历普遍有序树--试题解析.doc》由会员分享，可在线阅读，更多相关《【题09】按照先根次序和后根次序遍历普遍有序树--试题解析.doc（3页珍藏版）》请在金锄头文库上搜索。
1、【题9】按照先根次序和后根次序遍历普遍有序树输入一棵普通有序树，输出该树的先根次序和后根次序。输入：顶点个数n（1n200）以下含n行，其中第i行（1in）的元素依次为结点i的数据值ai。以后各元素为结点i的儿子序列，以0结束。若ai后仅含一个0，则说明结点i为叶子。例如对于下图（）的多叉树对应的输入信息为18r 2 3 4 0a 5 6 0b 7 0c 8 9 10 0w 0x 11 12 0f 0s 13 14 0t 0 0 0u 0 d 15 0e 0i 16 17 18 0j 0h 0m 0o 0h 0输出：两行，分别为普通有序树的先根次序和后根次序分析：“四、树或森林转换成二叉树”一
2、节中介绍了普通有序树转换成二叉树的规则。我们在输入普通有序树的同时，按照规则进行转换： fillchar（tree，sizeof（tree），0）； 二叉树初始化 readln(n)； 读入普通有序树的结点个数for i1to n do 依次读入普通有序树中每个结点的信息 begin read(treeidata)；read(j)； 读结点i的第一个儿子序号jif j0 then 若结点j非叶子begin treeilchj；treejprti； 结点j 作为结点i的左儿子 pj； 从结点j 出发转换其它兄弟结点 repeat read(j)； 读结点i的下一个儿子序号j if j0 then
3、 begin treeprchj；treejprtp； 结点j 作为结点p的右儿子 pj； end；then until j=0； 直至处理完结点i的所有儿子信息end；thenwriteln； 准备输入结点i+1的儿子信息end；for上述转换算法的时间复杂度为W（n2）。例如下图图（）的普通有序树经转换运算后得出的tree数组如下Dataprtlchrch1r0202a1533b2744c3805w2066x51107f3008s4099t801010u90011d6151212e110013i8161414j130015h110016m1301717o1601818n1700该数组正好对应图（b）的二叉树。在得出二叉树tree后，我们分别调用过程preorder(1)和过程inorder(1)，对其进行前序遍历和中序遍历，得出普通有序树的先根次序和后根次序。由此得出主程序输入普通有序树并转换成二叉树tree；preorder(1)； 对二叉树tree进行前序遍历inorder(1)； 对二叉树tree进行中序遍历
