个人主页:Lei宝啊

愿所有美好如期而遇

---

目录

二叉树层序遍历：

判断完全二叉树：

---

二叉树层序遍历：

层序遍历就是一层一层，从上到下遍历，上图遍历结果为：4 2 7 1 3 6 9

---

思路：

通过队列来实现层序遍历，让父节点带孩子节点。将父节点入队列，当其孩子节点不为空时，入队列，将父节点出队列，依次类推。

代码：

树的结构：

typedef struct BT_Tree
{char data;struct BT_Tree* left;struct BT_Tree* right;
}BT_Tree;

 队列结构：

typedef struct BT_Tree* DataType;
typedef struct Queue
{DataType data;struct Queue *next;
}Queue;typedef struct Q
{Queue* head;Queue* tail;int size;
}Q;

层序实现： 

void Sequence(BT_Tree* node)
{if (node == NULL){printf("NULL\n");return;}Q queue;Init(&queue);QueuePush(&queue, node);while (!Empty(&queue)){BT_Tree* front = GetQueueFrontNum(&queue);printf("%d ", front->data);if (front->left)QueuePush(&queue, front->left);if (front->right)QueuePush(&queue, front->right);QueuePop(&queue);}}

图解： 

---

判断完全二叉树：

思路：

这里同层序遍历的思路非常相似，但是不同的地方在于这里孩子节点为空我们仍要将其入队列，最后我们检查队列，若队列空后仍有非空的值，则不是完全二叉树。

代码：

bool JudgeTreeComplete(BT_Tree* node)
{if (node == NULL)return true;Q queue;Init(&queue);QueuePush(&queue, node);while (!Empty(&queue)){BT_Tree* front = GetQueueFrontNum(&queue);if (front == NULL)break;QueuePush(&queue, front->left);QueuePush(&queue, front->right);QueuePop(&queue);}while (!Empty(&queue)){BT_Tree* front = GetQueueFrontNum(&queue);if (front != NULL){Destroy(&queue);return false;}QueuePop(&queue);}Destroy(&queue);return true;}

图解：

---