題09按照先根次序和后根次序遍歷普遍有序樹(shù)試題解析

1、【題9】按照先根次序和后根次序遍歷普遍有序樹(shù)輸入一棵普通有序樹(shù)，輸出該樹(shù)的先根次序和后根次序。輸入：頂點(diǎn)個(gè)數(shù)n（1n200）以下含n行，其中第i行（1in）的元素依次為結(jié)點(diǎn)i的數(shù)據(jù)值ai。以后各元素為結(jié)點(diǎn)i的兒子序列，以0結(jié)束。若ai后僅含一個(gè)0，則說(shuō)明結(jié)點(diǎn)i為葉子。例如對(duì)于下圖（）的多叉樹(shù)對(duì)應(yīng)的輸入信息為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輸出：兩行，分別為普通有序樹(shù)的先根次序和后根次序分析：“四、樹(shù)或森林轉(zhuǎn)換成二叉樹(shù)”一

2、節(jié)中介紹了普通有序樹(shù)轉(zhuǎn)換成二叉樹(shù)的規(guī)則。我們?cè)谳斎肫胀ㄓ行驑?shù)的同時(shí)，按照規(guī)則進(jìn)行轉(zhuǎn)換： fillchar（tree，sizeof（tree），0）； 二叉樹(shù)初始化 readln(n)； 讀入普通有序樹(shù)的結(jié)點(diǎn)個(gè)數(shù)for i1to n do 依次讀入普通有序樹(shù)中每個(gè)結(jié)點(diǎn)的信息 begin read(treeidata)；read(j)； 讀結(jié)點(diǎn)i的第一個(gè)兒子序號(hào)jif j<>0 then 若結(jié)點(diǎn)j非葉子begin treeilchj；treejprti； 結(jié)點(diǎn)j 作為結(jié)點(diǎn)i的左兒子 pj； 從結(jié)點(diǎn)j 出發(fā)轉(zhuǎn)換其它兄弟結(jié)點(diǎn) repeat read(j)； 讀結(jié)點(diǎn)i的下一個(gè)兒子序號(hào)j if

3、 j<>0 then begin treeprchj；treejprtp； 結(jié)點(diǎn)j 作為結(jié)點(diǎn)p的右兒子 pj； end；then until j=0； 直至處理完結(jié)點(diǎn)i的所有兒子信息end；thenwriteln； 準(zhǔn)備輸入結(jié)點(diǎn)i+1的兒子信息end；for上述轉(zhuǎn)換算法的時(shí)間復(fù)雜度為W（n2）。例如下圖圖（）的普通有序樹(shù)經(jīng)轉(zhuǎn)換運(yùn)算后得出的tree數(shù)組如下Dataprtlchrch1r0202a1533b2744c3805w2066x51107f3008s4099t801010u90011d6151212e110013i8161414j130015h110016m1301717o1601818n1700該數(shù)組正好對(duì)應(yīng)圖（b）的二叉樹(shù)。在得出二叉樹(shù)tree后，我們分別調(diào)用過(guò)程preorder(1)和過(guò)程inorder(1)，對(duì)其進(jìn)行前序遍歷和中序遍歷，得出普通有序樹(shù)的先根次序和后根次序。由此得出主程序輸入普通有序樹(shù)并轉(zhuǎn)換成二叉樹(shù)tree