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

Question

给出当我在整数数组中具有先序和中序遍历时输出树的后序遍历的代码。如何使用给定的中序和后序数组来类似地获取前序？

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]<<" ";
}

这是 preorder() 的原型

void preorder( int inorderorder[], int inostart, int postorder[], int poststart, int length)

使用 postorder() 它将输出，

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 数组中的绝对位置。您的函数可能会以负长度进行调用。
• 您的第二个递归函数对于转换边界和长度来说还很遥远。将其画在纸上并跟踪您的算法可能会有所帮助。

画出这棵树可能会有所帮助：

     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. 通过使用该索引，我们将确定 left 中作为根的元素。

   通过使用

4. 我们对右子树也是如此，主要思想是通过查找中序数组来确定左子树和右子树的索引。希望我说清楚了..

   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)
            返回 ; 
     char root = postorder[p_end];
     System.out.print(root);
     System.out.print("(");
       整数k=0；
         for(int i=0; i< inorder.length; i++){
             if(inorder[i]==root){
               k = 我；
               休息;
             }
         }
     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(")");    
   }
   

这是我的作业。感谢@Stephen 的好回答