求二叉树高度非递归算法(C语言)
收起
知与谁同
2018-07-20 18:01:33
3731
0
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;
}
2019-07-17 22:55:37