网站入门,个人网站的建设流程,查询网站服务商,建设网站出什么科目完全二叉树#xff1a;就是每层横着划过去是连起来的#xff0c;中间不会断开 比如下面的左图就是完全二叉树 再比如下面的右图就是非完全二叉树 那我们可以采用层序遍历的方法#xff0c;借助一个辅助队列
当辅助队列不空的时候#xff0c;出队头元素#xff0c;入队头…完全二叉树就是每层横着划过去是连起来的中间不会断开 比如下面的左图就是完全二叉树 再比如下面的右图就是非完全二叉树 那我们可以采用层序遍历的方法借助一个辅助队列
当辅助队列不空的时候出队头元素入队头元素的左右孩子
这里不同于层序遍历的是我们这里入左右孩子如果左右孩子是NULL我们也入队
当我们在重复执行上面的操作时我们会有一刻出队列的时候遇到NULL的情况 这时再对队列的剩余元素进行判断如果全是NULL则是完全二叉树否则是非完全二叉树
举例如下
先把根节点A入队
然后队列不空队头A出队A的左右孩子BC入队
然后队列不空队头B出队B的左孩子D 和NULL入队
然后队列不空队头C出队C的左右孩子E 和NULL入队
然后队列不空队头D出队D的左右孩子NULL入队 接下来队不空出队的元素是NULL 对于这种情况我们就需要把队列剩余元素看一下了如果队列剩余元素中有非NULL元素 那么该树就不是完全二叉树
代码如下
//队列相关操作
void InitQueue(SqQueue* Q);//初始化队列
void EnQueue(SqQueue* Q,BiTree T);//入队
void DeQueue(SqQueue* Q,BiTree* T)//出队头元素用T带回出队元素
int QueueEmpty(SqQueue Q);//判断队列是否为空//判断是否是完全二叉树
int IsComplete(BiTree T){if(TNULL){//空树是一种特殊的完全二叉树return 1;}SqQueue Q;//初始化一个辅助队列InitQueue(Q);EnQueue(Q,T);//根节点入队while(!QueueEmpty(Q)){//层序遍历BiTree p;DeQueue(Q,p);if(p!NULL){//出的队头元素非空//左右孩子入队EnQueue(Q,p-lchild);EnQueue(Q,p-rchild);}else{//出的队头元素是NULL//判断队列中剩余元素是否全是NULL//全是NULL——完全二叉树//不全是NULL——非完全二叉树while(!QueueEmpty(Q)){DeQueue(Q,p);if(p!NULL){return 0;}}}}return 1;
}
