二叉树基于队列实现的操作详解

一、队列知识补充

有关队列的知识请详见博主的另一篇博客：http://t.csdnimg.cn/3PwO4

本文仅仅附上需要的队列操作供读者参考

//结构体定义
typedef struct BinaryTreeNode* QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType val;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;//入队
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = InitNewnode(x);if (pq->phead == 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);if (pq->phead->next == NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QNode* temp = pq->phead->next;free(pq->phead);pq->phead = temp;}pq->size--;
}
//取出队头元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}
//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* pcur = pq->phead;while (pcur){QNode* temp = pcur->next;free(pcur);pcur = temp;}pq->phead = pq->ptail = NULL;pq->size = 0;
}

二、层序遍历

2.1 递归思路

采用队列先进先出的特点，按照层序入队即可按照层序出队，从而达到层序遍历的目的。

考虑一般情况：

将根节点入队，下一次根节点出队的同时将孩子结点入队。

考虑特殊情况：

孩子结点可看作子树的根节点，重复递归即可。

只要队列不为空就一直递归

2.2 图解

2.3 C语言实现

注意：出队入队要额外新建变量来复制结点，避免销毁队列引发的原二叉树丢失的问题。

void TreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root){QueuePush(&q, root);}while (QueueEmpty(&q)==false){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->data);if (front->left){QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}}QueueDestroy(&q);
}

三、判断一棵树是不是完全二叉树

3.0 回顾

        什么是完全二叉树？完全二叉树是一种特殊的二叉树，其中除了最后一层外，每一层的节点都被填满，而且最后一层的节点都尽可能地靠左排列。换句话说，如果一个层次深度为k的树，除了第 k 层外，其他各层都是满的，并且第 k 层的节点都依次靠左排列，则这棵树就是完全二叉树。

        所以仅仅通过判断结点的范围处于k-1层满二叉树和k层满二叉树之间的解法是错误的！！       

3.1 思路

通过层序遍历，将第一次出现空结点的地方找到，只需判断后续遍历的过程中是否存在非空结点即可，若存在就不是完全二叉树，反之则是。

分两个循环解决该问题。

1. 第一层循环本质即为层序遍历，找到第一个空节点就退出。
2. 第二层循环依然为层序遍历，看是否可以找到非空结点。当队列里面没有元素即层序遍历结束时判断完成。

3.2 C语言实现

bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root != NULL){QueuePush(&q, root);}//入队遇到空停止入队while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL){break;}QueuePush(&q, front->left);QueuePush(&q, front->right);}//判断后面是否还有非空while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front != NULL){return false;}}QueueDestroy(&q);return true;
}