知识点速览
在学二叉树之前我们需要作为补充了解树的几个名词概念。
C算法
数据结构：二叉树遍历与实现
系统讲解了二叉树的基础知识，包括树的名词解释、四种遍历方式（前序、中序、后序、层序）、满二叉树与完全二叉树的性质及推导公式。内容涵盖二叉树的 C 语言结构体定义、初始化、节点插入及遍历实现的代码示例，并通过多道练习题和 OJ 案例（如根据遍历序列还原树、计算节点数、求最大深度）巩固算法思维。适合复习数据结构与准备大厂面试的读者参考。
系统讲解了二叉树的基础知识，包括树的名词解释、四种遍历方式（前序、中序、后序、层序）、满二叉树与完全二叉树的性质及推导公式。内容涵盖二叉树的 C 语言结构体定义、初始化、节点插入及遍历实现的代码示例，并通过多道练习题和 OJ 案例（如根据遍历序列还原树、计算节点数、求最大深度）巩固算法思维。适合复习数据结构与准备大厂面试的读者参考。
在学二叉树之前我们需要作为补充了解树的几个名词概念。
这四种遍历其实并不难，下面小编带大家深刻理解这四种遍历！
首先前、中、后三种遍历中的的这三个关键字'前''中''后'都是根据根节点而言的，左子树永远在右子树前面，它的遍历都是将一个子树对应位置遍历完之后再遍历又一个子树，理解：每次不断分成不同大小的树，然后递归到末尾，再原路返回。小编以中序遍历为例，仔细讲解一下！最好的理解方式就是动手画到不出错为止！
根节点、左子树、右子树
遍历顺序：A->B->D->NULL->NULL->E->NULL->NULL->C->NULL->F->NULL->NULL
左子树、根节点、右子树
以 A 为根节点，先访问左子树，也就是这部分
再以 B 为根节点，再访问左子树，也就是这部分
再以 D 为根节点，访问其左子树，已经是这部分
此时已经到底了无法再分，访问'NULL'，然后访问根节点'D'，再访问 D 的右子树 'NULL'
以此类推，直到不能分为止，这里是利用了递归到 NULL 就返回的原理。
遍历顺序：NULL->D->NULL->B->NULL->E->NULL->A->NULL->C->NULL->F->NULL
左子树、右子树、根节点
遍历顺序：NULL->NULL->D->NULL->NULL->E->B->NULL->NULL->NULL->F->C->A
一层一层访问
遍历顺序：A->B->C->D->E->NULL->F->NULL->NULL->NULL->NULL->NULL->NULL
概念：每个父节点除最后一层的叶子节点外都有两个子节（满二叉树是一种特殊的完全二叉树）
性质（1）：假设根节点层数为 0，树层数为 K，那么它的节点个数 N 为 2^K-1，高度为 logN。
推论：第一层有 1 个节点（2^0），第二层有 2 个节点（2^1），第三层有 4 个节点（2^2），以此类推，得到节点数 N = 2^0 + 2^1 + 2^2 + 2^3 + ...... = 2^K - 1。此时 K = log(N+1)。
性质（2）：假设根节点层数为 0，二叉树第 K 层的节点数最多为 2^K 个。
性质（3）：任意一棵二叉树，假设度为 0 的节点数为 n0，度为 2 的节点数为 n2，满足以下关系：n0 = n2+1（只记结论）。
例如：假设现在有这样一棵树，度为 0 的节点数有 5 个，度为 2 的节点数有 4 个，满足 5=4+1。
概念：只有最后一层不满，且最后一层从左到右是连续的。
性质：节点总数 N 满足 N < 2^K-1，高度 K = log(N+1)。
推论：我们无法确定完全二叉树具体的节点个数，只能通过满二叉树进行推理。
，其它树亦如此。
套用公式：度为 0 的节点数（叶子节点）= 度为 2 的节点数 + 1，得到最终答案 200。
这是一棵完全二叉树，它的节点组成是度为 0 的、度为 1 的、度为 2 的总和，也就是：x0 + x1 + x2 = 2n，同时套用公式 x0 = x2 + 1，两个结合得到：2 * x0 + x1 - 1 = 2n。
我们观察图，发现完全二叉树度为 1 的节点只有一个，因此 x1 = 1，那么算出来得到 x0 = n。
我们假设高度为 h，最后一层缺了 x 个，同时知道满二叉树是特殊的完全二叉树。
那么满足：2^h-1 - x = 531。同时 x 的范围应该在【0，2 ^ h-1】，x 的范围如下图所示：
直接一个都不缺，为 0 个。
最多缺一个，x 为 2 ^ h-1 个。
结合这两个关系式，去套，最后得出只有当高度为 10 时满足（注意这里的层数从 0 开始）。
除了直接套用公式的题，如果出现节点总数求某个变量的值，似乎都要去通过建立方程表示节点总数，表示方式一般有两种：（1）不同度的节点数之和（2）通过节点总数满二叉树计算公式去计算。
咱们按照二叉树的结构，定义一个左子节点、右子节点、一个数据域就行了，这是最简单的定义。
// 重定义类型
typedef int Datatype;
typedef struct Tree {
// 左孩子节点
struct Tree* left;
// 右孩子节点
struct Tree* right;
// 数据域
Datatype data;
} Tree;
初始化我们开辟一个根节点返回就行了，以后将其作为参数再去连接左右节点。
// 初始化树
Tree* Perliminary(Datatype data) {
// 开辟根节点
Tree* newnode = (Tree*)malloc(sizeof(Tree));
// 判断有效性
if (newnode == NULL) {
printf("节点开辟失败\n");
return NULL;
}
// 初始化指针
newnode->data = data;
newnode->left = NULL;
newnode->right = NULL;
return newnode;
}
首先我们初始化了一个根节点，新增的节点值与根节点的值进行比较。
如果小于根节点的值，递归左子树；如果大于根节点的值，递归右子树；
随着递归的不断调用，它的根节点会不断改变，如果为空，就返回新增的节点。
最后回到最初的根节点。
// 新增节点
Tree* Capacity(Tree* TreeNode, Datatype data) {
// 如果是空节点就插入
if (TreeNode == NULL) {
return Perliminary(data);
}
// 如果是非空节点就继续递归
// 较小就插入到左子节点
if (data < TreeNode->data) {
TreeNode->left = Capacity(TreeNode->left, data);
} else {
TreeNode->right = Capacity(TreeNode->right, data);
}
// 回到原初的根节点
return TreeNode;
}
首先递归到子树的极端，遇到空就开始返回，再调整打印顺序。
// 前序遍历
Tree* Preorder(Tree* TreeNode) {
if (TreeNode == NULL) {
return;
}
// 根节点
printf("%d ", TreeNode->data);
// 左子树
Preorder(TreeNode->left);
// 右子树
Preorder(TreeNode->right);
}
// 中序遍历
Tree* Mid(Tree* TreeNode) {
// 如果遇到空返回
if (TreeNode == NULL) {
return;
}
// 左子树
Mid(TreeNode->left);
// 根节点
printf("%d ", TreeNode->data);
// 右子树
Mid(TreeNode->right);
}
// 后序遍历
Tree* Behind(Tree* TreeNode) {
// 递归到深处，如果是空就开始返回
if (TreeNode == NULL) {
return;
}
// 左子树
Behind(TreeNode->left);
// 右子树
Behind(TreeNode->right);
// 根
printf("%d ", TreeNode->data);
}
假设现在有这样一棵树
它的中序遍历结果为：D->B->E->A->F->C，后序遍历结果为：D->E->B->F->C->A。
按照中序顺序，我们去推得到 b 应该在最左边；按照后序顺序，我们得到 a 应该是根节点。
所以 a 是在根节点，再根据中序顺序，得到 a 的左边是 b，同时 c 是 a 的右子树，这样就能推出。
题目是要我们将前序遍历的节点结果返回。
思维讲解： 流程：用一个空间将每次遍历的值存储起来，然后返回。
（1）首先我们开辟数组，数组的空间大小最好是由节点个数决定，因此先遍历二叉树计算节点。
return root==NULL? 0 : treesize(root->left) + treesize(root->right) + 1;
（2）然后开辟对应大小的数组空间。
// 计算节点个数
int size=treesize(root);
// 开辟空间
int* arr=(int*)malloc(sizeof(int)*size);
（3）接下来就是递归遍历储存节点，但是要考虑一个问题，如果在这个函数里面去递归，那么每次调用都要去开辟空间，所以我们选择再开一个来进行递归遍历，参数是根节点、空间指针、计数。
注意：计数的 i 应该取地址，因为递归会开辟多个函数，不然每次 i 都只是一次拷贝而已。
// 存进空间
int i=0;
preorder_Traversal(root,arr,&i);
（4）然后将之前的前序遍历的打印换成储存即可。
// 前序遍历
if(root==NULL) {
return;
}
arr[*i]=root->val;
++(*i);
preorder_Traversal(root->left,arr,i);
preorder_Traversal(root->right,arr,i);
（5）最后：这是整型指针空间，返回的只是一个元素，所以按照题目要求，还有设置元素个数。
*returnSize = size;
return arr;
此题和上面这题几乎一模一样，就作为思维训练巩固给大家了！记得独立完成哦！
**思维讲解：**此题是求二叉树的最大深度，二叉树最大深度就是最大层数。
（1）假设有一棵树如上图，它的深度是 3。这里采用分治思想，先求左子树的深度为 3，再求右子树的深度为 2，再对比找最大值，然后返回 最大值 +1（因为一个节点层次为 1）。
（2）下面我们来实现，先递归左子树，再递归右子树，那么它是如何计算子树深度的呢？
假设递归到左子树的末尾，q 的左子树右子树都为空，返回 0，此时 0>0 为假，返回 0+1。
那么 q 拿到的就是 1。
假设递归到 c，c 的左右子树都不为空，继续递归，此时 d 的左右子树都为空返回，0>0 为假 d 拿到 1。
同理，e 拿到 1；1>1 为假，c 拿到的就是 1+1。其它节点类推即可。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online