[说明] 求树的宽度，所谓宽度是指在二叉树的各层上，具有结点数最多的那一层的结点总数。本算法是按层次遍历二叉树，采用一个队列q，让根结点入队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。 [函数] int Width ( BinTree *T { int front=-1, rear=-1; /*队列初始化*/ int flag=0, count=0, p; /*p用于指向树中层的最右边的结点, flag 记录层中结点数的最大值*/ if ( T!=Null) { rear++; (1) ; flag=1; p=rear; } while ( (2) ) { front++; T=q [front]]; if (T->lchild!=Null ) { roar+-+; (3) ; count++; } if ( T-＞rchild!=Null ) { rear++; q[rear]=T-＞rchild; (4) ; } if (front==p ) // 当前层已遍历完毕 { if( (5) ) flag=count; count=0; p=rear, //p 指向下一层最右边的结点 } } return ( flag );}
