专栏首页为学判断是否为完全二叉树

判断是否为完全二叉树

判断是否为完全二叉树

题目要求及思路分析

  • 题目:编写算法判别给定二叉树是否为完全二叉树。 —《数据结构习题集(C语言版)》
  • 思路:
    • 使用层序遍历二叉树
    • 若完全二叉树中的某个结点没有左孩子,则其一定没有右孩子
    • 若完全二叉树中的某个结点缺左孩子或右孩子,则其一定没有后继结点

算法实现

1.二叉树及队列的结构体定义

/*-------二叉树的二叉链结点结构定义------*/

#define TElemType char


typedef struct BiTNode{          // 结点结构
    TElemType data;             // 结点数据
    struct BiTNode *lchild, *rchild;    // 左右 孩子指针
} BiTNode, *BiTree;

/*-------队列的数据结构定义------*/

#define MAXSIZE 1000


typedef struct {
    BiTree data[MAXSIZE];
    int front;
    int rear;
}SqQueue;

2.队列的基本操作

*----------以下为队列的基本操作函数----------*/

/*初始化一个空队列*/
Status InitQueue(SqQueue *Q){
    if (!Q)return ERROR;             //若空间分配失败,则返回ERROR
    Q->front = 0;
    Q->rear = 0;
    return OK;
}

/*判断SqQueue是否为空*/
Status IsQueueEmpty(SqQueue Q){
    if (Q.rear == Q.front)return TRUE;           //若尾指针指向头指针,则为空队列,返回TRUE
    else{ return FALSE; }                        //否则返回FALSE     
}

/*插入元素e为新的队尾元素*/
Status EnQueue(SqQueue *Q, BiTree e){
    if ((Q->rear + 1)  == MAXSIZE)return ERROR;    // 若队列已满,则返回ERROR
    Q->data[Q->rear] = e;           //e 入队列 
    Q->rear = (Q->rear + 1);                      //队尾指针后移
    return OK;
}

/*若队列不空,则删除队头元素,并用e返回其值*/
Status DeQueue(SqQueue *Q, BiTree *e){

    if (Q->front == Q->rear)return ERROR;    //若队列为空,则返回ERROR
    *e = Q->data[Q->front];                 //若队列不为空,用e接收队头元素
    Q->front = Q->front + 1;        //队头指针后移

    return OK;
}
/*----------队列的基本操作函数结束----------*/

3.二叉树的基本操作

/*-----------基本操作的函数-------------*/
//按照二叉树的定义初始化一个空树
Status InitBiTree(BiTree *bt){

    *bt = (BiTree )malloc(sizeof(BiTNode));
    if (!bt)return OVERFLOW;

    *bt = NULL;

    return OK;
}

//构造二叉链表表示的二叉树T
//按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树
Status CreateBiTree(BiTree *T){
    TElemType ch;

    printf_s("请输入数据:");
    scanf_s("%c", &ch);
    getchar();                      //getchar()用于处理回车占字符的问题
    if (ch == '#')
        *T = NULL;
    else{
        *T = (BiTree)malloc(sizeof(BiTNode));

        if (!T)return OVERFLOW; // 若内存分配失败,则返回OVERFLOW

        (*T)->data = ch;            // 生成根结点
        CreateBiTree(&((*T)->lchild));  //构建左子树
        CreateBiTree(&((*T)->rchild));  //构建右子树
    }

    return OK;
}

4.判断二叉树是否为完全二叉树 ​

Status IsCompleteBiTree(BiTree T){
    if (!T)return TRUE;             // 若为一个空树,则直接结束

    int flag = 0;               //设立一个flag,若某结点有左右孩子则为0;若某一个空了,则为1

    SqQueue Q;
    BiTree* e;
    e = (BiTree *)malloc(sizeof(BiTree));

    InitQueue(&Q);
    EnQueue(&Q, T);             //将根结点入队列

    while (DeQueue(&Q, e)){     //当队列不空时
        if (!(*e)){             //若当前元素为空,则flag = 1,直接进行下一个循环
            flag = 1;
            continue;
        }else if (flag){        //若当前元素不为空,且flag == 1,则证明该数不为完全二叉树
            return FALSE;
        }else{
            EnQueue(&Q, (*e)->lchild);
            EnQueue(&Q, (*e)->rchild);
        }
    }


    printf_s("\n");
    return TRUE;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 二叉树及其四种遍历

    本次主要是针对二叉树的基本操作,另外还有二叉树相似的判断和叶子结点的计数,这些方法中都用到了递归。关于结构体的预定义还是会放在之前的博客(数据结构常用于定义总结...

    李志伟
  • 队列的基本操作(简单版)

    李志伟
  • Java基础---简易提款机

    1.创建用户类User(包含卡号、姓名、密码、余额等属性),用户开卡时录入的姓名和密码(自动分配一个卡号、初始金额设置为0)。

    李志伟
  • 改进版CodeTimer及XCode性能测试

    在测试XCode性能的时候,发现每次执行测试程序得到的执行时间差距实在太大,于是采用了老赵的CodeTimer来计算线程时间,后来因为测试程序稍微有点复杂,在使...

    大石头
  • 高效开发的4条原则

    做好单元测试、集成测试,确保对于核心业务有足够测试。如果你的测试覆盖不足,那么客户早晚会帮你找出bug。

    dys
  • Linux-Shell脚本

    shift命令可以造成参数变量,拿掉前面那个参数。如果加上数字作为参数的话,可以拿掉最前面的n个参数。 例子:

    悠扬前奏
  • Oops首页被人挂黑页

    Wikileaks 维基解密Oops首页被人挂黑页 ? Oops!维基解密被臭名远扬的黑客组织OurMine挂了黑页! 据Twitter上的截图显示,维基解密官...

    企鹅号小编
  • 浅谈大型互联网的企业入侵检测及防护策略

    如何知道自己所在的企业是否被入侵了?是没人来“黑”,还是因自身感知能力不足,暂时还无法发现?其实,入侵检测是每一个大型互联网企业都要面对的严峻挑战。价值越高的公...

    美团技术团队
  • 「首席看容器云架构」K8s 多区域部署

    Kubernetes 1.2增加了在多个故障区域中运行单个集群的支持(GCE称它们为“区域”,AWS称它们为“可用区域”,在这里我们将它们称为“区域”)。这是...

    首席架构师智库
  • 1、根据SC数据库用SQL语句完成以下任务。

    update SC set Grade=Grade+5 whereGrade<60;

    week

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动