前言
在之前的二叉树的顺序结构中我们发现，该二叉树对于堆（一种完全二叉树）非常实用，但是对于非完全二叉树就会出现以下的结构，造成空间浪费：
所以这里我们还是要通过链式结构来实现二叉树。但是其实普通二叉树是没有什么意义的，增删查改没有多大的意义。真正有意义的是搜索二叉树：
搜索二叉树的特点是左子树比根大/小，右子树比根小/大。这里的二叉树可以用来搜索，也可以用来进行插入，删除等操作，拥有实际的意义。所以对于普通二叉树，我们不用学习他的增删查改，只用学习他的遍历等操作，并且复习一下递归的相关知识。
一.二叉树的理解：
我们先回顾一下回顾下二叉树的概念，二叉树是：
空树
非空：根节点，根节点的左子树、根节点的右子树组成的。
对于一颗二叉树，我们看到它就要把他分为：根，左子树，右子树。对于左子树，在把他分为：根，左子树，右子树。对于右子树，在把他分为：根，左子树，右子树……以此类推直到左右子树都为空才停止。
从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。
二.二叉树的遍历：
学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的每个节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历。我们以这颗二叉树为例：
创建二叉树：
typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; BTNode* BuyNode(BTDataType x) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); if (node == NULL) { perror("malloc::fail"); return; } node->left = NULL; node->right = NULL; node->data = x; return node; } BTNode* CreatTree() { BTNode* node1 = BuyNode(1); BTNode* node2 = BuyNode(2); BTNode* node3 = BuyNode(3); BTNode* node4 = BuyNode(4); BTNode* node5 = BuyNode(5); BTNode* node6 = BuyNode(6); BTNode* node7 = BuyNode(7); node1->left = node2; node1->right = node4; node2->left = node3; node4->left = node5; node4->right = node6; node3->right = node7; return node1; }
1.前序遍历：
前序遍历的顺序是：根，左子树，右子树。
代码实现：
void PreOrder(BTNode* root) { if (root = NULL) { printf("NULL "); return; } printf("%d ", root->data); PreOrder(root->left); PreOrder(root->right); }
结果：
2.中序遍历：
中序遍历的顺序是：左子树，根，右子树。
代码实现：
void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left); printf("%d ", root->data); InOrder(root->right); }
结果：
3.后序遍历：
后序遍历的顺序是：左子树，右子树，根。
代码实现：
void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->data); }
结果：
其实上面的三种遍历就是通过s三句代码的顺序导致结果的不同，当然他们的递归过程都能用下面这张图来代表：
4.层序遍历：
除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历
那么如何实现层序遍历呢？这里我们就要用到我们之前所学的队列了！
在这里，我们将二叉树的根先进队列，然后将其出队列，每出一次，就让其左右子结点进入队列，随后在出一个队列，将其左右子节点加入队列……这样通过队列的push和pop就能实现层序遍历
我们首先将队列的代码导入即可，就可以创建队列了：
代码实现：
void LevelOrder(BTNode* root) { Queue q; QueueInit(&q); if (root) { QueuePush(&q, root); } while (!QueueEmpty(&q)) { BTNode* front= QueueFront(&q); QueuePop(&q); printf("%d ", front->data); if (front->left) { QueuePush(&q, front->left); } if (front->right) { QueuePush(&q, front->right); } } QueueDestroy(&q); }
注意：
这里我们放入队列的不是要打印的数据，而是树结点的指针，为什么呢？如果我们存入的是要打印的数据（整形数据），那么我们无法找到他们的子节点!所以我们每次pop出一个指针，然后push这个指针（结点）的子节点即可。图解如下：
