实验三 二叉树的应用 一、实验目的 掌握树形结构的特点，二叉树的存储方式以及相应操作。 二、实验内容 1、根据输入的数据建立一个二叉树。 2、输出其前序、中序和后序遍历的结果。 3、输出树的深度，最大元，最小元。 三、代码 #include #include typedef char ElemType; typedef struct node { ElemType data; struct node *lchild,*rchild; }BTNode; void CreateBTNode(BTNode *&b,char str[]) { BTNode *St[100],*p=NULL; b=NULL; int top=-1,k,j=0; char ch=str[j]; while(ch!='\0') { switch(ch) { case'(':top++;St[top]=p;k=1;break; case')':top--;break; case',':k=2;break; default:p=(BTNode*)malloc(sizeof(BTNode)); p->data=ch; p->lchild=p->rchild=NULL; if(b==NULL) b=p; else switch(k) { case 1:St[top]->lchild=p;break; case 2:St[top]->rchild=p;break; 

} } j++;ch=str[j]; } void PreOrder(BTNode *b) { if (b!=NULL) { printf("%c ",b->data); PreOrder(b->lchild); PreOrder(b->rchild); /*先序遍历的递归算法*/ } void InOrder(BTNode *b) /*中序遍历的递归算法*/ { } } } } if(b!=NULL) { InOrder(b->lchild); printf("%c ",b->data); InOrder(b->rchild); } void PostOrder(BTNode *b) { if(b!=NULL) { PostOrder(b->lchild); PostOrder(b->rchild); printf("%c ",b->data); } int BTNodeDepth(BTNode *b) { int lchilddep,rchilddep; if(b==NULL) return 0; else { } } int BTNodeMax(BTNode *b) { int lchildmax,rchildmax,max; /*后序遍历递归算法*/ lchilddep=BTNodeDepth(b->lchild); rchilddep=BTNodeDepth(b->rchild); return(lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1); 

} } int BTNodeMin(BTNode *b) { int lchildmin,rchildmin,min; if(b==NULL) return 32767; else { } } void main() { lchildmin=BTNodeMin(b->lchild); rchildmin=BTNodeMin(b->rchild); min=lchildmin<=rchildmin?lchildmin:rchildmin; return min<=b->data-'0'?min:b->data-'0'; if(b==NULL) return 0; else { lchildmax=BTNodeMax(b->lchild); rchildmax=BTNodeMax(b->rchild); max=lchildmax>=rchildmax?lchildmax:rchildmax; return max>=b->data-'0'?max:b->data-'0'; BTNode *b; char str[100]; scanf("%s",str); CreateBTNode(b,str); printf("************* 二 叉 树 遍 历 , 求 深 度 , 最 大 元 , 最 小 元 c 语 言 实 现 *************\n"); printf("先序遍历:"); PreOrder(b); printf("\n 中序遍历:"); InOrder(b); printf("\n 后序遍历:"); PostOrder(b); printf("\n 此二叉树的深度:%d",BTNodeDepth(b)); printf("\n 此二叉树的最大元:%d",BTNodeMax(b)); printf("\n 此二叉树的最小元:%d\n",BTNodeMin(b)); } 

四、实验结果 五、问题 输出最大元最小元时，只考虑了每个节点数据为一位的情况；用了很多的递归，降 低了执行效率。