#16541:


freedom501999@gmail.com (帥氣魔方生)

學校 : 不指定學校
編號 : 88611
來源 : [39.8.203.54]
最後登入時間 :
2019-05-30 22:56:25
c126. 00536 - Tree Recovery -- UVa536 | From: [110.28.110.140] | 發表日期 : 2019-01-12 20:17

一開始看到題目以為要建立樹,但仔細想一下後發現

既然從前序跟中序可以拆解出樹的樣子,不如以拆解字串的方式,藉由遞迴來進行後序走訪

因為後序是 左 - 右 - 樹根,所以先找出樹根,將字串拆成左右,往左遞迴到剩下一個節點印出,再往右遞迴,最後才印根

C 的處理,首先在全域宣告字元陣列,然後讀入字串後跑函式,只要傳遞前序跟中序的指標及字串長度即可

跑遞迴傳指標時要注意當前字串的開頭,以免傳錯而發生錯誤

虛擬碼如下

後序遞迴函式 (  前序字串開頭指標 , 中序字串開頭指標 , 字串長度 )
{
      樹根 = 前序第一個字母
      left 是左子樹長度、right 是右子樹長度
      while ( 樹根 != 中序指標取值)  
            左子樹長度加一
      if ( left > 0 ) 
            遞迴 函式 ( 前序加一 , 中序 ,  left );
      else if( 字串長度 == 1 ) /* 當前樹只剩一個節點 */
            印出節點
      right = 字串長度 - left -1 ;  /* 要扣掉樹根,所以長度要減一 */ 
      if ( right > 0 ) 
            遞迴 函式 ( 前序 + left+1 , 中序 + left+1 , right );
      if ( 字串長度 > 1 )  /* 左右子樹都印完才印樹根 */
            印出樹根
}
 
ZeroJudge Forum