求二叉树中的结点个数、叶子结点个数、某结点层次和二叉树宽度

目的： 掌握二叉树遍历算法的应用，熟练使用先序、中序、后序3种递归遍历算法和层次遍历算法进行二叉树问题求解。 功能： （1）输出二叉树b的结点个数； （2）输出二叉树b的叶子结点个数； （3）求二叉树b中指定结点值（假设所有结点值不同）的结点的层次； （4）利用层次遍历求二叉树b的宽度。 代码：

#include<stdio.h> #include<malloc.h> #define MaxSize 100 typedef char ElemType; typedef struct node { ElemType data; struct node *lchild; struct node *rchild; }BTNode; void CreateBTree(BTNode *&b,char *str) { BTNode *St[MaxSize],*p; int top=-1,k,j=0;char ch; b=NULL; 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 DestroyBTree(BTNode *&b) { if(b!=NULL) { DestroyBTree(b->lchild); DestroyBTree(b->rchild); free(b); } } BTNode *FindNode(BTNode *b,ElemType x) { BTNode *p; if(b==NULL) return NULL; else if(b->data==x) return b; else { p=FindNode(b->lchild,x); if(p!=NULL) return p; else return FindNode(b->rchild,x); } } BTNode *LchildNode(BTNode *p) { return p->lchild; } BTNode *RchildNode(BTNode *p) { return p->rchild; } int BTHeight(BTNode *b) { int lchildh,rchildh; if(b==NULL)return(0); else { lchildh=BTHeight(b->lchild); rchildh=BTHeight(b->rchild); return (lchildh>rchildh)?(lchildh+1):(rchildh+1); } } void DispBTree(BTNode *b) { if(b!=NULL) { printf("%c",b->data); if(b->lchild!=NULL||b->rchild!=NULL) { printf("("); DispBTree(b->lchild); if(b->rchild!=NULL)printf(","); DispBTree(b->rchild); printf(")"); } } } int Nodes(BTNode *b) { int num1,num2; if(b==NULL) return 0; else if(b->lchild==NULL&&b->rchild==NULL) return 1; else { num1=Nodes(b->lchild); num2=Nodes(b->rchild); return (num1+num2+1); } } int LeafNodes(BTNode *b) { int num1,num2; if(b==NULL) return 0; else if(b->lchild==NULL&&b->rchild==NULL) return 1; else { num1=LeafNodes(b->lchild); num2=LeafNodes(b->rchild); return (num1+num2); } } int Level(BTNode *b,ElemType x,int h) { int l; if(b==NULL) return 0; else if(b->data==x) return h; else { l=Level(b->lchild,x,h+1); if(l!=0)return l; else return(Level(b->rchild,x,h+1)); } } int BTWidth(BTNode *b) { struct { int lno; BTNode *p; }Qu[MaxSize]; int front,rear; int lnum,max,i,n; front=rear=0; if(b!=NULL) { rear++;Qu[rear].p=b; Qu[rear].lno=1; while(rear!=front) { front++;b=Qu[front].p; lnum=Qu[front].lno; if(b->lchild!=NULL) { rear++;Qu[rear].p=b->lchild; Qu[rear].lno=lnum+1; } if(b->rchild!=NULL) { rear++;Qu[rear].p=b->rchild; Qu[rear].lno=lnum+1; } } max=0;lnum=1;i=1; while(i<=rear) { n=0; while(i<=rear&&Qu[i].lno==lnum) { n++; i++; } lnum=Qu[i].lno; if(n>max)max=n; } return max; } else return 0; } int main() { ElemType x='K'; BTNode *b,*p,*lp,*rp; CreateBTree(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"); printf("输出二叉树b：");DispBTree(b);printf("\n"); printf("二叉树b的结点个数：%d\n",Nodes(b)); printf("二叉树的叶子结点个数：%d\n",LeafNodes(b)); printf("二叉树b中值为%c结点的层次：%d\n",x,Level(b,x,1)); printf("二叉树b的宽度：%d\n",BTWidth(b)); DestroyBTree(b); return 1; }

备注： 有问题可以评论，看到后我会尽力及时回复的，谢谢！