判断二叉树是否为完全二叉树算法（二叉树是否一种完全树）

本文目录

• 二叉树是否一种完全树
• 怎么判断是否是完全二叉树 用C++或C语言
• 判断完全二叉树用C语言编写
• 完全二叉树的算法
• 将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1
• 如何判断二叉树是否是完全二叉树 递归
• 编写函数判断一棵给定二叉树是否为完全二叉树
• 编写算法，判断一个二叉树链存储的二叉树是否为完全二叉树

二叉树是否一种完全树

1、含义不同：

完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

2、表示不同：

对于满二叉树，除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。而完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。

对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

判断一棵树是否是完全二叉树的思路

1》如果树为空，则直接返回错

2》如果树不为空：层序遍历二叉树

2.1》如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列；

2.1》如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树；

2.2》如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空，且则该节点之后的队列中的结点都为叶子节点，该树才是完全二叉树，否则就不是完全二叉树；

以上内容参考：百度百科-完全二叉树

怎么判断是否是完全二叉树 用C++或C语言

你可以上网先找一个用队列实现二叉树的广度优先搜索的代码，然后在代码中增加一个标志变量tag，初始化为0。然后找到代码中访问结点的那句代码，在那句代码处增加
if(tag==0)
判断该结点是否有两个孩子，如果没有两个孩子，则将tag=1
else
判断该结点是否为叶结点，如果不是叶结点，则不是完全二叉树。

判断完全二叉树用C语言编写

用一个线性表和一个队列，表存放的是边集，队列用于按层次遍历。程序流程如下

1 初始化空表、空队；

2 输入结点数、指定根结点，输入边到表中；

3 根结点进队；

4 将队首出队到p；

5 若表为空，返回1（真）。不空则在表中查找第一项等于p的边i。若找到，将边i的第二项进队，从表中删除边i。若没有找到，则返回0（假）。

6 若表为空，返回1（真）。不空则在表中查找第二项等于p的边i。若找到，将边i的第一项进队，从表中删除边i。若没有找到，则返回0（假）。

7 跳到4。

补充提供一个相应的程序代码如下，你可以试试

#include 《stdio.h》
#define N 1024

void main( )
{
    short list, listLength = 0, front = 0, rear = 0, r, n, i, p;/*1  初始化空表，空队*/
    char flag;   /*flag是判断结果标识*/
    scanf("%d%d", &n, &r);    /*2  输入结点数、指定根结点，输入边到表中*/
    for(i = 0; i 《 n - 1; i++)
        scanf("%d%d", &list);
    listLength = n - 1;
    queue = r;    /*3  根结点进队*/
    while(1) {
        p = queue;   /*4  将队首出队到p*/
        if(listLength == 0) {    /*5  如果表为空，则返回1（真）*/
            flag = 1;  
            break;
        }
        for(i = 0; i 《 listLength && list != p; i++);  /*寻找第一项等于p的边i*/
        if(i == listLength) {    /*如果没有找到，返回0（假）*/
            flag = 0;
            break;
        }
        queue;   /*将边i的第二项进队*/
        for(; i 《 listLength - 1; i++)        /*删除边i*/
            list;
        listLength--;

        if(listLength == 0) {   /*6  若表为空，返回1（真）*/
            flag = 1;
            break;
        }
        for(i = 0; i 《 listLength && list != p; i++);   /*在表中查找第二项等于p的边i*/
        if(i == listLength) {    /*如果没有找到，返回0（假）*/
            flag = 0;
            break;
        }
        queue;   /*将边i的第一项进队*/
        for(; i 《 listLength - 1; i++)           /*删除边i*/
            list;
        listLength--;
    }    /*7  跳到4*/
    if(flag)
        printf("yes\n");
    else
        printf("no\n");
}

运行结果

完全二叉树的算法

如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应，这棵二叉树称为完全二叉树。
可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0=n2+1，则n= n0+n1+n2（其中n为完全二叉树的结点总数），由上述公式把n2消去得：n= 2n0+n1-1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0=(n+1)/2或n0=n/2。
总结起来，就是 n0=表示上取整。可根据完全二叉树的结点总数计算出叶子结点数。

将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1

编号为49的结点的左孩子编号为98，公式是2i，不是2i+1。

举个简单的例子就可以看出来的，比如7个节点时（也就是三层时），编号为1的左子树编号是2，编号2的左子树是4，编号3的左子树编号为6，以此就可以看出来。

一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同。

算法思路

判断一棵树是否是完全二叉树的思路

如果树为空，则直接返回错

如果树不为空：层序遍历二叉树

如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列；

如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树；

以上内容参考：百度百科-完全二叉树

如何判断二叉树是否是完全二叉树 递归

bool isComplete(TreeNode * root, bool &isFull, int &deep)
{
isFull = true;
if (root == NULL) //空树为完全（且满）二叉树
return true;
isFull = false;
if (root-》left == NULL && root-》right != NULL)//右子树存在，左子树不存在则不是完全二叉树
return false;
deep = deep + 1;
//左子树的高度，左子树是满二叉树，左子树是完全二叉树吗？
int leftDeep = deep;
bool leftFull = false;
bool leftComplete = isComplete(root-》left, isFull, leftDeep);
//右子树的高度，右子树是满二叉树，右子树是完全二叉树吗？
int rightDeep = deep;
bool rightFull = false;
bool rightComplete = isComplete(root-》right, isFull, rightDeep);
deep = leftDeep;
//左右子树有一个不是完全二叉树，则树不是完全二叉树
if (!leftComplete || !rightComplete)
return false;
//左右子树为满二叉树，且左右子树深度一致，则此树为完全（且满）二叉树
if (leftFull && rightFull && leftDeep == rightDeep)
{
isFull = true;
return true;
}
//左右子树为满二叉树，且右子树近比左子树矮1，则此树为完全二叉树
if (leftFull && rightFull && leftDeep == (rightDeep + 1))
return true;
//左子树为非满二叉树，右子树为满二叉树，且右子树近比左子树矮1，则此树为完全二叉树
if (!leftFull && rightFull && leftDeep == (rightDeep + 1))
return true;
//否则为非完全二叉树
return false;
}

编写函数判断一棵给定二叉树是否为完全二叉树

#include《
iostream
》
#include《deque》
using
namespace
std;
struct
SHAGUO
{
char
data;
struct
SHAGUO
*lchild,*rchild;
};
typedef
SHAGUO*
bitree;
void
createtree(
bitree
&shaguo)
{
char
c;
cin》》c;
if(c==’#’)
shaguo
=
NULL;
else
{
shaguo
=
new
SHAGUO;
shaguo-》data
=
c;
createtree(shaguo-》lchild);
createtree(shaguo-》rchild);
}
}
int
isfulltree(SHAGUO
*t)//判断是否完全二叉树
{
deque《SHAGUO
*》shaguo;
SHAGUO
*p
=
NULL
;
shaguo.push_front(t);
while(!shaguo.empty())
{
p
=
shaguo.front();
shaguo.pop_front();
if(p)//不为空左右孩子入队
{
shaguo.push_back(p-》lchild);
shaguo.push_back(p-》rchild);
}
else
while(!shaguo.empty())//找到空节点
{
p
=
shaguo.front();
shaguo.pop_front();
if(p)//空节点后还有节点
非
{
cout《《"非完全二叉树"《《endl;
return
0;
}
}
}
return
1;
}
void
main()
{
SHAGUO
*
shaguo;
cout《《"先序输入二叉树节点
#代表空节点"《《endl;
createtree(shaguo);
if(isfulltree(shaguo))
cout《《"是完全二叉树"《《endl;
}
或者参考一下下面的帖子

编写算法，判断一个二叉树链存储的二叉树是否为完全二叉树

#include 《stdio.h》
#include 《stdlib.h》
#define Max 100
typedef struct Node
{
char data;
struct Node * LChild,*RChild;
}BiTNode,*BiTree;
void CreateBiTree(BiTree * bt)
{
char ch;
ch=getchar();
if(ch==10)ch=getchar();//如果为 回车换行 读取下一个字符
if(ch==’.’) *bt=NULL; //如果为 . 代表此节点为空
else
{
* bt=(BiTree)malloc(sizeof(BiTNode));
(* bt)-》data=ch; //赋值
CreateBiTree(&((* bt)-》LChild));
CreateBiTree(&((* bt)-》RChild));
}
}
bool fullBiTree(BiTree b)
{
if(b-》LChild==NULL && b-》RChild==NULL)return true;// 如果左右子树为空，返回真
if(b-》LChild==NULL || b-》RChild==NULL)return false;// 如果左右子树只有一个为空，返回假
return fullBiTree(b-》LChild) && fullBiTree(b-》RChild);// 通过递归，返回
}
void main()
{
printf("请依次输入字符\n");
BiTree b;
CreateBiTree(&b); //创建二叉树
bool cm=fullBiTree(b);
if(cm)printf("´此二叉树为完全二叉树\n");
else printf("´此二叉树不是完全二叉树\n");
}