西安网站制作设计定制/产品推广语

在本题中，给出中序遍历结果以及先序遍历结果或后序遍历才可以构建唯一二叉树，若给出先序和后序，则不唯一。

本题思路即从左到右按顺序读取pre字符串，并在mid字符串中找到相应位置pos_m，在pos_m左边的字符串递归建立左子树，右边递归建立右子树。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef struct Node
{char data;struct Node* LChild;struct Node* RChild;
}BiNode, *BiTree;int PreFindMid(char *pre, char *mid, int pos_p, int pos_le, int pos_ri);
//找到先序字符对应的中序字符
BiTree CreateTree(char *pre, char *mid, int *pos_p, int pos_le, int pos_ri);
//建立二叉树
void PostOrder(BiTree T);
//后序输出int main()
{int len_pre;char pre[100], mid[100];scanf("%s%s", pre, mid);len_pre = strlen(pre);BiTree T;int pos_p = 0;T = CreateTree(pre, mid, &pos_p, 0, len_pre-1);PostOrder(T);return 0;
}int PreFindMid(char *pre, char *mid, int pos_p, int pos_le, int pos_ri)
{  //找到先序字符对应的中序字符for (int i = pos_le; i <= pos_ri; i++) {if (pre[pos_p] == mid[i]) {return i;}}return 0;
}BiTree CreateTree(char *pre, char *mid, int *pos_p, int pos_le, int pos_ri)
{  //建立二叉树BiTree tmp;tmp = (BiTree) malloc (sizeof(BiNode));tmp->data = pre[*pos_p];tmp->LChild = NULL;tmp->RChild = NULL;(*pos_p)++;int pos_m;pos_m = PreFindMid(pre, mid, *pos_p-1, pos_le, pos_ri);//找到pre字符串的读取字符在mid字符串的位置if (pos_m > pos_le) {tmp->LChild = CreateTree(pre, mid, pos_p, pos_le, pos_m-1);}if (pos_m < pos_ri) {tmp->RChild = CreateTree(pre, mid, pos_p, pos_m+1, pos_ri);}return tmp;
}void PostOrder(BiTree T)
{  //后序输出if (T == NULL) {return;}PostOrder(T->LChild);PostOrder(T->RChild);printf("%c", T->data);
}