深度和广度优先遍历
代码实现二叉树的前中后序遍历，其实这种遍历叫深度优先遍历。即这种遍历和二叉树深度有关，访问到最深，递归回来继续访问其他的。
而层序遍历，就是广度优先遍历，即以根为主，一层一层往下遍历。借助队列的先进先出。核心思路就是：上一层带下一层。
层序遍历思路和代码实现
思路
借助队列先进先出的方法，以上面二叉树为例，先访问第一层根结点A，放到队列里面，此时判断队列不为空，因为有结点A。然后A出队列先遍历A。
再把下一层B和C放入队列，此时判断队列不为空。只取出结点B，一次只能取一个。
再把B的下一层D和E放入队列，此时判断队列不为空，队列有CDE。然后取出结点C。
结点C下面没有其他与之相连结点，此时队列还有DE，取出结点D。
D下面没有结点，此时队列还有E，取出结点E。E下一层也没有其他结点
最后判断队列为空，遍历结束。
即遍历结束标志：队列为空。
代码实现
队列相关代码
Queue.h
// 前置声明typedefcharBTDataType; typedefstructBinaryTreeNode{ structBinaryTreeNode*left; structBinaryTreeNode*right; BTDataTypedata; }BTNode; typedefstructBinaryTreeNode*QDataType; typedefstructQueueNode{ structQueueNode*next; QDataTypedata; }QNode; typedefstructQueue{ QNode*head; QNode*tail; }Queue; voidQueueInit(Queue*pq); voidQueueDestory(Queue*pq); // 队尾入voidQueuePush(Queue*pq, QDataTypex); // 队头出voidQueuePop(Queue*pq); QDataTypeQueueFront(Queue*pq); QDataTypeQueueBack(Queue*pq); intQueueSize(Queue*pq); boolQueueEmpty(Queue*pq);
Queue.c
voidQueueInit(Queue*pq) { assert(pq); pq->head=pq->tail=NULL; } voidQueueDestory(Queue*pq) { assert(pq); QNode*cur=pq->head; while (cur) { QNode*next=cur->next; free(cur); cur=next; } pq->head=pq->tail=NULL; } // 队尾入voidQueuePush(Queue*pq, QDataTypex) { assert(pq); QNode*newnode= (QNode*)malloc(sizeof(QNode)); if (newnode==NULL) { printf("malloc fail\n"); exit(-1); } newnode->data=x; newnode->next=NULL; if (pq->tail==NULL) { pq->head=pq->tail=newnode; } else { pq->tail->next=newnode; pq->tail=newnode; } } // 队头出voidQueuePop(Queue*pq) { assert(pq); assert(pq->head); // 1、一个// 2、多个if (pq->head->next==NULL) { free(pq->head); pq->head=pq->tail=NULL; } else { QNode*next=pq->head->next; free(pq->head); pq->head=next; } } QDataTypeQueueFront(Queue*pq) { assert(pq); assert(pq->head); returnpq->head->data; } QDataTypeQueueBack(Queue*pq) { assert(pq); assert(pq->head); returnpq->tail->data; } intQueueSize(Queue*pq) { assert(pq); intsize=0; QNode*cur=pq->head; while (cur) { ++size; cur=cur->next; } returnsize; } boolQueueEmpty(Queue*pq) { assert(pq); returnpq->head==NULL; }
层序遍历代码
voidLevelOrder(BTNode*root) { Queueq; QueueInit(&q); if (root!=NULL) QueuePush(&q, root); while (!QueueEmpty(&q)) //队列不为空则继续 { BTNode*front=QueueFront(&q); QueuePop(&q); printf("%c", front->data); if (front->left) //左边不为空 { QueuePush(&q, front->left); } if (front->right) { QueuePush(&q, front->right); } } printf("\n"); QueueDestory(&q); }
main函数直接调用LevelOrder();即可，括号里面加一个根结点，比如A。
