一棵二叉树的繁茂度定义为各层结点数的最大值与树的高度的乘积。试写一算法，求二叉树的繁茂度 #include #include #define MaxSize 100 typedef char ElemType; typedefstruct node { ElemType data; //数据元素 struct node *lchild; //指向左孩子结点 struct node *rchild; //指向右孩子结点 } BTNode; voidCreateBTNode(BTNode * &b,char *str) { BTNode *St[MaxSize],*p=NULL; int top=-1,k,j=0; charch; b=NULL; //建立的二叉树初始时为空 ch=str[j]; while (ch!='\0') //str 未扫描完时循环 { 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) //*p 为二叉树的根结点 b=p; else //已建立二叉树根结点 { switch(k) { case 1:St[top]->lchild=p;break; case 2:St[top]->rchild=p;break; } } } j++; ch=str[j]; } } voidDispBTNode(BTNode *b) { if (b!=NULL) { printf("%c",b->data); if (b->lchild!=NULL || b->rchild!=NULL) { printf("("); //有孩子结点时才输出( DispBTNode(b->lchild); //递归处理左子树 if (b->rchild!=NULL) printf(","); //有右孩子结点时才输出, DispBTNode(b->rchild); //递归处理右子树 printf(")"); //有孩子结点时才输出) } } } typedefstruct { BTNode *node1; int rank; }BTNre; voidLevelOrder(BTNode *b) { int c[MaxSize]={0}; inti,max; BTNre p; BTNrequ[MaxSize]; //定义环形队列,存放结点指针 intfront,rear; //定义队头和队尾指针 front=rear=-1; //置队列为空队列 rear++; qu[rear].node1=b; qu[rear].rank=1;//根结点指针进入队列 while (front!=rear) //队列不为空 { front=(front+1)%MaxSize; p=qu[front]; //队头出队列 c[p.rank]++; //访问结点 if (p.node1->lchild!=NULL) //有左孩子时将其进队 { rear=(rear+1)%MaxSize; qu[rear].node1=p.node1->lchild; qu[rear].rank=p.rank+1; } if (p.node1->rchild!=NULL) //有右孩子时将其进队 { rear=(rear+1)%MaxSize; qu[rear].node1=p.node1->rchild; qu[rear].rank=p.rank+1; } } max=c[1]; for(i=2;i<=p.rank;i++) if(c[i]>max) max=c[i]; printf("树的繁茂度为: %d\n",max*p.rank); } void main() { BTNode *b; CreateBTNode(b,"A(B(D(,G),E(H(I))),C(M,F(,I))"); printf("b:");DispBTNode(b);printf("\n"); LevelOrder(b);printf("\n"); }
