博客

7-1 根据后序和中序遍历输出先序遍历 (25分)

• 题目
  本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的先序遍历结果。
  输入格式:
  第一行给出正整数N(≤30)，是树中结点的个数。随后两行，每行给出N个整数，分别对应后序遍历和中序遍历结果，数字间以空格分隔。题目保证输入正确对应一棵二叉树。
  输出格式:
  在一行中输出Preorder:以及该树的先序遍历结果。数字间有1个空格，行末不得有多余空格。
  输入样例:
  7
  2 3 1 5 7 6 4
  1 2 3 4 5 6 7
  输出样例:
  Preorder: 4 1 3 2 6 5 7

• 整个题目的分析自己最好还是在纸上写写画画，这样自己更清楚。

• 主要就是递归的思想，从中序数组找根节点，中序数组中这个根节点左边的就是左子树，右边就是右子树，递归左右两部分然后就可得所有节点。

• 代码

#include<bits/stdc++.h>
using namespace std;

int mid[33],post[33];

typedef int Status;

/*先根据后序和中序得出那个二叉树，然后再输出
使用递归来对树进行赋值。后序序列中最后一个元素为根,
中序序列中该结点前的元素为左子树,后的元素为右子树。
对于左/右子树,最后一个在后序序列中出现的元素为子树的根结点,
再看中序序列,依此类推
主要的是怎么后序序列中找子树的根节点,递归中也要求子树的长度来求最后位置的那个根结点
*/

//树的储存结构定义
typedef struct BiTNode{
   int data;//结点的值
   struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

BiTree Creat(int *mid,int *post,int n){//根据后序和中序求出树
   if(n<1)return NULL;//如果输入出错

   int *p = mid;//寻找中序中的根结点

   while(p){
   if(*p== *(post+n-1))
   break;
   p++;
   }//p为中序中第一个根结点

   BiTree T =(BiTree)malloc(sizeof(BiTNode));//开辟空间

   T->data=*p;//p为第一个根结点
   int len = p-mid;
   //递归
   T->lchild= Creat(mid,post,len);
   T->rchild = Creat(p+1,post+len,n-len-1);
   return T;



}

void Print(BiTree T){
if(T){
   cout<<" "<<T->data;
   Print(T->lchild);
   Print(T->rchild);

}
return;


}

int main(){
   int n;
   BiTree T;
   cin>>n;
   //输入两个储存后序和中序的数组
   for(int i=0;i<n;i++){
       cin>>post[i];
   }
   for(int j=0 ;j < n;j++){
       cin>>mid[j];
   }
   T = Creat(mid,post,n);
   //将树前序输出
   cout<<"Preorder:";
   Print(T);


}