c语言实现二叉树的代码

11,2两问的程序代码如下：#includestdio.h#includemalloc.htypedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;BiTreeCreate(BiTreeT){charch;ch=getchar();if(ch=='#')T=NULL;else{T=(BiTNode*)malloc(sizeof(BiTNode));T-data=ch;T-lchild=Create(T-lchild);T-rchild=Create(T-rchild);}returnT;}intnode(BiTreeT){intsum1=0,a,b;2if(T){if(T!=NULL)sum1++;a=node(T-lchild);sum1+=a;b=node(T-rchild);sum1+=b;}3returnsum1;}intmnode(BiTreeT){intsum2=0,e,f;if(T){if((T-lchild!=NULL)&&(T-rchild!=NULL))sum2++;e=mnode(T-lchild);sum2+=e;f=mnode(T-rchild);sum2+=f;}returnsum2;4}voidPreorder(BiTreeT){if(T){printf(%c,T-data);Preorder(T-lchild);Preorder(T-rchild);}}intSumleaf(BiTreeT){intsum=0,m,n;if(T){if((!T-lchild)&&(!T-rchild))sum++;m=Sumleaf(T-lchild);sum+=m;n=Sumleaf(T-rchild);sum+=n;}returnsum;}voidzhongxu(BiTreeT){5if(T){zhongxu(T-lchild);printf(%c,T-data);zhongxu(T-rchild);}}voidhouxu(BiTreeT){if(T){houxu(T-lchild);houxu(T-rchild);printf(%c,T-data);}}main(){BiTreeT;intsum,sum1,sum3;printf(请输入字符串：\n);T=Create(T);printf(前序遍历:\n);Preorder(T);printf(\n);6printf(中序遍历:\n);zhongxu(T);printf(\n);printf(后序遍历:\n);houxu(T);printf(\n);sum=Sumleaf(T);printf(树叶数为:\n);printf(%d,sum);printf(\n);printf(树结点数为:\n);sum1=node(T);printf(\n);printf(%d,sum1);printf(\n);printf(树满结点数为:\n);sum3=mnode(T);printf(%d,sum3);printf(\n);}73,4两问的程序代码如下：#includestdio.hJK#includemalloc.h#defineNULL0#defineMAX100/*定义二叉树*/typedefstructbitnode{chardata;structbitnode*lchild,*rchild;}bitnode;/*定义栈元素的类型*/typedefstructnode{structbitnode*p;}node;/*定义栈*/typedefstructstack{node*base;node*top;intsize;}stack;/*全局变量*/structbitnode*T;stack*s;inti=0,a;/*a为二叉树的结点总数；i为访问结点时的计数*//*构建空栈*/stack*initstack(){s-base=(structnode*)malloc(MAX*sizeof(node));if(!s-base)exit(0);s-top=s-base;s-size=MAX;returns;}/*判断栈是否为空栈*/intstackempty(stack*s){if(s-top==s-base)return1;elsereturn0;}/*入栈*/stack*push(stack*s,structbitnode*t){if(s-top-s-base==s-size){s-base=(structnode*)realloc(s-base,(s-size+10)*sizeof(node));if(!s-base)exit(0);8s-top=s-base+s-size;s-size+=10;}(*s-top).p=t;s-top++;returns;}/*出栈*/structbitnode*pop(stack*s){if(s-top==s-base){printf(这是一个空栈\n);return0;}else{s-top--;return((*s-top).p);}}/*取栈顶的元素*/structbitnode*getpop(stack*s){if(s-top==s-base){printf(这是一个的空栈！\n);returnNULL;}elsereturn(*(s-top-1)).p;}/*先序递归构建二叉树*/structbitnode*creatbitree(structbitnode*r){chara;scanf(%c,&a);if(a=='')returnr=NULL;else{r=(structbitnode*)malloc(sizeof(bitnode));r-data=a;r-lchild=creatbitree(r-lchild);r-rchild=creatbitree(r-rchild);}returnr;9}/*访问元素*/voidvisit(charch){if(i!=(a-1)){printf(%c-,ch);i++;}else{printf(%c,ch);printf(\n);}}/*中序非递归遍历二叉树*/voidinorder(structbitnode*T){structbitnode*p,*q;p=T;s=initstack();if(p){while(p){push(s,p);p=p-lchild;}while(!stackempty(s)){p=pop(s);visit(p-data);if(p-rchild!=NULL){q=p-rchild;while(q){push(s,q);q=q-lchild;}}}}}/*求二叉树的结点总数*/intcounter(structbitnode*T){intnum1,num2,num;if(T==NULL)return0;else{num1=counter(T-lchild);num2=counter(T-rchild);num=num1+num2+1;returnnum;10}}/*求二叉树的单分支的结点数*/intonecount(structbitnode*T){ints1,s2;if(T==NULL)return(0);else{s1=onecount(T-lchild);s2=onecount(T-rchild);if((T-lchild!=NULL&&T-rchild==NULL)||(T-rchild!=NULL&&T-lchild==NULL))return(s1+s2+1);elsereturn(s1+s2);}}/*主函数*/main(){intsum;printf(xianxushurubitree:\n);T=creatbitree(T);/*创建二叉树*/a=counter(T);/*求结点总数*/printf(\na=%d\n,a);printf(\nzhongxubianlibitree:\n);inorder(T);/*中序遍历二叉树*/sum=onecount(T);/*求单分支的结点数*/printf(\n\nthebitreedanfenzhijiedianshu:\nSUM=%d\n,sum);getch();}