1. 链式存储
1.1 概念
二叉树的链式存储结构是指，
用链表来表示一棵二叉树，
即用链来指示元素的逻辑关系。
通常的方法是链表中每个结点由三个域组成
数据域和左右指针域，
左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。
链式结构又分为二叉链和三叉链，
当前我们学习中一般都是二叉链，
后面学到高阶数据结构如红黑树等会用到三叉链。
图示：
节点定义代码：
// 二叉链 struct BinaryTreeNode { struct BinTreeNode* pLeft; // 指向当前节点左孩子 struct BinTreeNode* pRight; // 指向当前节点右孩子 BTDataType _data; // 当前节点值域 } // 三叉链 struct BinaryTreeNode { struct BinTreeNode* pParent; // 指向当前节点的双亲 struct BinTreeNode* pLeft; // 指向当前节点左孩子 struct BinTreeNode* pRight; // 指向当前节点右孩子 BTDataType _data; // 当前节点值域 }；
1.2 应用
1.2.1 前序/中序/后序的递归结构遍历(深度遍历)简述
前序/中序/后序的递归结构遍历：是根据访问结点操作发生位置命名
NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
LNR：中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
LRN：后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。
NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
图示：此图可以较好的阐述前中后序遍历，根据访问顺序不同而结果不同
所以在写代码时只要更改访问顺序就能分别实现前中后序遍历。
代码实现：
定义节点：
typedef char BTDataType; typedef struct BinaryTreeNode { struct BinaryTreeNode* left; struct BinaryTreeNode* right; BTDataType data; }BTNode;
创造节点：
这里仅是模拟上图情况
BTNode* BuyNode(BTDataType x) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); if (node == NULL) { printf("malloc fail\n"); exit(-1); } node->data = x; node->left = node->right = NULL; return node; } BTNode* CreatBinaryTree() { BTNode* nodeA = BuyNode('A'); BTNode* nodeB = BuyNode('B'); BTNode* nodeC = BuyNode('C'); BTNode* nodeD = BuyNode('D'); BTNode* nodeE = BuyNode('E'); BTNode* nodeF = BuyNode('F'); nodeA->left = nodeB; nodeA->right = nodeC; nodeB->left = nodeD; nodeB->right = nodeE; nodeC->right = nodeF; return nodeA; }
1.2.1.1 前序遍历的实现
二叉树前序遍历函数：
先访问根节点再访问左孩子和右孩子，若为NULL则返回
void PreOrder(BTNode* root) { if (root == NULL){ printf("NULL "); return; } printf("%c ", root->data); PreOrder(root->left); PreOrder(root->right); }
1.2.1.2中序遍历的实现
二叉树中序遍历函数：
先一直访问左孩子再访问根节点再访问右孩子，若为NULL则返回
void InOrder(BTNode* root) { if (root == NULL){ printf("NULL "); return; } InOrder(root->left); printf("%C ", root->data); InOrder(root->right); }
1.2.1.3 后序遍历的实现
二叉树后序遍历函数：
先访问完它的左孩子和右孩子再访问根节点，若为NULL则返回
void PostOrder(BTNode* root) { if (root == NULL){ printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%C ", root->data); }
主函数：
int main() { BTNode* root = CreatBinaryTree(); PreOrder(root); printf("\n"); InOrder(root); printf("\n"); PostOrder(root); printf("\n"); return 0; }
可能你到了这里还是觉得模糊，不太理解，我画个图你就理解了：
前序遍历解析图：
中序后序也是相同的原理，不过访问根节点的顺序不同而已。
1.2.1.4 根据遍历结果重构二叉树
这也是考研常考内容
根据前中序遍历结果推断后序遍历结果或者画出这棵树
根据中后序遍历结果推断前序遍历结果或者画出这棵树
其实都是一样的思路，把树画出来，再求前or后序遍历顺序
在这里通过两个例子来带你学习怎么推算：
1.2.2 已知前中序遍历顺序求后序遍历顺序
1.若某二叉树的前遍历访问顺序是abdgcefh，中序遍历顺序是dgbaechf，则后序遍历的访问顺序是什么。
思路
前序遍历，先访问根节点，再访问左子树，最后访问右子树
故第1个访问的节点就是整个树的根节点
中序遍历，先访问左子树，再访问根节点，最后访问右子树
已知整个树的根节点，中序遍历顺序中以前序遍历访问的第一个节点为限，左边是左子树，右边是右子树。
再反复利用前序遍历结果，反复判断左右子树，直至叶子节点
是不是感觉好复杂？
画图带你理解：
前序遍历的第一个元素，就是树根，此处是a。
那么就能构造出下图所示的二叉树
根据“a”在中序出现的位置，将中序遍历的结果分成左右两棵子树，它们的中序遍历分别是：
{d,g,b} 和{e,c,h,f}；这两棵子树的前序结果：{b,d,g}和{c,e,f,h}。
现在我们重复步骤1、2，先构造左子树，再构建右子树。
如下图所示：
故最终树结构为
此时再根据树结构来推算后序遍历的顺序为：gdbehfca
1.2.3 已知中后序遍历顺序求前序遍历顺序
已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和 DECBHGFA，请求前序遍历顺序。
和上面的思路相同：
思路
后序遍历，先访问左子树，再访问右子树，最后访问根节点
故最后1个访问的节点就是整个树的根节点
中序遍历，先访问左子树，再访问根节点，最后访问右子树
已知整个树的根节点，中序遍历顺序中以后序遍历访问的最后一个节点为限，左边是左子树，右边是右子树。
再反复利用后序遍历结果，反复判断左右子树，直至叶子节点
同样画图演示：
后序遍历的最后一个元素，就是树根，此处是A。
那么就能构造出下图所示的二叉树
根据“A”在中序出现的位置，将中序遍历的结果分成左右两棵子树，它们的中序遍历分别是：
{B,D,C,E} 和{F,H,G}；这两棵子树的后序结果：{D,E,C,B}和{H,G,F}。
现在我们重复步骤1、2，先构造右子树，再构建左子树。
如下图所示：
故最终树结构为
此时再根据树结构来推算前序遍历的顺序为：ABCDEFGH
1.2.4 已知前后序遍历顺序可以求中序遍历顺序吗？
不可以。
因为它不能重构出唯一的二叉树。
举例：
情况一：
假设前序结果是{C,A,B}，后序结果是{B,A,C}
那么二叉树的结构可能如下：
这种情况下，二叉树并不唯一；
情况二：
假设前序结果是{C,A,B}，后序结果是{A,B,C}
那么二叉树的结构如下：
1.2.5 层次遍历(广度遍历)
除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。
设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
图示：自上而下，自左至右逐层访问树的结点
思路
你看我们要将每一层从上到下，从左至右，依次访问。
所以想到了使用队列这一数据结构的性质，
先入根，当前节点出来，把孩子带进去，
这样上一层节点出的时候，带入下一层，
直至队列为空，说明最后一层没有节点了，遍历结束。
图示
注意：此图队列中（黑色框中）红色元素为将要Pop的元素，然后右边是其左右孩子节点的进入，为空则不进入。
如上，这就实现了层次遍历
代码实现
得实现两个数据结构，而且注意进入队列中的元素是树的节点
队列的实现就不过多赘述了，相信各位看官可以自行理解~~
层次遍历的代码会做注释方便理解。
Test.c
先构建一棵树：
typedef char BTDataType; typedef struct BinaryTreeNode { struct BinaryTreeNode* left; struct BinaryTreeNode* right; BTDataType data; }BTNode; BTNode* BuyNode(BTDataType x) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); if (node == NULL) { printf("malloc fail\n"); exit(-1); } node->data = x; node->left = node->right = NULL; return node; } BTNode* CreatBinaryTree() { BTNode* nodeA = BuyNode('A'); BTNode* nodeB = BuyNode('B'); BTNode* nodeC = BuyNode('C'); BTNode* nodeD = BuyNode('D'); BTNode* nodeE = BuyNode('E'); BTNode* nodeF = BuyNode('F'); nodeA->left = nodeB; nodeA->right = nodeC; nodeB->left = nodeD; nodeB->right = nodeE; nodeC->right = nodeF; return nodeA; }
层次遍历函数：
void BinaryTreeLevelOrder(BTNode* root) { if (root == NULL)//节点为空则返回 return; Queue q; QueueInit(&q);//队列初始化 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);//销毁队列 }
二叉树销毁函数：
注意：这里销毁的原理是：后序列遍历，将节点一个个free掉。
void BinaryTreeDestory(BTNode* root) { if (root == NULL) { return; } BinaryTreeDestory(root->left); BinaryTreeDestory(root->right); free(root); }
主函数：
int main() { BTNode* root = CreatBinaryTree(); BinaryTreeLevelOrder(root); BinaryTreeDestory(root); root = NULL; return 0; }
Queue.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> // 前置声明 struct BinaryTreeNode; typedef struct BinaryTreeNode* QDataType; //数据类型为树的节点 typedef struct QueueNode { struct QueueNode* next; QDataType data; }QueueNode; typedef struct Queue { QueueNode* head; QueueNode* tail; }Queue; void QueueInit(Queue* pq); void QueueDestroy(Queue* pq); void QueuePush(Queue* pq, QDataType x); void QueuePop(Queue* pq); QDataType QueueFront(Queue* pq); bool QueueEmpty(Queue* pq);
Queue.c
#include "Queue.h" void QueueInit(Queue* pq) { assert(pq); pq->head = NULL; pq->tail = NULL; } void QueueDestroy(Queue* pq) { assert(pq); QueueNode* cur = pq->head; while (cur != NULL) { QueueNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; } void QueuePush(Queue* pq, QDataType x) { assert(pq); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); newnode->data = x; newnode->next = NULL; if (pq->head == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } } void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); QueueNode* next = pq->head->next; free(pq->head); pq->head = next; if (pq->head == NULL) { pq->tail = NULL; } } QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; }
后记
这一篇讲述了二叉树链式存储，前中后序遍历，以及怎么根据前中，后中的遍历结果推出二叉树的结构，和层次遍历的实现。
下一篇将讲述一些二叉树的OJ题，感谢支持，如果有什么问题，可在评论区提出！
