大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。
严蔚敏那本教材上的说法:一个深度为k,节点个数为 2^k – 1 的二叉树为满二叉树。这个概念非常好理解,
就是一棵树,深度为k,而且没有空位。
首先对满二叉树依照广度优先遍历(从左到右)的顺序进行编号。
一颗深度为k二叉树,有n个节点,然后,也对这棵树进行编号,假设全部的编号都和满二叉树相应,那么这棵树是全然二叉树。
随意的一个二叉树,都能够补成一个满二叉树。这样中间就会有非常多空洞。在广度优先遍历的时候,假设是满二叉树,或者全然二叉树,这些空洞是在广度优先的遍历的末尾,所以,但我们遍历到空洞的时候,整个二叉树就已经遍历完毕了。而假设,是非全然二叉树,
我们遍历到空洞的时候,就会发现,空洞后面还有没有遍历到的值。这样,仅仅要依据是否遍历到空洞,整个树的遍历是否结束来推断是否是全然的二叉树。
算法例如以下:
// 推断是否还有未被訪问到的节点
while (!q.is_empty())
{
ptr = q.pop();
// 有未訪问到的的非NULL节点,则树存在空洞,为非全然二叉树
if (NULL != ptr)
{
return false;
}
}
return true;
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118806.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...