由先序序列和中序序列建立二叉树 建树：betree(&T,i,j,length) { 如果串长度length 不为0 { 定位值k=中序序列起始值j； 判断(中序序列定位值k==先序序列起始值i)，若！=， 则定位值+1 向后继续寻找; 当找到时，给树T 申请空间，将先序序列起始值赋给树结点的数据域T->data; 然后计算出左子树结点数pos=定位值k-中序序列起始值j； 建左子树：递归调用建树函数betree（将树的左孩子传过去，左子树初始值+1，中序序列的定位值，pos）； 建右子树：递归调用建树函数betree（将树的右孩子传过去，左子树初始值+1 再+定位值，串长-定位值-1） //这样递归建树就完成了 }否则 树赋空值； } /////////////////////////////////////////////////////////////////////// //由先序序列和中序序列建立二叉树 //start1 是先序序列的起始位置，start2 是中序序列的起始位置， //len 是先序序列长度 void CreateBiTree(int start1,int start2,int len,BiTree &T) { int pos,len1; if (len<=0) T=NULL; else { pos=start2; //记录中序序列串的位置 while(b[pos]!=a[start1]) pos++; //只要在中序序列串b 中没有找到根，那么就向继续向后寻找 T=(BiTree)malloc(sizeof(BiTNode));//在中序序列b 中找到根，开辟根结点的空间 T->data=a[start1]; //根的值为先序序列的第一个元素 len1=pos-start2; //中序序列根左子区即左子树的长度 CreateBiTree(start1+1,start2,len1,T->lchild); //建立左子树 CreateBiTree(start1+len1+1,pos+1,len-len1-1,T->rchild); //建立右子树 } } 例如 先序序列：EBADCFHGIKJ 0 1 2 3 4 5 6 7 8 9 10 E B A D C F H G I K J start1 start1+1 start1+pos+1 中序序列：ABCDEFGHIJK 0 1 2 3 4 5 6 7 8 9 10 A B C D E F G H I J K pos=start2 k=pos K+1 #include"stdio.h" #include"stdlib.h" #include"conio.h" #include"string.h" #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; #define TElemType char char a[20],b[20]; // a 存放先序序列，b 存放中序序列 //- - - - -二叉树的二叉链表存储表示- - - - - typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchi...
