如何輸出給定中序和後序遍歷的樹的前序遍歷？

Question

給定輸出樹的後序遍歷的代碼，當我有一個整數數組中的前序和inorder遍歷時。我如何同樣地獲得給定的inorder和postorder數組的前序？

void postorder(int preorder[], int prestart, int inorder[], int inostart, int length) 
{ 
    if(length==0) return; //terminating condition 
    int i; 
    for(i=inostart; i<inostart+length; i++) 
    if(preorder[prestart]==inorder[i])//break when found root in inorder array 
     break; 
    postorder(preorder, prestart+1, inorder, inostart, i-inostart); 
    postorder(preorder, prestart+i-inostart+1, inorder, i+1, length-i+inostart-1); 
    cout<<preorder[prestart]<<" "; 
} 

這裏是原型序（）

空隙序（INT inorderorder []，INT inostart，INT後序[]，INT開始後，INT長度）

使用後序（）這將是

int preorder[6]={6,4,1,5,8,9}; 
int inorder[6]={1,4,5,6,8,9}; 
postorder(preorder,0,inorder,0,6); 

出認沽將

1 5 4 9 8 6 

下面

是print_preorder（）不正確的代碼，仍然沒有工作如下

void print_preorder(int inorder[], int inostart, int postorder[], int poststart, int length) 
    { 
     if(length==0) return; //terminating condition 
     int i; 
     for(i=inostart; i<inostart+length; i++) 
     if(postorder[poststart+length-1]==inorder[i]) 
      break; 
     cout<<postorder[poststart+length-1]<<" "; 
     print_preorder(inorder, inostart , postorder, poststart, i-inostart); 
     print_preorder(inorder, inostart+i-poststart+1, postorder, i+1, length-i+inostart-1); 
    } 

Answer 1

下面是一些提示：

• 在postorder子陣的最後一個元素是你的新preorder根。
• inorder數組可以在新的preorder根的任一側分成兩部分。
• 您可以在這兩個inorder子陣列上遞歸調用print_preorder函數。
• 當調用print_preorder函數時，inorder和postorder數組將具有相同的大小。
• 你有一個越界陣列訪問：postorder[poststart+length]已經超過了數組的末尾。爲了得到最後一個元素，你想postorder[poststart+length-1]
• 你的第一個遞歸print_preorder函數選擇錯誤的長度。請記住length是子陣列的長度，但inostart是inorder陣列中的絕對位置。您的功能可能會調用負面的length。
• 你的第二個遞歸函數對於翻譯邊界和長度是相當遙遠的。這可能有助於將其繪製在紙上並跟蹤您的算法。

它可能有助於繪製樹：

 6 
/ \ 
    4  8 
/\  \ 
1 5  9 

然後寫出三個遍歷：

// index:   0 1 2 3 4 5 
int postorder[6]={1,5,4,9,8,6}; 
int inorder[6]= {1,4,5,6,8,9}; 
int preorder[6]= {6,4,1,5,8,9}; 

現在，放下電腦，拿出一支筆&紙和認爲關於這個問題:)

想象一下這個調用堆棧（新根印在左起）：

6 print_preorder(len=6, in=[1 4 5 6 8 9], post=[1 5 4 9 8 6]) 
4 |-> print_preorder(len=3, in=[1 4 5], post=[1 5 4]) 
1 | |-> print_preorder(len=1, in=[1], post=[1]) 
    | | |-> print_preorder(len=0, in=[], post=[]) 
    | | |-> print_preorder(len=0, in=[], post=[]) 
5 | |-> print_preorder(len=1, in=[5], post=[5]) 
    |  |-> print_preorder(len=0, in=[], post=[]) 
    |  |-> print_preorder(len=0, in=[], post=[]) 
8 |-> print_preorder(len=2, in=[8 9], post=[9 8]) 
     |-> print_preorder(len=0, in=[], post=[]) 
9  |-> print_preorder(len=1, in=[9], post=[9]) 
      |-> print_preorder(len=0, in=[], post=[]) 
      |-> print_preorder(len=0, in=[], post=[]) 

祝你好運:)

Answer 2

1. 在職務序列的最後一個元素將是樹的根。

2. 之後，我們將看Inorder數組來確定根的位置。數組左側是左側子樹，右側是右側子樹。

3. 通過使用該索引我們將確定左側的元素是根。

4. 同樣我們爲右子樹做決定，主要思想是通過查看inorder數組來確定左子樹和右子樹的索引。希望我是清楚的..

   public static void printpreorder(char []inorder,int i_start,int i_end,char[] postorder,int p_start,int p_end) 
   { 
       if(i_start > i_end || p_start > p_end) 
        return ; 
       char root = postorder[p_end]; 
       System.out.print(root); 
       System.out.print("("); 
       int k=0; 
        for(int i=0; i< inorder.length; i++){ 
         if(inorder[i]==root){ 
         k = i; 
         break; 
         } 
        } 
       printpreorder(inorder, i_start, k-1, postorder, p_start, p_start+k-(i_start+1)); 
       System.out.print(")("); 
       printpreorder(inorder, k+1, i_end, postorder, p_start+k-i_start, p_end-1); 
       System.out.print(")");  
   } 
   

這是hommework我。感謝@Stephen的一個很好的答案