前言
Hello,友友们，小编将继续重新开始数据结构的学习，前面讲解了堆的部分知识，今天将讲解二叉树的链式结构的部分内容。
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
