PTA 树与二叉树 1 二叉链树的创建与遍历
作者 张鏖烽
单位 湖南工程学院计算机与通信学院
从键盘输入一个二叉树的括号表达式，编程实现下列函数：
（1）CreateLinkBT(bt,ctr):扫描二叉树的括号表达式ctr，创建一个二叉链树bt；
（2）PreOrder(bt):先序遍历二叉链树bt，输出其遍历结果
（3）InOrder(bt):中序遍历二叉链树bt，输出其遍历结果
（4）PostOrder(bt):后序遍历二叉链树bt，输出其遍历结果
函数接口定义：
void CreateLinkBT(BTNode * &b,char str[]);//创建二叉链树 void PreOrder(BTNode *b);//先序遍历 void InOrder(BTNode *b);//中序遍历 void PostOrder(BTNode *b);//后序遍历其中b为二叉链树，str[]为存储二叉树括号表达式的数组
裁判测试程序样例：
#include<stdio.h> #include<malloc.h> #include<stdbool.h> #define MaxSize 100 typedef struct Node{ char data; struct Node *lchild,*rchild; }BTNode; void CreateLinkBT(BTNode * &b,char str[]);//创建二叉链树 void PreOrder(BTNode *b);//先序遍历 void InOrder(BTNode *b);//中序遍历 void PostOrder(BTNode *b);//后序遍历 int main() { char ctr[MaxSize]; scanf("%s",ctr); BTNode *bt; CreateLinkBT(bt,ctr); printf("先序遍历结果："); PreOrder(bt); printf("\n中序遍历结果："); InOrder(bt); printf("\n后序遍历结果："); PostOrder(bt); } /* 请在这里填写答案 */输入样例：
在这里给出一组输入。例如：
c从键盘输入二叉树的括号表达式形式：
G(B(D(A,H),C),E(F(J),I(,K)))输出样例：
在这里给出相应的输出。例如：
先序遍历结果：G B D A H C E F J I K 中序遍历结果：A D H B C G J F E I K 后序遍历结果：A H D C B J F K I E G参考代码：
void CreateLinkBT(BTNode *&b,char str[]){ BTNode*stack[MaxSize]; BTNode*a=NULL; int i=0,k,t=-1; b=NULL; while(str[i]!='\0'){ char ch=str[i++]; if(ch=='('){ stack[++t]=a; k=1; }else if(ch==',') k=2; else if(ch==')') t--; else{ a=(BTNode*)malloc(sizeof(BTNode)); a->data=ch; a->lchild=a->rchild=NULL; if(!b) b=a; else if(k==1) stack[t]->lchild=a; else if(k==2) stack[t]->rchild=a; } } } void PreOrder(BTNode *b) { if (b){ printf("%c ",b->data); PreOrder(b->lchild); PreOrder(b->rchild); } } void InOrder(BTNode *b) { if (b){ InOrder(b->lchild); printf("%c ",b->data); InOrder(b->rchild); } } void PostOrder(BTNode *b) { if (b) { PostOrder(b->lchild); PostOrder(b->rchild); printf("%c ",b->data); } }