PTA 树与二叉树 2 根据先序+中序遍历序列构造二叉树

作者 张鏖烽单位 湖南工程学院计算机与通信学院从键盘输入一个二叉树的先序遍历序列和中序遍历序列编程实现下列函数1CreateBT_PI(pre,in,n):根据先序遍历序列*pre和中序遍历*in构造二叉链树2DisplayBT(bt):以括号表达式的形式输出二叉链树bt3LevelNode(bt,x,h):求二叉链树中值等于x的节点的层次 hx不在树中返回04PrintLeaf(bt):输出二叉链树的所有叶子节点函数接口定义BTNode * CreateBT_PI(char *pre,char *in,int n);//根据先序遍历和后序遍历序列构造二叉链树 void DisplayBT(BTNode *b); //以括号表达式形式输出二叉链树 int LevelNode(BTNode *b,char x,int h);//找到等于x的结点后h为其层次否则为0 void PrintLeaf(BTNode *b);//输出二叉链树的所有叶子节点其中*pre为先序遍历序列指针*in为中序遍历序列指针n为遍历序列的长度x为键盘输入的待查找节点字符h为节点的层次裁判测试程序样例#includestdio.h #includemalloc.h #includestring.h #define MaxSize 100 typedef struct Node{ char data; struct Node *lchild,*rchild; }BTNode; BTNode * CreateBT_PI(char *pre,char *in,int n);//创建二叉链树 void DisplayBT(BTNode *b); //以括号表达式形式输出二叉链树 int LevelNode(BTNode *b,char x,int h);//找到等于x的结点后h为其层次否则为0 void PrintLeaf(BTNode *b);//输出二叉链树的所有叶子节点 int main() { char Prectr[MaxSize],Inctr[MaxSize]; char *pre,*in; char ch; int n,h1,level; BTNode *bt; scanf(%s,Prectr); scanf(%s,Inctr); getchar(); scanf(%c,ch); prePrectr; nstrlen(Prectr); inInctr; btCreateBT_PI(pre,in,n); levelLevelNode(bt,ch,h); printf(\n二叉树的括号表达式); DisplayBT(bt); if(level0) printf(\n节点%c 在二叉树的第%d层,ch,level); else printf(\n二叉树没有等于%c的节点,ch); printf(\n二叉树的所有叶子节点); PrintLeaf(bt); return 0; } /* 请在这里填写答案 */输入样例在这里给出一组输入。例如第1行输入先序序列第2行输入中序序列第3行输入要查找的节点数据chGBDAHCEFJIK ADHBCGJFEIK D输出样例在这里给出相应的输出。例如二叉树的括号表达式G(B(D(A,H),C),E(F(J),I(,K))) 节点D 在二叉树的第3层 二叉树的所有叶子节点A H C J K参考代码BTNode *CreateBT_PI(char *pre,char *in,int n){ if(n0) return NULL; BTNode *r(BTNode*)malloc(sizeof(BTNode)); r-datapre[0]; int k; for(k0;kn;k){ if(*pre*(ink)) break; } r-lchildCreateBT_PI(pre1,in,k); r-rchildCreateBT_PI(pre1k,ink1,n-k-1); return r; } void DisplayBT(BTNode *b){ if(b!NULL){ printf(%c,b-data); if(b-lchild!NULL||b-rchild!NULL){ printf((); DisplayBT(b-lchild); if(b-rchild!NULL){ printf(,); DisplayBT(b-rchild); } printf()); } } } int LevelNode(BTNode *b,char x,int h){ if(bNULL) return 0; if(b-datax) return h; int leftLevelNode(b-lchild,x,h1); if(left0) return left; return LevelNode(b-rchild,x,h1); } void PrintLeaf(BTNode *b){ static int f1; if(!b) return; if(!b-lchild!b-rchild){ if(!f) printf( ); printf(%c,b-data); f0; }else{ PrintLeaf(b-lchild); PrintLeaf(b-rchild); } }