NYOJ--重建二叉树

r囧r小猫 2022-08-26 14:19 97阅读 0赞

## 重建二叉树 ##

时间限制： 1000 ms  |  内存限制： 65535 KB

难度： 3

描述

题目很简单，给你一棵二叉树的后序和中序序列，求出它的前序序列（So easy!）。

输入

输入有多组数据（少于100组），以文件结尾结束。  
每组数据仅一行，包括两个字符串，中间用空格隔开，分别表示二叉树的后序和中序序列（字符串长度小于26，输入数据保证合法）。

输出

每组输出数据单独占一行，输出对应得先序序列。

样例输入

ACBFGED ABCDEFG
    CDAB CBAD

样例输出

DBACEGF
    BCAD

**来源**

[原创][Link 1]

解析：这是一道数据结构中很水的题，可惜自己因为文件结束符EOF这个TLE了很多次，唉……粗心哈！先简单说一下二叉树的遍历

先序遍历二叉树：先序遍历根节点，先序遍历左子树，先序遍历右子树，也就是NLR

中序遍历二叉树：中序遍历左子树，中序遍历根节点，中序遍历右子树，也就是LNR

后序遍历二叉树：后序遍历左子树，后序遍历右子树，后序遍历根节点，也就是LRN

要想由这三种遍历二叉树的序列重建唯一的二叉树则至少得有两种遍历序列，且这两种中一定要有中序序列，也就是先序+中序-->二叉树  或者  后序+中序-->二叉树，而先序+中序得不到唯一的二叉树。

下面看一下这三种遍历的特点，首先先序序列总是先遍历根节点，所以它的序列的第一个必然是整个二叉树的根节点，相反，后序遍历的序列最后一个必然是二叉树的根节点，通过缺点了二叉树的根节点，在中序序列中找到这个根节点，因为中序序列是先遍历左字数再遍历根节点，然后是右子树，所以在中序序列中的根节点左边的节点全都是左子树的，右边的序列都应该是右子树的，接着递归的应用就可以得到整个二叉树了(不知道说清楚的没)

后序序列：ACBFGED

中序序列：ABCDEFG

首先确定D是整个二叉树的根节点，然后在中序序列中找到D则其左边的ABC就是D的左子树，EFG就是 D的右子树。

提取出左字数的后序和中序序列

后序序列：ACB

中序序列: ABC

后序序列的最后一个字符是B则B是当前子树的根节点，然后在中序序列中找到B则左边的A是B的左子树,C是B的右子树。

以此递推就可以得到整个二叉树的结构了，如下图所示

![20140415102059562][]

同样知道先序序列和中序序列后也可以构建出唯一的二叉树，掌握的思想，下面就是用代码实现的事情了。

代码本着重建二叉树的原则，并没考虑太多OJ时间和空间的限制，但AC还是可以的，在代码中我右加上了先序+中序-->二叉树的函数

当然在实际的OJ上做类似的题时不用那么麻烦根根节点分配空间，直接输出就好了，我只不过是想将二叉树建立起来，看起来比较直观而已

#include <stdio.h> #include <malloc.h> #include <string.h> //二叉链表 typedef struct node{ char data;//节点数据元素 struct node *lchild;//指向左孩子 struct node *rchild;//指向右孩子 }BiNode,*BTree; //利用后序和中序建立二叉树 void GetPreOrder(char *last,char *mid,BTree &T,int len) { if(len==0) { T = NULL; return; } //取出后序序列中的最后一个节点 char ch=last[len-1]; int index=0; //在中序序列中进行查找根节点，并用index记录其在序列中的索引 while(mid[index]!=ch) { index++; } //给根节点分配空间 T=(BTree)malloc(sizeof(BiNode)); T->data=mid[index]; //建立左子树 GetPreOrder(last,mid,T->lchild,index); //建立右子树 GetPreOrder(last+index,mid+index+1,T->rchild,len-index-1); } void GetPostOrder(char *prim,char *mid,BTree &T,int len) { if(len==0) { T=NULL; return; } //提出先序序列中的第一个节点 char ch=prim[0]; int index=0; //在中序序列中查找当前根节点，并用index记录其在序列中的位置 while(mid[index]!=ch) { index++; } //给根节点分配空间 T=(BTree)malloc(sizeof(BiNode)); T->data=mid[index]; //建立左子树 GetPostOrder(prim+1,mid,T->lchild,index); //建立右子树 GetPostOrder(prim+index+1,mid+index+1,T->rchild,len-index-1); } //先序输出二叉树 void PreOrder(BTree T) { if(T!=NULL) { printf("%c",T->data); PreOrder(T->lchild); PreOrder(T->rchild); } } //后序输出二叉树 void PostOrder(BTree T) { if(T!=NULL) { PostOrder(T->lchild); PostOrder(T->rchild); printf("%c",T->data); } } int main() { char first[26],mid[26],last[26]; while(scanf("%s%s",last,mid)!=EOF) { BTree T=NULL; GetPreOrder(last,mid,T,strlen(last)); PreOrder(T); // GetPostOrder(last,mid,T,strlen(last)); // PostOrder(T); printf("\n"); } return 0; }

[Link 1]: http://acm.nyist.edu.cn/JudgeOnline/search_result.php?source=%E5%8E%9F%E5%88%9B
[20140415102059562]: /images/20220824/148efbd2a47e491682c71b411cbb3ad2.png