【二叉树广度优先遍历和深度优先遍历】

---

一、二叉树的深度优先遍历

学习二叉树结构，最简单的方式就是遍历。

所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉
树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。

遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

0.建立一棵树

typedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;}BTNode;int main()
{BTNode* A = (BTNode*)malloc(sizeof(BTNode));A->data = 'A';A->left = NULL;A->right = NULL;BTNode* B = (BTNode*)malloc(sizeof(BTNode));B->data = 'B';B->left = NULL;B->right = NULL;BTNode* C = (BTNode*)malloc(sizeof(BTNode));C->data = 'C';C->left = NULL;C->right = NULL;BTNode* D = (BTNode*)malloc(sizeof(BTNode));D->data = 'D';D->left = NULL;D->right = NULL;BTNode* E = (BTNode*)malloc(sizeof(BTNode));E->data = 'E';E->left = NULL;E->right = NULL;A->left = B;A->right =C;B->left = D;B->right = E;return 0;
}

结果如下：

1. 前序遍历

访问根结点的操作发生在遍历其左右子树之前。

先访问根节点，再到左子节点，然后到右子节点。
根->左->右

//后序遍历
void PrevOrder(BTNode* root)
{if (root == NULL){return;}printf("%c ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}

2.中序遍历

2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。

先访问左子树，再访问根，再到右子树
左–>根–>右

由于NULL不打印出来，故结果为 D->B->E->A->C

代码如下：

//中序遍历
void InOrder(BTNode* root)
{if (root == NULL){return;}InOrder(root->left);printf("%c ", root->data);InOrder(root->right);
}

代码分析：

3. 后序遍历

3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

先访问左子节点，再访问右子节点，最后访问根。
左–>右–>根

分析结果如下
打印结果为： D E B C A

代码如下：

//后续遍历
void PostOrder(BTNode* root)
{if (!root){return;}PostOrder(root->left);PostOrder(root->right);printf("%c ", root->data);
}

代码分析如下：

二叉树的前序，中序，后序遍历结果如下：

二、二叉树的广度优先遍历

层序遍历

层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1

层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点

以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

层序遍历就是一层一层地访问，先访问第一层， 再访问第二层。
核心思想是上一层出去带下一层进来

实现的过程不使用递归实现，使用队列实现：
借助队列先进先出的特点

队列源代码：

typedef struct BinaryTreeNode* QDataType;typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;void QueueInit(Queue* pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;pq->size = 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* del = cur;cur = cur->next;free(del);//del = NULL;}pq->head = pq->tail = NULL;pq->size = 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");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;}pq->size++;
}void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* del = pq->head;pq->head = pq->head->next;free(del);}pq->size--;
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->head == NULL && pq->tail == NULL;
}

实现层序遍历过程中二叉树借助队列源代码：

//借助队列的先进先出来实现层级递进
void LevelOrder(BTNode* root)
{//核心思路，上一层出的时候带下一层Queue q;QueueInit(&q);if (root){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");QueueDestroy(&q);
}

三、有关二叉树练习

1.某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。
该完全二叉树的前序序列为（ ）
A ABDHECFG
B ABCDEFGH
C HDBEAFCG
D HDEBFGCA

解析：
已知该树为完全二叉树，第一层只有一个节点，第二层有2个节点，第三层有4个节点…
容易知道该完全二叉树的高度是4，还原可得：

根据前序序列遍历，先根，再左子节点，再右子节点，选A

2.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则二叉树根结点为（）
A E
B F
C G
D H

解析：由二叉树的前序遍历可知，根节点为E。
此时已经得出答案，但我想还原这棵树
由中序遍历可知：E是根节点，那么E左边的所有节点为HFI，右边的所有节点为JKG
由前序遍历可知，E到F，说明F是E的左子节点，由中序遍历，H到F，说名H是F的左子节点。到这里可以还原二叉树的左半部分了，右半部分同理。

3.设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，
则二叉树前序遍历序列为____。
A adbce
B decab
C debac
D abcde

解析：
由二叉树的后序遍历可知根节点为a。
由中序序列可知a的左子节点只有b，右子节点右dce
又由后序遍历往前推，可知c是a的右子节点
到这里已经可以推出整棵树了

所以该树的前序序列为abcde，选D

4.某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，
则按层次输出（同一层从左到右）的序列为
A FEDCBA
B CBAFED
C DEFCBA
D ABCDEF

解析：
由二叉树的后序遍历可知，根节点为F，由中序遍历可知，根节点F无右子节点。
F的左节点有ABCDE
又因为前序和中序都相同，那么只有一种情况：

所以答案选A