电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

求树的繁茂度(数据结构)

求树的繁茂度(数据结构)_第1页
1/6
求树的繁茂度(数据结构)_第2页
2/6
求树的繁茂度(数据结构)_第3页
3/6
一棵二叉树的繁茂度定义为各层结点数的最大值与树的高度的乘积。试写一算法,求二叉树的繁茂度 #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"); }

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

求树的繁茂度(数据结构)

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部