非递归求二叉树高度
算法
层序遍历求二叉树高度:设置变量
level
记录当前节点所在的层数,设置变量last
指向当前层最右节点,每次层次遍历出队时与last
指针比较,若二者相等,则层数加1,并让last
指向下一层最右节点。直至遍历完成,level
的值即为二叉树的高度
伪代码
const int N = 110;
BiTree q[N];
int depth(BiTree T)
{
if (!T) return 0;
int hh = -1, tt = -1;
int last = 0, level = 0;
q[++tt] = T;
while (hh < tt)
{
auto p = q[++hh];
if (p->lchild) q[++tt] = p->lchild;
if (p->rchild) q[++tt] = p->rchild;
if (hh == last) level++, last = tt;
}
return level;
}
非递归求二叉树宽度
算法
层序遍历求二叉树宽度:设置变量
last
指向当前层最右节点,每次层次遍历出队队头hh
与last
指针比较,若hh > last
,说明当前层节点已经遍历完,此时队列中全部是下一层节点,下一层节点数为tt - hh + 1
, 并让last
指向下一层最右节点。直至遍历完成
伪代码
const int N = 110;
BiTree q[N];
int width(BiTree T)
{
int max_width = 0;
if (!T) return 0;
int hh = -1, tt = -1;
int last = 0;
q[++tt] = T;
while (hh < tt)
{
auto p = q[++hh];
if (p->lchild) q[++tt] = p->lchild;
if (p->rchild) q[++tt] = p->rchild;
if (hh == last) max_width = max(max_width, tt - hh + 1), last = tt;
}
return max_width;
}
非递归求二叉树某一层k层节点数
算法
层序遍历求二叉树某一层节点数:设置变量
level
记录当前节点所在的层数,设置变量last
指向当前层最右节点,每次层次遍历出队队头hh
与last
指针比较,若二者相等,则层数加1,若level == k
, 则队列中元素个数就是第k层节点数
伪代码
const int N = 110;
BiTree q[N];
int k_cnt (BiTree T)
{
if (!T) return 0;
int hh = -1, tt = -1;
int last = 0, level = 0;
q[++tt] = T;
while (hh < tt)
{
auto p = q[++hh];
if (p->lchild) q[++tt] = p->lchild;
if (p->rchild) q[++tt] = p->rchild;
if (hh == last)
{
level++;
if (level == k) return tt - hh + 1;
last = tt;
}
}
return 0;
}
利用前序序列,中序序列建立二叉树
算法
递归