一般来讲，给定二叉树的先序遍历序列和后序遍历序列，不能唯一确定这棵二叉树。但 是，对于真 二叉树来讲，给定它的先序遍历序列 pre 和后序遍历序列 post，可以唯一确定这 棵真二叉树。所谓真 二叉树是指每个内部节点都有两个孩子的二叉树。 根据真二叉树的先序遍历序列 pre 和后序遍历序列 post，编写一个实现真二叉树的构造 及中序遍 历的程序，要求如下： （1）具有操作界面； （2）可以测试多组数据，每组数据的真二叉树先序遍历序列 pre、后序遍历序列 post 通过键盘输 入 （ 3 ） 将 先 序 遍 历 序 列 pre 、 后 序 遍 历 序 列 post 、 中 序 遍 历 序 列 in 保 存 到 文 本 文 件 proper-bitree.txt 中， 格式如下： 真二叉树的先序遍历序列 pre 真二叉树的后序遍历序列 post 真二叉树的中序遍历序列 in
分析：二叉树前序遍历的第一个元素和后序遍历的最后一个元素为树根，后序遍历序列的倒数第二个元素为右子树的根，前序遍历中右子树的根的前面的元素均为左子树元素，从而分隔左右子树的元素，据此可以采用递归依次构建每一棵子树。
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct BitNode { char data; struct BitNode *lchild; struct BitNode *rchild; } BitNode; BitNode *Creat_ProperBiTree(char *pre, char *post, int length, int *tag); //前序后序转中序 void InOrderTraverse(BitNode*T); int main(void) { int c; while(1) { printf("请开始选择：0、构造真二叉树，1、退出\n"); scanf("%d", &c); fflush(stdin); switch(c) { case 0: { FILE *fp ; int tag = 0;//标记错误，0为无错误 if((fp = fopen("proper-bitree.txt", "a")) == NULL) { printf("打开文件失败\n"); exit(EXIT_FAILURE); } system("cls"); char pre[1024]; char post[1024]; //文件写入前序序列 printf("请输入前序输出序列(不要有空格)\n"); gets(pre); fputs(pre, fp); fprintf(fp, "\n"); //文件写入后序序列 printf("请输入后序输出序列(不要有空格)\n"); gets(post); fputs(post, fp); fprintf(fp, "\n"); fclose(fp); int prelength = strlen(pre); int postlength = strlen(post); if(prelength != postlength || prelength % 2 == 0 || postlength % 2 == 0) { tag = 1;//长度不符合要求，设置错误 } //开始构造真二叉树 BitNode* T; T = Creat_ProperBiTree(pre, post, prelength, &tag);//tag指示是否出错 if(tag == 0) { InOrderTraverse(T); if((fp = fopen("proper-bitree.txt", "a")) == NULL) { printf("打开文件失败\n"); exit(EXIT_FAILURE); } fprintf(fp, "\n");//行末增加换行 fclose(fp); printf("结果已写入文件\n"); } else { if((fp = fopen("proper-bitree.txt", "a")) == NULL) { printf("打开文件失败\n"); exit(EXIT_FAILURE); } fprintf(fp, "对不起，输入的序列无法构成真二叉树\n"); fclose(fp); printf("结果已写入文件\n"); } system("pause"); } break; case 1: { return 0; break; } default: printf("输入错误，请重新输入\n"); break; } } return 0; } void InOrderTraverse(BitNode*T) { if(T) { InOrderTraverse(T->lchild); //在文件中写入中序遍历序列 FILE *fp1; if((fp1 = fopen("proper-bitree.txt", "a")) == NULL) { printf("打开文件失败\n"); exit(EXIT_FAILURE); } fputc(T->data, fp1); fclose(fp1); InOrderTraverse(T->rchild); } } BitNode *Creat_ProperBiTree(char *pre, char *post, int length, int *tag) //前序后序转中序 { if(length == 1)//有一个节点，必为根 { BitNode* T = (BitNode*)malloc(sizeof(BitNode)); if(pre[0] == post[0])//唯一的节点相同 { T->data = pre[0]; T->lchild = NULL; T->rchild = NULL; return T; } else//唯一的节点不相同，必错误 { *tag = 1; return NULL; } } if(length % 2 == 0)//序列长度为偶数，无法构成真二叉树 { *tag = 1; return NULL; } int i = 0; if(pre[0] != post[length - 1])//在前序和后序遍历序列中找到的根不一样 { *tag = 1;//设置错误 return NULL; } char Root = pre[0];//根 char rightRoot = post[length - 2]; //右子树根 while(pre[i] != rightRoot && i < length) { i++;//在前序遍历中找到右子树的根，从而分隔左右子树 } if( i == length ) { *tag = 1;//在前序序列没找到右子树的根，错误 return NULL; } int leftlength = i - 1;//左子树节点个数 int rightlength = length - i;//右子树节点个数 BitNode * T = (BitNode*)malloc(sizeof(BitNode)); T->data = Root; T->lchild = Creat_ProperBiTree(&pre[1], &post[0], leftlength,tag); T->rchild = Creat_ProperBiTree(&pre[i], &post[i - 1], rightlength,tag); return T; }注：文件指针做成全局变量更好，会节省不少行代码，也可以提高代码运行效率。(懒得不想改了)
附上流程图：
