作者：一个喜欢猫咪的的程序员
专栏：《数据结构》
喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》
目录
2.4.2二叉树第K层的节点个数（TreeLevelSize）：
2.7.1判断二叉树是否是完全二叉树（BinaryTreeComplete）
3.1test.c文件(二叉树实现):3.2Queue.h文件：
1.二叉树的概念及结构
1.1二叉树的概念
二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分。
1.2二叉树的类型分类：
二叉树分为两种：
- 完全二叉树
- 满二叉树
1.3二叉树的结构
由上图可知，二叉树是一个节点root，链接着一个左节点left和一个右节点right。
定义二叉树的结构：
typedef int BTDataType; typedef struct BinaryTreeNode {//二叉树的结构 BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode;
创建二叉树节点：
BTNode* BuyBTNode(BTDataType x) { BTNode*newnode=(BTNode*)malloc(sizeof(BTNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->left = newnode->right = NULL; return newnode; }
在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入，为了降低大家学习成本，此处手动快速创建一棵简单的二叉树.
这里手动链接各方便大家理解后面的操作，以及对测试用例的修改来测试接口函数是否正确符合要求.
//构造二叉树 BTNode* n1 = BuyBTNode(1); BTNode* n2 = BuyBTNode(2); BTNode* n3 = BuyBTNode(3); BTNode* n4 = BuyBTNode(4); BTNode* n5 = BuyBTNode(5); BTNode* n6 = BuyBTNode(6); BTNode* n7 = BuyBTNode(7); n1->left = n2;//链接二叉树 n1->right = n4; n2->left = n3; n4->left = n5; n4->right = n6; n3->left = n7;
2.接口实现及其具体细节的讲解
2.1知识铺垫：二叉树的遍历方式
遍历顺序分为4种：（root为根节点）
- 前序遍历：root 左子树 右子树
- 中序遍历：左子树 root 右子树
- 后序遍历：左子树 右子树 root
- 层序遍历：一层一层遍历（后面会单独讲）
如：前序遍历是每颗子树都先遍历root节点，再遍历左子树，最后在遍历右子树。
以下图为例：我们来了解一下前序遍历的顺序。
先root节点出1，然后是1的左子树（以2为根节点的子树）出2，再到2的左子树出3，再出3的左子树NULL，然后返回3的位置再走3的右子树然后出NULL，再返回2走2的右子树出NULL再返回到1的位置，1的右子树也是如此，以此类推。
还是以上图为例子，前中后序的顺序如下：
2.2前中后序遍历代码实现：
2.2.1前序遍历（PreOrder）：
前序遍历的遍历顺序：root 左子树 右子树
将一个二叉树分为根节点、左子树和右子树，它的子树也是可以这样分。
这样的操作是重复的，因此可以看成一个递归的底层过程。
只看最下面的部分的话
- 当root为NULL时，打印NULL。
- 当root不为NULL时，打印root->data的值。
只看最顶部 1 2 4的时候。
先打印root（1）,然后递归找到左子树（2）打印2，再递归找到右子树（4）打印4。
从局部映射到整体后，函数递归写法就是如此。
// 二叉树前序遍历 void PreOrder(BTNode* root) { //assert(root); if (root == NULL) { printf("NULL "); return; } printf("%d ", root->data); PreOrder(root->left); PreOrder(root->right); }
2.2.2中序遍历（InOrder）：
中序遍历与前序遍历不相同的地方就是在打印的先后顺序不同
因此递归的前后顺序随着改变。
// 二叉树中序遍历 void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left); printf("%d ", root->data); InOrder(root->right); }
2.2.3后序遍历（PostOrder）:
// 二叉树后序遍历 void PostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->data); }
2.3二叉树的节点个数和叶节点个数：
2.3.1二叉树节点的个数（TreeSize）：
二叉树节点的个数，可以看成左子树的节点个数+右子树的节点个数+1（根节点）。
遇到NULL返回0。
当只有1个节点时，它也有左子树(NULL)和右子树（NULL）。
当树为 1 2 4时，1的左子树为2，右子树为4。那2和4的左子树和右子树又是相当于只有一个节点的情况。
...
扩张到n个节点的情况下，就是递归不断向下找并且返回的过程。
// 二叉树节点个数 int TreeSize(BTNode* root) { if (root == NULL) return 0; return TreeSize(root->left) + TreeSize(root->right) + 1; }
2.3.2二叉树叶子节点的个数（TreeLeafSize）
计算叶子结点的个数，又跟就是二叉树节点个数不太一样
叶节点代表它没有左右节点了，也就是左右节点皆为NULL
- 当左右左右节点皆为NULL时返回1
- 叶节点数等于左子树的叶子个数+右子树的叶子个数
// 二叉树叶子节点个数 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); }
