二叉树高度、宽度、结点个数、叶子结点个数

实现二叉树宽度递归算法~
  1 #include <iostream>
  2 using namespace std;
  3 typedef struct node
  4 {
  5 char data;
  6 int lab;
  7 struct node *lchild;
  8 struct node *rchild;
  9 }btree;
 10 int m=0;
 11 void ct(btree *&b,char *str)
 12 {
 13 btree *st[99],*p=NULL;
 14 int top=-1,k,j=0;
 15 char ch;
 16 b=NULL;
 17 ch=str[j];
 18 while(ch!='\0')
 19 {
 20    switch(ch)
 21    {
 22    case '(':top++;st[top]=p;k=1;break;
 23    case ')':top--;break;
 24    case ',':k=2;break;
 25    default:p=(btree *)malloc(sizeof(btree));
 26     p->data=ch;
 27     p->lchild=p->rchild=NULL;
 28     if(b==NULL)
 29      b=p;
 30     else
 31     {
 32      switch(k)
 33      {
 34      case 1:st[top]->lchild=p;break;
 35      case 2:st[top]->rchild=p;break;
 36      }
 37     }
 38    }
 39    j++;
 40    ch=str[j]; 
 41 }
 42 }
 43 void outbt(btree *b)
 44 {
 45 if(b!=NULL)
 46 {
 47    cout<<b->data;
 48    outbt(b->lchild);
 49    outbt(b->rchild);
 50 }
 51 }
 52 btree *findchild(btree *b,char x)
 53 {
 54 btree *p;
 55 if(b==NULL)
 56 {
 57    return NULL;
 58 }
 59 else
 60    if(b->data==x)
 61    {
 62     cout<<"找到结点"<<x<<"!"<<endl;
 63     if(b->lchild==NULL)
 64      cout<<"左节点为空!"<<endl;
 65     else
 66      cout<<"左孩子为:"<<b->lchild->data<<endl;
 67     if(b->rchild==NULL)
 68      cout<<"右孩子为空!"<<endl;
 69     else
 70      cout<<"右孩子为:"<<b->rchild->data<<endl;
 71     return b;
 72    }
 73    else
 74    {
 75     p=findchild(b->lchild,x);
 76     if(p!=NULL)
 77      return p;
 78     else
 79      return findchild(b->rchild,x);
 80    }
 81 }
 82 int btreeheight(btree *b)
 83 {
 84 int lchildh,rchildh;
 85 if(b==NULL)
 86    return(0);
 87 else
 88 {
 89    lchildh=btreeheight(b->lchild);
 90    rchildh=btreeheight(b->rchild);
 91    return(lchildh>rchildh?(lchildh+1):(rchildh+1));
 92 }
 93 }
 94 int i=-1,a[20];
 95 void btreewide(btree *b)
 96 {
 97 if(b!=NULL)
 98 {
 99    if(b->lchild!=NULL)
100    {
101     i++;
102     b->lchild->lab=b->lab+1;
103     a[i]=b->lab+1;
104    }
105    if(b->rchild!=NULL)
106    {
107     i++;
108     b->rchild->lab=b->lab+1;
109     a[i]=b->lab+1;
110    }
111    btreewide(b->lchild);
112    btreewide(b->rchild);
113 }
114 }
115 void vernum(btree *b)
116 {
117 if(b!=NULL)
118 {
119    m++;
120    vernum(b->lchild);
121    vernum(b->rchild);
122 }
123 }
124 int leafver(btree *b)
125 { 
126     if(b==NULL)
127    return 0;
128     else 
129    if(b->lchild==NULL&&b->rchild==NULL)
130     return 1;
131         else 
132     return leafver(b->lchild)+leafver(b->rchild); 
133 }
134 void main()
135 {
136 char *s;
137 s="A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))";
138 btree *bt;
139 cout<<"将要创建的二叉树:"<<endl<<s<<endl;
140 ct(bt,s);
141 cout<<"输出二叉树:"<<endl;
142 outbt(bt);
143 cout<<endl;
144 cout<<"H结点左右孩子结点值:"<<endl;
145 findchild(bt,'H');
146 cout<<"二叉树的深度:"<<btreeheight(bt)<<endl;
147 vernum(bt);
148 cout<<"二叉树结点个数:"<<m<<endl;
149 cout<<"二叉树叶子结点个数:"<<leafver(bt)<<endl;
150 bt->lab=1;
151 btreewide(bt);
152 int j,k,num,max=0;
153 for(j=1;j<=i+1;j++)
154 {
155    num=0;
156    for(k=0;k<=i;k++)
157     if(a[k]==j)
158      num++;
159    if(max<num)
160    {
161     max=num;
162    }
163 }
164 cout<<"二叉树宽度为:"<<max<<endl;
165 }