c – 如果给定顺序和后序遍历,如何输出树的前序遍历？

发布时间：2020-12-16 10:27:37 所属栏目：百科来源：网络整理

导读：给出了在我有预订顺序和整数数组中的inorder遍历时输出树的后序遍历的代码.我如何同样获得带有inorder和postorder数组的预订顺序？ void postorder( int preorder[],int prestart,int inorder[],int inostart,int length){ if(length==0) return; //terminat

给出了在我有预订顺序和整数数组中的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,i+1,length-i+inostart-1);
  cout<<preorder[prestart]<<" ";
}

这是preorder()的原型

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

使用postorder()就可以了

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

out put将是

1 5 4 9 8 6

下面是print_preorder()的错误代码,仍然无法在下面工作

void print_preorder( int inorder[],int postorder[],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,postorder,poststart,i-inostart);
      print_preorder(inorder,inostart+i-poststart+1,length-i+inostart-1);
    }

解决方法

这里有一些提示：

>后序子阵列中的最后一个元素是您的新预订根.
> inorder数组可以在新预订根的任一侧拆分为两个.
>您可以在这两个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,9,6};
int inorder[6]=  {1,9};
int preorder[6]= {6,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,post=[])
5 |   |-> print_preorder(len=1,in=[5],post=[5])
  |       |-> print_preorder(len=0,post=[])
  |       |-> print_preorder(len=0,post=[])
8 |-> print_preorder(len=2,in=[8 9],post=[9 8])
      |-> print_preorder(len=0,post=[])
9     |-> print_preorder(len=1,in=[9],post=[9])
          |-> print_preorder(len=0,post=[])
          |-> print_preorder(len=0,post=[])

祝好运：)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!