經測,該代碼已經修改正確,只需在void BuildTree(char *level,char *inorder,pBiTree T)這裏的最後壹個變量T改為引用即可。還有壹個地方判斷調用右子樹的地方的判斷條件。
#include?<stdio.h>#include?<stdlib.h>
#include?<string.h>
typedef?struct?_BiTree
{
char?data;
struct?_BiTree?*lchild;
struct?_BiTree?*rchild;
}BiNode,?*pBiTree;
void?BuildTree(char?*level,char?*inorder,pBiTree?&T)
{
int?i;
int?len=strlen(level);?//取得層次遍歷長度
int?pos=0;
if(len==0)
return?;
char?*p=strchr(inorder,level[0]);
if(p==NULL)?//如果為空則拋棄第壹個,跳到下壹個;
{
char?*L=(char*)malloc(sizeof(char)*len);//開辟數組
strncpy(L,level+1,len-1);//舍棄第壹個
L[len-1]=0;
BuildTree(L,inorder,T);?//調用建樹函數
return?;
}
pos=p-inorder;?//得到中序遍歷左子樹字符串長度
T->data=level[0];//為根節點賦值
T->lchild=NULL;
T->rchild=NULL;
if(pos!=0)?//左子樹的遞歸調用
{
T->lchild=(pBiTree)malloc(sizeof(BiNode));
char?*left_level=(char*)malloc(sizeof(char)*len);
char?*left_inor=(char*)malloc(sizeof(char)*(pos));
strncpy(left_level,level+1,len-1);?//舍去層次遍歷第壹個
strncpy(left_inor,inorder,pos);?//截取左子樹字符串
left_level[len-1]=0;
left_inor[pos]=0;
BuildTree(left_level,left_inor,T->lchild);
}
if(pos?<?strlen(inorder)-1)?//右子樹的遞歸調用
{
T->rchild=(pBiTree)malloc(sizeof(BiNode));
char?*right_level=(char*)malloc(sizeof(char)*(len));
char?*right_inor=(char*)malloc(sizeof(char)*(len-pos));
strncpy(right_level,level+1,len-1);
strncpy(right_inor,inorder+pos+1,len-pos-1);
right_level[len-1]=0;
right_inor[len-pos-1]=0;
BuildTree(right_level,right_inor,T->rchild);
}
}
void?priOrder(pBiTree?T)
{
if?(T?!=?NULL){
printf?("%c",?T->data);
priOrder(T->lchild);
priOrder(T->rchild);
}
}
void?postOrder(pBiTree?T)
{
if?(T?!=?NULL){
postOrder(T->lchild);
postOrder(T->rchild);
printf?("%c",?T->data);
}
}
void?freeNode(pBiTree?&T)
{
if?(T?!=?NULL){
freeNode(T->lchild);
freeNode(T->rchild);
free(T);
}
}
int?main()
{
pBiTree?root;
char?level[28],?inorder[28];
int?n;
scanf?("%d",?&n);
//fflush(stdin);
getchar();
while?(n?--){
scanf?("%s%s",?level,?inorder);
root?=?(pBiTree)malloc(sizeof(BiNode));
BuildTree(level,?inorder,?root);
priOrder(root);
printf?("\n");
postOrder(root);
printf?("\n");
//freeNode(root);
}
return?0;
}