给定的顺序和后序tranversal如何输出树的前序遍历？ [英] How do I output the preorder traversal of a tree given the inorder and postorder tranversal?

问题描述

给定用于在我有一个整数数组中的preorder和inorder遍历时输出树的后序遍历的代码。我们如何类似地获得给定的inorder和postorder数组的前序。

  void postorder（int preorder [ int inorder []，int inostart，int length）
 {
 if（length == 0）return; // terminate condition 
 int i; 
 for（i = inostart; i  if（preorder [prestart] == inorder [i]）//当在inorder数组中找到根时断开
 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）

将是

  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; // terminate condition 
 int i; 
 for（i = inostart; 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）; 
} 
  

解决方案

这里有几个提示： / p>

• postorder 子阵列中的最后一个元素是您的新 c> c $ c> preorder root。


• 您可以调用 print_preorder c> c> c> c> c> inorder 和 postorder 数组的大小将相同。


• bounds数组访问： 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]）$ ​​b $ b | | |  - > 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 = []）
  

/ p>

Given the code for outputing the postorder traversal of a tree when I have the preorder and the inorder traversal in an integer array. How do I similarly get the preorder with the inorder and postorder array given?

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

Here is the prototype for preorder()

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

to use postorder() it will be

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

out put will be

1 5 4 9 8 6

below is the incorrect code for print_preorder(), still not working below

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);
    }

解决方案

Here's a few hints:

• The last element in the postorder subarray is your new preorder root.
• The inorder array can be split in two on either side of the new preorder root.
• You can call recursively call the print_preorder function on those two inorder subarrays.
• When calling the print_preorder function, the inorder and postorder arrays will be the same size.
• You have an out-of-bounds array access: postorder[poststart+length] is past the end of the array. To get the last element, you want postorder[poststart+length-1]
• Your first recursive print_preorder function chooses the wrong length. Remember that length is the length of the subarray, but inostart is the absolute position within the inorder array. Your function will probably call with a negative length.
• Your second recursive function is pretty far off for translating the bounds and length. It'll probably help to draw it on paper and trace your algorithm.

It may help to draw the tree:

     6
   /   \
  4     8
 / \     \
1   5     9

Then write out the three traversals:

// 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};

Now, put down the computer, get out a pen & paper and think about the problem :)

Imagine this call stack (the new root is printed on the left):

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=[])

Good luck :)

这篇关于给定的顺序和后序tranversal如何输出树的前序遍历？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！