如何输出给定中序和后序遍历的树的前序遍历？

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的一个很好的答案