需要先创建一颗二叉树，然后才能学习其相关的基本操作，考虑到我们刚刚接触二叉树，
为了能够先易后难地进行讲解，这里将手动创建一颗简单的二叉树，用来方便大家学习。
等二叉树结构了解的差不多后，后期会研究二叉树的真正的创建方式。
（后面的层序遍历跟着的那篇OJ就是用前序遍历构建二叉树）
1.二叉树概念
二叉树是什么？① 空树 ② 非空：根节点、根节点的左子树与根节点的又子树组成的。
从概念中我们不难看出，二叉树的定义是递归式的。因此后续基本操作中，基本都是按照该概念来实现的，来看 A 的左子树，把 B 看作为根节点，又是颗二叉树。所以可以通过采用递归的手法来实现二叉树。
2.二叉树定义
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> typedef char BTDataType; typedef struct BinaryTreeNode { struct BinaryTreeNode* left; // 记录左节点 struct BinaryTreeNode* right; // 记录右节点 BTDataType data; // 存储数据 } BTNode; //创建新节点 BTNode* CreateNode(BTDataType x) { BTNode* new_node = (BTNode*)malloc(sizeof(BTNode)); if (new_node == NULL) { printf("malloc failed!\n"); exit(-1); } new_node->data = x; new_node->left = new_node->right = NULL; return new_node; } //手动创建二叉树 BTNode* CreateBinaryTree() { BTNode* nodeA = CreateNode('A'); BTNode* nodeB = CreateNode('B'); BTNode* nodeC = CreateNode('C'); BTNode* nodeD = CreateNode('D'); BTNode* nodeE = CreateNode('E'); BTNode* nodeF = CreateNode('F'); nodeA->left = nodeB; // A nodeA->right = nodeC; // B C nodeB->left = nodeD; // D E F nodeC->left = nodeE; nodeC->right = nodeF; return nodeA; } int main() { BTNode* root = CreateBinaryTree(); }
3.二叉树深度优先遍历
学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历，就是按照某种特定的规则，一次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。 访问节点所做的操作要看具体的应用问题。遍历是二叉树上最重要的运算之一，也是二叉树上进行其他运算的基础。
二叉树遍历（Traversal）：沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。 按照规则，二叉树的遍历有：前序 / 中序 / 后序 的递归或非递归遍历。除了前序、中序和后续遍历外，我们还可以对二叉树进行层序遍历。
比如二叉树的中序遍历：
3.1二叉树前序遍历
前序遍历（Preorder Traversal）：访问根节点的操作发生在遍历其右子树之前。即：首先访问根结点，然后遍历左子树，最后遍历右子树（根左右）。
代码实现前序遍历：
//二叉树前序遍历 void PreOrder(BTNode* root) { //首先判断根是否为空，为空就返回 if (root == NULL) { printf("NULL "); // 暂时打印出来，便于观察 return; } //走到这里说明不为空，根据前序遍历，先访问根节点 printf("%c ", root->data); //然后遍历左子树（利用递归） PreOrder(root->left); //最后遍历右子树（利用递归） PreOrder(root->right); // A // B C // D E F 前序：根 左 右 //执行输出： A B D NULL NULL NULL C E NULL NULL F NULL NULL }
① 首先判断根是否为空，如果根为空，则返回。这里为了表示，我们把空节点以 " Ø " 打印出来。
② 如果跟不为空，这说明有数据。由于是前序遍历（Preorder），前序遍历是先访问根节点，然后遍历左子树，最后再遍历右子树。所以，我们这里先要访问的是根节点，我们把根节点的数据打印出来。
③ 然后我们需要遍历左子树，这时我们利用递归就可以实现。将根节点 root 的左数 left 传入 PreOrder 函数（将其左树看作根），一直递归下去，直到碰到 root == NULL 则返回。
④ 最后，遍历完左子树后遍历右子树。利用递归，方法同上。
3.2二叉树中序遍历
递归的中序和后序和前序差不多 顺序换一下就行
//二叉树中序遍历 void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left); printf("%c ", root->data); InOrder(root->right); // A // B C // D E F 中序：左 根 右 //执行输出：NULL D NULL B NULL A NULL E NULL C NULL F NULL }
3.3二叉树后序遍历
void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%c ", root->data); // A // B C // D E F 后序：左 右 根 //执行输出：NULL NULL D NULL B NULL NULL E NULL NULL F C A }
4.二叉树的几个接口函数
下面我们实现几个接口函数
// 二叉树结点个数 int BinaryTreeSize(BTNode* root); // 二叉树叶子结点个数 int BinaryTreeLeafSize(BTNode* root); // 二叉树第k层结点个数 int BinaryTreeLevelKSize(BTNode* root, int k); // 二叉树查找值为x的结点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x); // 二叉树销毁 void BinaryTreeDestory(BTNode** root);
4.1 求二叉树结点个数
和上面遍历一样，采用分治的思想：是空就返回0，不是空就返回左子树的结点和右子树的结点+1（本身）。
int TreeSize(BTNode* root) { return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1; }
4.2 求二叉树叶子结点个数
同理，是空返回1，是叶子返回0，不是空也不是叶子的话就求其左子树的叶子+右子树的叶子
int TreeLeafSize(BTNode* root) { if (root == NULL) { return 0; } if (root->left == NULL && root->right == NULL) { return 1; } return TreeLeafSize(root->left) + TreeLeafSize(root->right); }
数据结构与算法⑭(第四章_下)二叉树的模拟实现和遍历代码（下）：https://developer.aliyun.com/article/1513455
