#include <stdio.h> #include <stdlib.h> void printT(char pred[],int pre_start,int pre_end,char inod[],int in_start,int in_end); int main(){ //char pred[]="ABDECFG"; //char inod[]="DBEACGF"; //printT(pred,0,6,inod,0,6); //char pred[]="ABCDEF"; //char inod[]="CBDAFE"; //这个例子是E没有右孩子 //printT(pred,0,5,inod,0,5); char pred[]="ABCDEF"; char inod[]="BCAEDF";//这个例子是B没有左孩子 printT(pred,0,5,inod,0,5); return 1; } void printT(char pred[],int pre_start,int pre_end,char inod[],int in_start,int in_end){ //根 char root=pred[pre_start]; if(in_start>in_end) return ;//非法节点 这句话必须有//怎么会出现非法子树呢？ if(pre_start==pre_end || in_start==in_end ){//表明此时该树只有一个节点 printf("%c,",root); return; } //寻找该根在中序遍历中的位置 这样才能确定该根的左右子树 int leftNo=0;//统计左子树总节点数 int inIndex=in_start;//用于记录root在中序遍历中的位置 while(inod[inIndex]!=root){ inIndex++; } leftNo=inIndex-in_start; //左子树 //上面已经求出了左子树的节点个数 那么pred中左子树的范围就很好确定了 printT(pred,pre_start+1,pre_start+leftNo,inod,in_start,inIndex-1); //右子树 printT(pred,pre_start+leftNo+1,pre_end,inod,inIndex+1,in_end); printf("%c,",root); } /* 关于非法子树 假如某一个子树 没有左边孩子 或者没有右边孩子 假如这一层的没有左孩子 那么在中序遍历中in_start==inIndex 那么本次算出来的in_start 会大于 inIndex-1 进入本层 左子树 后 左子树接收到的in_start就大于 in_end 属于非法子树 假如这一层没有右孩子 那么在中序遍历中 inIndex==in_end 进入本层的 右子树这一层后 接收到的in_start>in_end 属于非法子树 */