首先,看一下完全二叉树的定义:
若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。
思路:可以采用广度优先的遍历方法,从根节点开始将所有的节点按层添加到队列里面,当遇到第一个没有左儿子或者右儿子的节点时,设置标志位,继续遍历,如果后面遇到了有子节点的节点,则不是完全二叉树。
代码:
//二叉树结点定义
typedef struct Node
{
int data;
struct Node* left;
struct Node* right;
}Node;
//实现广度遍历需要队列
Queue<Node*> queue;
//第n层最右节点标志
bool leftMost = false;
bool ProcessChild(Node* child)
{
if (child)
{
if (!leftMost)
queue.push(child);
else
return false;
}
else
{
leftMost = true;
}
return true;
}
bool IsCompleteBinaryTree(Node* root)
{
//空树也是完全二叉树
if (!root)
return true;
//首先根节点入队列
queue.push(root);
while(!queue.empty())
{
Node* node = queue.pop();
//处理左节点
if (!ProcessChild(node->left))
return false;
//处理右节点
if (!ProcessChild(node->right))
return false;
}
//广度优先遍历完毕,此乃完全二叉树
return true;
}
分享到:
相关推荐
写一算法,判断一棵二叉树是否是一棵二叉排序树。
在二叉树类binarytree中增加一个功能,判断是否为完全二叉树(使用自定义的队列类完成)
算法面试通关40讲完整课件 18-20 树、二叉树、二叉搜索树 算法面试通关40讲完整课件 18-20 树、二叉树、二叉搜索树 算法面试通关40讲完整课件 18-20 树、二叉树、二叉搜索树 算法面试通关40讲完整课件 18-20 树、...
编写算法判别给定二叉树是否为完全二叉树。
本程序提供了二叉树的各种操作:各种遍历,复制,求高度,判断是否为一棵完全二叉树以及计算用二叉树存储的表达式
/*选择二叉链式存储结构作为二叉树的存储结构,设计一个程序实现二叉树的基本操作(包括建立、输出、前序遍历、中序遍历、后序遍历、求树高、统计叶子总数等) 【实验内容】 必做内容 程序的菜单功能项如下: 1----...
//该程序用于判断二叉树是否为二叉排序树
算法大全-面试题-链表-栈-二叉树-数据结构,面试利器
判断两颗二叉树是否相似,C语言二叉树部分入门小程序,适合C语言课程的入门小练习 判断两颗二叉树是否相似,C语言二叉树部分入门小程序,适合C语言课程的入门小练习 判断两颗二叉树是否相似,C语言二叉树部分入门...
主要介绍了C语言判定一棵二叉树是否为二叉搜索树的方法,结合实例形式综合对比分析了C语言针对二叉搜索树判定的原理、算法、效率及相关实现技巧,需要的朋友可以参考下
一棵空树,或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值; (3)左、右子树也分别为二叉排序树...
包含排序,链表,图,队列,二叉树算法c++实现,这些c++是自己写的都能运行,另外还有一些c的算法实现
从键盘输入字符建立两棵二叉树,对两颗二叉树进行每个结点对比,从而判断两棵二叉树是否相等
算法大全-面试题-链表-栈-二叉树-数据结构.docx 一、单链表 目录 1.单链表反转 2.找出单链表的倒数第4个元素 3.找出单链表的中间元素 4.删除无头单链表的一个节点 5.两个不交叉的有序链表的合并 6.有个二级...
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 包含二叉树的建立,测试输出。。可直接运行。。
将一个数组的各个元素构造为二叉树,其中涉及到求叶子节点的函数,深度函数
判断一棵给定的二叉树是否为完全二叉树的算法,分几种情况,分别判断