10þ¦

来自「1、猴子选大王 2、约瑟夫环 3、迷宫求解 4、回文游戏 5、地图四染色」· 代码 · 共 58 行

//求二叉树的宽度
#include <iostream>
#include <stdlib.h>
#include <malloc.h>
#include <stdio.h>
#define N 100

int ex[N];//ex[i]表示第i层节点数
int level=1;


typedef struct node
{	char data;
	int ceng;//标记此节点的层数
	struct node *lchild;
	struct node *rchild;
}*BiTree;

void creatBT(BiTree &T,int level)//建立从level层开始的二叉树
{	char ch;
	scanf("%c",&ch);
	if(ch=='.')
		T=NULL;
	else
	{
		T=(node *)malloc(sizeof(node));
		T->data=ch;
		T->ceng=level;
		creatBT(T->lchild,level+1);//建立从level+1层开始的二叉树，作为它的左子树
		creatBT(T->rchild,level+1);//建立从level+1层开始的二叉树，作为它的右子树
	}
}
void pre_order(node *T)//先序遍历二叉树，并统计每层的节点数
{
	if(T)
	{	ex[T->ceng]++;
		pre_order(T->lchild);
		pre_order(T->rchild);
	}
}
int main()
{	int max=0;
	for(int i=0;i<N;i++)
		ex[i]=0;
	printf("请输入先序字符串：\n");
	node *T;
	creatBT(T,level);
	pre_order(T);
	printf("每层的结点数目是:\n");
	i=1;
	while(ex[i]!=0)
	{	printf("%d ",ex[i]);	i++;	}
	for(int j=1;j<=i-1;j++)
		if(ex[j]>max) max=ex[j];
	printf("\n二叉树的宽度是:%d \n",max);
	return 0;
}