首页 > 编程语言 > 详细

设计一个算法,判断一个二叉树是否为完全二叉树

时间:2015-07-08 02:06:53      阅读:797      评论:0      收藏:0      [点我收藏+]

思想:根据完全二叉树的定义,对完全二叉树按照从上到下、从左到右的层次遍历,应该满足一下两条要求:

某节点没有左孩子,则一定无右孩子

若某节点缺左或右孩子,则其所有后继一定无孩子

若不满足上述任何一条,均不为完全二叉树。

算法思路:采用层序遍历算法,用cm变量值表示迄今为止二叉树为完全二叉树(其初值为1,一旦发现不满足上述条件之一,则置cm为0),bj变量值表示迄今为止所有节点均有左右孩子(其初值为1),一旦发现一个节点没有左孩子或没有右孩子时置bj为0),在遍历完毕后返回cm的值。

对应的算法如下:

int CompBTNode(BTNode * b)

{

BTNode *Qu[MaxSize],*p; //定义一个队列,用于层次遍历

int front=0,rear=0; //队头、队尾指针

int cm=1;

int bj=1;

if(b!=NULL)

{

rear++;

Qu[rear]=b; //进队

while(front!=rear)

{

front++;

p=Qu[front];

if(p->lchild==NULL) //*p节点没有左孩子

{

bj=0;

if(p->rchild!=NULL) //没有左孩子但有右孩子

cm=0; //则不是完全二叉树

}

else //*p节点有左子树

{

if(bj==1) //迄今为止,所有节点均有左右孩子

{

rear++; //左孩子进队

Qu[rear]=b->lchild;

if(p->rchild==NULL) //*p有左孩子但没有右孩子

bj=0;

else

{

rear++; //右孩子进队

Qu[rear]=p->rchild;

}

else //bj=0:迄今为止,已有节点缺孩子

cm=0; //而此时*p节点有左孩子,违反(2)

}

}

return cm;

}

return 1; //把空树当成特殊的完全二叉树

}

版权声明:本文为博主原创文章,未经博主允许不得转载。

设计一个算法,判断一个二叉树是否为完全二叉树

原文:http://blog.csdn.net/wuruiaoxue/article/details/46797815

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!