1206还原二叉树2

1206还原二叉树2

• 描述： PIPI现在有两个序列，分别为二叉树的中序序列和二叉树的后序序列，他想由这两个序列还原二叉树，你能帮PIPI还原吗？

• 输入：第一行输入序列的长度n (0 第二行输入二叉树的中序序列。
  第三行输入二叉树的后序序列。

• 输出：输出二叉树的先序遍历序列。

• 输入示例

  3
  2 1 3
  2 3 1
  

• 输出示例

  1 2 3
  

• 代码块

  #include 
  using namespace std;typedef struct BiTNode{int data;struct BiTNode *lchild, *rchild;
  }BiTNode, *BiTree;BiTNode *BuildTree(){int data;scanf("%d", &data);if(data == -1)return NULL;BiTNode *p = (BiTNode *)malloc(sizeof(BiTNode));p->data = data;p->lchild = BuildTree();p->rchild = BuildTree();return p;
  }BiTree CreateBiTreeByInAndPost(int in[], int post[], int inf, int inl, int postf, int postl){if(inf > inl || postf > postl) return NULL;BiTNode *p = (BiTNode *)malloc(sizeof(BiTNode));p->data = post[postl];int i;for(i = inf; i <= inl; i++){if(in[i] == post[postl]) break;}p->lchild = CreateBiTreeByInAndPost(in, post, inf, i-1, postf, i-inf+postf-1);p->rchild = CreateBiTreeByInAndPost(in, post, i+1, inl, i-inf+postf, postl-1);return p;
  }void PreOrder(BiTree T){if(!T) return;printf("%d ", T->data);PreOrder(T->lchild);PreOrder(T->rchild);
  }int main(){int n;scanf("%d", &n);int in[105], post[105];for(int i=0; i<n; i++)scanf("%d", &in[i]);for(int i=0; i<n; i++)scanf("%d", &post[i]);BiTree T = CreateBiTreeByInAndPost(in, post, 0, n-1, 0, n-1);PreOrder(T);system("pause");return 0;
  }
  

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！