个人主页: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; }
图解：
