百度网盘官方网站,上海公司有哪些,主机托管,wordpress域名授权1.判断二叉树是否是完全二叉树
辨别#xff1a;
不能使用递归或者算节点个数和高度来判断。 满二叉树可以用高度和节点来判断#xff0c;因为是完整的。
但是完全二叉树前面是满的#xff0c;但是最后一层是从左到右连续这种
如果仍然用这种方法的话#xff0c;如下图…1.判断二叉树是否是完全二叉树
辨别
不能使用递归或者算节点个数和高度来判断。 满二叉树可以用高度和节点来判断因为是完整的。
但是完全二叉树前面是满的但是最后一层是从左到右连续这种
如果仍然用这种方法的话如下图两个识别方法是一样的但是无法准确识别 完全二叉树前h-1层是满的最后一层是从左到右连续。
如果走层序那么一定是连续的也就是说要通过层序遍历来走。
思路1.层序遍历走空也进序列。
2.遇到第一个空时开始判断如果后面都为空则是完全二叉树若空后面还出席那非空的情况则说明不是完全二叉树。
代码实现
//判断二叉树是否是完全二叉树
bool TreeComplete(BTNode* root)
{ Queue q;//仍然使用队列去实现QueueInit(q);if (root)QueuePush(q,root)while (!QueueEmpty){BTNode* front QueueFront(q);QueuePop(q);//遇到第一个空就可以开始判断如果队列中还有非空就不是完全二叉树。if (front NULL){break;}QueuePush(q, front-left);QueuePush(q, front-right);}while (!QueueEmpty){BTNode* front QueueFront(q);QueuePop(q);//如果仍有非空元素直接
// return false;if (front){QueueDestroy(q);//如果存在非空。return false;}QueueDestroy(q);return true;
//最终QueueDestroy再返回}
}
补充队列的一系列实现
void QueueInit(Queue* pq)
{assert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}// 队尾插入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-next NULL;newnode-val x;if (pq-ptail NULL){pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}// 队头删除
void QueuePop(Queue* pq)
{assert(pq);assert(pq-size ! 0);/*QNode* next pq-phead-next;free(pq-phead);pq-phead next;if (pq-phead NULL)pq-ptail NULL;*/// 一个节点if (pq-phead-next NULL){free(pq-phead);pq-phead pq-ptail NULL;}else // 多个节点{QNode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq-phead);return pq-phead-val;
}QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq-ptail);return pq-ptail-val;
}int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}
//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}
