Question

求二叉树高度非递归算法（C语言）

给出算法就好了，给出必要说明。用层次遍历怎么实现

Answer 1

int BiTreeDepthHierarchy(BiThrTree T) //非递归类层次遍历求二叉树深度
{
int depth=0,hp,tp,lc; //hp为已访问的结点数，tp历史入队的结点总数，lc为每层最后一个结点标记
LinkQueue Q;
BiThrNode *p;
if(T)
{
p=T;
hp=0;tp=1;lc=1;
InitQueue(Q);
EnQueue(Q,p);
while(!QueueEmpty(Q))
{
DeQueue(Q,p);
hp++; //hp为已访问的结点数
if(p->lchild)
{
EnQueue(Q,p->lchild);
tp++; //tp记录历史入队的结点总数
}
if(p->rchild)
{
EnQueue(Q,p->rchild);
tp++;
}
if(hp==lc) //当hp=lc时，表明本层结点均已访问完
{
depth++;
lc=tp; //lc=tp，更新下层的末结点标记
}
}
}
return depth;
}