【数据结构】·励志大厂版（复习+刷题）：二叉树

前引：哈喽小同伴们！颠末几个月的隔断，还是逃走不了再次复习的运气！！！本篇文章没有冗杂的闲话，满是干货教学，带你横扫二叉树的几种遍历，怎么前序、、中序、后续？怎样辨认？二叉树着实惆怅就是它的递归，代码量着实并不多，插入与遍历打印都是递归，但是本篇文章完全就是buuff加身，看完还不会二叉树的欢迎在品评区留言，小编继续检验！~~正文开始
目录
 知识点速览
树的名词表明
二叉树的四种遍历
二叉树性质：
满二叉树：
完全二叉树：
训练题（1）
训练题（2）
训练题（3）
训练总结
二叉树实现
界说结构体
初始化
新增节点
前序遍历
 中序遍历
 后序遍历
二叉树OJ（1）
二叉树OJ（2）
二叉树OJ（3）
二叉树OJ（4） 

---

 知识点速览

在学二叉树之前我们须要作为补充相识树的几个名词概念
树的名词表明

节点的度：一个节点含有子节点的个数。比方A的度：为6
叶节点或终端节点：度为0的节点。比方：B、C、H、P、Q、N都为叶节点
分支节点或非终端节点：度不为0的节点。比方：D、A、G、J都为分支节点
双亲节点或父节点：若一个节点有度（即有子节点），该节点为父节点。比方：A、D、E为父节点
孩子节点或子节点：也就是拥有度的这些节点的下一层节点。比方：B、C、D都为子节点
兄弟节点：拥有雷同父节点的子节点。比方：I、J是兄弟节点，K、L、M是兄弟节点
树的度：孩子节点最多的度。比方：这棵树中孩子节点最多的是A节点，那么这颗树的度为6
节点的条理：从根节点开始从1开始算。比方：J的条理为3，Q的条理为4
树的高度大概深度：树中节点的最大条理。比方：这棵树节点条理最大的是P与Q，树最大条理为4
节点的先人：从根节点到该分支的全部节点。比方：A是全部节点的先人。G不是L的先人
子孙：以某节点为根的子树中的任意节点。比方：全部节点是A的子孙。Q不是D的子孙
森林：由 m （m>0）棵互不相交的多棵树的聚集称为森林
二叉树的四种遍历

这四种遍历着实并不难，下面小编带大家深刻明白这四种遍历！
起首前、中、后三种遍历中的的这三个关键字“前”“中”“后”都是根据根节点而言的，左子树永久在右子树前面，（大家注意观察根节点与遍历方式的位置！）它的遍历都是将一个子树对应位置遍历完之后再遍历又一个子树，明白：每次不停分成差别巨细的树，然后递归到末尾，再原路返回。小编以中序遍历为列，仔细讲解一下！最好的明白方式就是动手画到不堕落为止！
前序遍历：根节点、左子树、右子树
遍历次序：A->B->D->NULL->NULL->E->NULL->NULL->C->NULL->F->NULL->NILL
中序遍历：左子树、根节点、右子树

以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） 
推论：我们无法确定完全二叉树详细的节点个数，只能通过满二叉树进行推理

，别的树亦云云
训练题（1）

套用公式：度为0的节点数（叶子节点）= 度为2的节点数 + 1  ，得到终极答案 200
训练题（2）

这是一棵完全二叉树，它的节点构成是度为0的、度为1的、度为2的总和，也就是：
x0 + x1 + x2 =2n  ，同时套用公式 x0 =  x2 + 1，两个结合得到：2 * x0 + x1 - 1 = 2n
我们观察图，发现完全二叉树度为1的节点只有一个，因此 x1 = 1，那么算出来得到 x0 = n
训练题（3）

我们假设高度为 h ，末了一层缺了 x 个，同时知道满二叉树是特别的完全二叉树
那么满意： 2^h-1  - x = 531.    同时 x 的范围应该在 【0，2 ^ h-1】，x 的范围如下图所示：

直接一个都不缺，为0个

最多缺一个，x为2 ^ h-1个 

结合这两个关系式，去套，末了得出只有当高度为10时满意 （注意这里的层数从0开始）
训练总结

除了直接套用公式的题，假如出现节点总数求某个变量的值，似乎都要去通过创建方程表现节点总数，表现方式一样寻常有两种：（1）差别度的节点数之和（2）通过节点总数满二叉树盘算公式去盘算
二叉树实现

界说结构体

咱们按照二叉树的结构，界说一个左子节点、右子节点、一个数据域就行了，这是最简单的界说

1. //重定义类型
2. typedef int Datatype;
4. typedef struct Tree
5. {
6.         //左孩子节点
7.         struct Tree* left;
8.         //右孩子节点
9.         struct Tree* right;
10.         //数据域
11.         Datatype data;
12. }Tree;

复制代码

初始化

初始化我们开辟一个根节点返回就行了，以后将其作为参数再去毗连左右节点

1. //初始化树
2. Tree* Perliminary(Datatype data)
3. {
4.         //开辟根节点
5.         Tree* newnode = (Tree*)malloc(sizeof(Tree));
6.         //判断有效性
7.         if (newnode == NULL)
8.         {
9.                 printf("节点开辟失败\n");
10.                 return NULL;
11.         }
12.         //初始化指针
13.         newnode->data = data;
14.         newnode->left = NULL;
15.         newnode->right = NULL;
17.         return newnode;
18. }

复制代码

新增节点

起首我们初始化了一个根节点，新增的节点值与根节点的值进行比力
假如小于根节点的值，递归左子树；假如大于根节点的值，递归右子树；
随着递归的不停调用，它的根节点会不停改变，假如为空，就返回新增的节点
末了回到最初的根节点

1. //新增节点
2. Tree* Capacity(Tree* TreeNode, Datatype data)
3. {
4.         //如果是空节点就插入
5.         if (TreeNode == NULL)
6.         {
7.                 return Perliminary(data);
8.         }
9.         //如果是非空节点就继续递归
10.         //较小就插入到左子节点
11.         if (data < TreeNode->data)
12.         {
13.                 TreeNode->left = Capacity(TreeNode->left, data);
14.         }
15.         else
16.                 TreeNode->right = Capacity(TreeNode->right, data);
18.         //回到原初的根节点
19.         return TreeNode;
20. }

复制代码

前序遍历

起首递归到子树的极度，碰到空就开始返回，再调解打印次序

1. //前序遍历
2. Tree* Preorder(Tree* TreeNode)
3. {
4.         if (TreeNode == NULL)
5.         {
6.                 return;
7.         }
8.         //根节点
9.         printf("%d ", TreeNode->data);
10.         //左子树
11.         Preorder(TreeNode->left);
12.         //右子树
13.         Preorder(TreeNode->right);
14. }

复制代码

 中序遍历

1. //中序遍历
2. Tree* Mid(Tree* TreeNode)
3. {
4.         //如果遇到空返回
5.         if (TreeNode == NULL)
6.         {
7.                 return;
8.         }
9.         //左子树
10.         Mid(TreeNode->left);
11.         //根节点
12.         printf("%d ", TreeNode->data);
13.         //右子树
14.         Mid(TreeNode->right);
15. }

复制代码

 后序遍历

1. //后序遍历
2. Tree* Behind(Tree* TreeNode)
3. {
4.         //递归到深处，如果是空就开始返回
5.         if (TreeNode == NULL)
6.         {
7.                 return;
8.         }
9.         //左子树
10.         Behind(TreeNode->left);
11.         //右子树
12.         Behind(TreeNode->right);
13.         //根
14.         printf("%d ", TreeNode->data);
15. }

复制代码

二叉树OJ（1）

   假设如今有如许一棵树

它的中序遍历结果为：D->B->E->A->F->C       后序遍历结果为：D->E->B->F->C->A
按照中序次序，我们去推得到 b 应该在最左边；按照后序次序，我们得到 a 应该是根节点
以是 a 是在根节点，再根据中序次序，得到 a 的左边是 b ，同时 c 是 a 的右子树，如许就能推出

二叉树OJ（2）

题目链接：https://leetcode.cn/problems/binary-tree-preorder-traversal 
题目是要我们将前序遍历的节点结果返回 
头脑讲解：
流程：用一个空间将每次遍历的值存储起来，然后返回
（1）起首我们开辟数组，数组的空间巨细最好是由节点个数决定，因此先遍历二叉树盘算节点

1. return root==NULL? 0 : treesize(root->left) + treesize(root->right) + 1;

复制代码

（2）然后开辟对应巨细的数组空间

1.    //计算节点个数
2.    int size=treesize(root);
3.    //开辟空间
4.    int* arr=(int*)malloc(sizeof(int)*size);

复制代码

（3）接下来就是递归遍历储存节点，但是要思量一个题目，假如在这个函数里面去递归，那么每次调用都要去开辟空间，以是我们选择再开一个来进行递归遍历，参数是根节点、空间指针、计数
注意：计数的 i 应该取所在，由于递归会开辟多个函数，不然每次 i 都只是一次拷贝而已 

1.   //存进空间
2.     int i=0;
3.     preorder_Traversal(root,arr,&i);

复制代码

（4）然后将之前的前序遍历的打印换成储存即可

1. //前序遍历
2.     if(root==NULL)
3.     {
4.         return;
5.     }
7.     arr[*i]=root->val;
8.     ++(*i);
10.     preorder_Traversal(root->left,arr,i);
11.     preorder_Traversal(root->right,arr,i);

复制代码

（5）末了：这是整型指针空间，返回的只是一个元素，以是按照题目要求，另有设置元素个数

1. *returnSize = size;
2.     return arr;

复制代码

二叉树OJ（3）

题目链接：https://leetcode.cn/problems/binary-tree-postorder-traversal 
此题和上面这题险些如出一辙，就作为头脑训练巩固给大家了！记得独立完成哦！ 

二叉树OJ（4） 

题目链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree 

头脑讲解：此题是求二叉树的最大深度，二叉树最大深度就是最大层数

（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。别的节点类推即可

                                                       小编等待与你的下次相遇 ！