求树的宽度.txt

来自「数据结构书上源代码（严蔚敏C语言版）以及二叉树的各种基本算法」· 文本 代码 · 共 49 行

②求树的宽度 
思想：按层遍历二叉树，采用一个队列q，让根结点入队列，最后出队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。 
int Width(BinTree *T) 
{ 
int 
front=-1,rear=-1;/* 
队列初始化*／ 
int flag=0,count=0,p; 
/* p用于指向树中层的最右边的结点，标志flag记录层中结点数的最大值。*／if(T!=Null) 
{ 
rear++; 
q[rear]=T; 
flag=1; 
p=rear; 
} 
while(front<p) 
{ 
front++; 
T=q[front]; 
if(T->lchild!=Null) 
{ 
rear++; 
q[rear]=T->lchild; 
count++; 
} 
if(T->rchild!=Null) 
{ 
rear++; 
q[rear]=T->rchild; 
count++; 
} 
if(front==p) 
/* 当前层已遍历完毕*/ 
{ 
if(flag<count) 
flag=count; 
count=0; 
p=rear; /* p指向下一层最右边的结点*/ 
} 
} 
/* endwhile*/ 
return(flag); 
}
本贴来自ZDNetChina中文社区 http://bbs.zdnet.com.cn ,本贴地址：http://bbs.zdnet.com.cn/viewthread.php?tid=1000761