《【题09】按照先根次序和后根次序遍历普遍有序树--试题解析》由会员分享，可在线阅读，更多相关《【题09】按照先根次序和后根次序遍历普遍有序树--试题解析（3页珍藏版）》请在金锄头文库上搜索。
1、【题 9】按照先根次序和后根次序遍历普遍有序树输入一棵普通有序树，输出该树的先根次序和后根次序。输入：顶点个数 n（1n200）以下含 n 行，其中第 i 行（1 i n）的元素依次为结点 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 依次读入普通有序树中每个结点的信息beginread(treei data)；read(j)； 读结点 i 的第一个儿子序号 jif j0 then begintreeprch j ；treejprtp； 结点 j 作为结点 p 的右儿子pj；end；thenuntil j=0； 直至处理完结点 i 的所有儿子信息end
3、；thenwriteln； 准备输入结点 i+1 的儿子信息end；for上述转换算法的时间复杂度为 W（n 2） 。例如下图图（）的普通有序树经转换运算后得出的 tree 数组如下Data prt lch rch1 r 0 2 02 a 1 5 33 b 2 7 44 c 3 8 05 w 2 0 66 x 5 11 07 f 3 0 08 s 4 0 99 t 8 0 1010 u 9 0 011 d 6 15 1212 e 11 0 013 i 8 16 1414 j 13 0 015 h 11 0 016 m 13 0 1717 o 16 0 1818 n 17 0 0该数组正好对应图（b）的二叉树。在得出二叉树 tree 后，我们分别调用过程 preorder(1)和过程 inorder(1)，对其进行前序遍历和中序遍历，得出普通有序树的先根次序和后根次序。由此得出主程序输入普通有序树并转换成二叉树 tree；preorder(1)； 对二叉树 tree 进行前序遍历inorder(1)； 对二叉树 tree 进行中序遍历
