1.概念回顾与新增
二叉树是一种数据结构，其中每个节点最多有两个子节点，分别是左子节点和右子节点。二叉树的链式结构表示是使用指针（或引用）来连接节点，形成树形结构。每个节点包含一个数据元素和两个指向子节点的指针。
2.简单创建二叉树
分为节点的定义，创建节点，创建树
下面我们将简单的手撕一个二叉树：
typedef struct BTnode {
int val;
struct BTnode* left;
struct BTnode* right;
}Node;
//节点创建
Node* BuyNode(int x) {
Node* node = (Node*)malloc(sizeof(Node));
if (node == NULL) {
perror("node fail");
return NULL;
}
node->val = x;
node->left = NULL;
node->right = NULL;
return node;
}
//树的创建
Node* CreatTree() {
Node* node1 = BuyNode(1);
Node* node2 = BuyNode(2);
Node* node3 = BuyNode(3);
Node* node4 = BuyNode(4);
Node* node5 = BuyNode(5);
Node* node6 = BuyNode(6);
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
return node1;
}注意：上述代码并不是创建二叉树的方式，真正创建二叉树方式后序详解重点讲解。
二叉树建立过后，接下来我们要进行二叉树的遍历操作
3.二叉树的遍历
所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的结点进行相应的操作，并且每个结点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
按照规则，二叉树的遍历有： 前序 / 中序 / 后序的递归结构遍历 ：
1. 前序遍历 (Preorder Traversal 亦称先序遍历 )—— 访问根结点的操作发生在遍历其左右子树之前。
2. 中序遍历 (Inorder Traversal)—— 访问根结点的操作发生在遍历其左右子树之中（间）。
3. 后序遍历 (Postorder Traversal)—— 访问根结点的操作发生在遍历其左右子树之后。
由于被访问的结点必是某子树的根， 所以 N(Node ）、 L(Left subtree ）和 R(Right subtree ）又可解释为， 根的左子树和根的右子树 。 NLR 、 LNR 和 LRN 分别又称为先根遍历、中根遍历和后根遍历。
注意：为了方便理解，我们将空节点都视作为NULL
3.1前序遍历
代码：
void PreOrder(Node* root) {
if (root == NULL) {
printf("N ");
return;
}
printf("%d ", root->val);
PreOrder(root->left);
PreOrder(root->right);
}递归图解：
代码递归理解：
运行结果：1 2 3 N N N 4 5 N N 6 N N
注意：中序和后序与前序的递归展开图类似，小编就不在展示了。
3.2中序遍历
void InOrder(Node* root) {
if (root == NULL) {
printf("N ");
return;
}
InOrder(root->left);
printf("%d ", root->val);
InOrder(root->right);
}运行结果：N 3 N 2 N 1 N 5 N 4 N 6 N
3.3后序遍历
void PostOrder(Node* root) {
if (root == NULL) {
printf("N ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->val);
}运行结果:N N 3 N 2 N N 5 N N 6 4 1
3.4层序遍历
层序遍历 ：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根结点所在层数为1 ，层序遍历就是从所在二叉树的根结点出发，首先访问第一层的树根结点，然后从左到右访问第 2 层上的结点，接着是第三层的结点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
层序遍历较为复杂，这里我们采用队列的方式来实现层序遍历。
这里我们简单的用动态数组实现队列，包括了队列的初始化，入队出队判空的操作。
3.4.1队列的实现
// 队列结构
typedef struct Queue {
Node* data[MAX];
int front;
int rear;
} Queue;
// 初始化队列
void initQueue(Queue* q) {
q->front = 0;
q->rear = 0;
}
// 入队
void enqueue(Queue* q, Node* node) {
if ((q->rear + 1) % MAX == q->front) {
printf("Queue is full\n");
return;
}
q->data[q->rear] = node;
q->rear = (q->rear + 1) % MAX;
}
// 出队
Node* dequeue(Queue* q) {
if (q->front == q->rear) {
printf("Queue is empty\n");
return NULL;
}
Node* node = q->data[q->front];
q->front = (q->front + 1) % MAX;
return node;
}
// 判断队列是否为空
int isEmpty(Queue* q) {
return q->front == q->rear;
}3.4.2层序遍历实现
从根节点开始，将每个节点的值打印出来，并依次将其左子节点和右子节点加入队列。
// 层序遍历函数
void levelOrder(Node* root) {
if (root == NULL) {
return;
}
Queue q;
initQueue(&q);
enqueue(&q, root);
while (!isEmpty(&q)) {
Node* node = dequeue(&q);
printf("%d ", node->val);
if (node->left) {
enqueue(&q, node->left);
}
if (node->right) {
enqueue(&q, node->right);
}
}
}3.5主函数测试代码
int main() {
Node* root = CreatTree();
PreOrder(root);
printf("\n");
InOrder(root);
printf("\n");
PostOrder(root);
printf("\n");
levelOrder(root);
return 0;
}运行结果展示：
4.遍历相关选择练习
1. 某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为（ A）
A . ABDHECFG
B. ABCDEFGH
C. HDBEAFCG
D. HDEBFGCA
2. 二叉树的先序遍历和中序遍历如下：先序遍历： EFHIGJK; 中序遍历： HFIEJKG. 则二叉树根结点为（A）
A . E B. F C. G D. H
3. 设一课二叉树的中序遍历序列： badce ，后序遍历序列： bdeca ，则二叉树前序遍历序列为(D)
A. adbce B. decab C. debac D. abcde
4. 某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同一层从左到右）的序列 为(A)
A. FEDCBA
B. CBAFED
C. DEFCBA
D. ABCDEF
