else 四、应用题(本题共28分) 树的后根遍历方法是:若树非空则(4分) (1)依据次后根遍历根的各个子树T1,T2, (2)访问根结点 对下图所示的树,用后根遍历方法进行遍历,请写出遍历所得到的结点访问序列 2.将下图的森林转换为二叉树。(4分) 3.下图表示一个地区的交通网,顶点表示城市,边表示连结城市间的公路,边上的权表示 修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的n-1条公路,画出所 有可能的方案。(4分) 4.已知一个无向图的邻接表如下图所示。(本题4分,每小题2分) 2V2 4 3V3 2 5V53 else_________; } 四、 应用题（本题共２８分） 1．树的后根遍历方法是：若树非空则（４分） （1）依据次后根遍历根的各个子树Ｔ１，Ｔ２，……Ｔm; （2）访问根结点。 对下图所示的树，用后根遍历方法进行遍历，请写出遍历所得到的结点访问序列。 2. 将下图的森林转换为二叉树。（４分） 3. 下图表示一个地区的交通网，顶点表示城市，边表示连结城市间的公路，边上的权表示 修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的 n-1 条公路，画出所 有可能的方案。（４分） 4．已知一个无向图的邻接表如下图所示。（本题４分，每小题２分） A B A C A D A E A F A G A H A I J K A A B A C A D A E A F A G A I J v2 v4 v1 v5 v6 v3 16 21 11 33 14 19 6 18 6 5 V5 V1 V2 V3 V4 1 1 2 3 4 5 2 5 4 3 3 4 4 5 2 2 1 Λ Λ Λ Λ Λ