二叉树以及二叉树可以解决的问题
野生代码狗表示完全不理解为什么面试官特别喜欢问二叉树的问题，然后去搜了一下表示可以解决的问题好像还是很多，所以写个东西梳理一下。
先回顾一下大学学过的二叉树，二叉树是树的特殊一种，具有如下特点1.每个节点最多有两颗子树，结点的度最大为2
2.左子树和右子树是有顺序的，次序不能颠倒
3.即使某结点只有一个子树，也要区分左右子树
一 特殊的二叉树及其特点
1。斜树
所有的结点都只有左子树，或者右子树，这就是斜树
image.png
2.满二叉树
所有的分支结点都存在左子树和右子树，并且所有的叶子结点都在同一层上，这样就是满二叉树，关键在于树的平衡
image.png
根据满二叉树的定义，得到其特点为:
(1).叶子结点只能出现在最下一层
(2).非叶子结点度一定是2（度是一个结点有几个孩子）
(3).在同样深度的二叉树中，满二叉树的结点个数最多，叶子树最多
3.完全二叉树
对于一颗具有n个结点的二叉树按层序排号，如果编号为i的结点与同样深度的满二叉树编号为i结点在二叉树中位置完全相同，就是完全二叉树，满二叉树一定是完全二叉树，反之不一定
image.png
根据完全二叉树定义得到其特点
1）.叶子结点只能出现在最下一层
2）最下层叶子结点一定集中在左部连续位置
3)倒数第二层，如有叶子结点，一定出现在右部连续位置
4）同样结点树的二叉树，完全二叉树的深度最小
image.png
三。二叉树的性质
1.一般二叉树的性质
1、在非空二叉树的i层上，至多有2i-1个节点(i>=1)。通过归纳法论证。
2、在深度为K的二叉树上最多有2k-1个结点（k>=1)。通过归纳法论证。
3、对于任何一棵非空的二叉树,如果叶节点个数为n0，度数为2的节点个数为n2，则有: n0 = n2 + 1
在一棵二叉树中，除了叶子结点（度为0）之外，就剩下度为2(n2)和1(n1)的结点了。则树的结点总数为T = n0+n1+n2;在二叉树中结点总数为T，而连线数为T-1.所以有：n0+n1+n2-1 = 2*n2 +n1;最后得到n0 = n2+1;
image.png
- 完全二叉树性质
四. 二叉树遍历
二叉树遍历：从树的根结点出发，按照某种次序依次访问二叉树中所有的结点，使得每个结点被访问近且一次。
1.前序遍历
根左右
image.png
2.中序遍历
左根右
image.png
-
后续遍历
左右根
image.png
五。二叉树的建立
其实二叉树的建立就是二叉树的遍历，只不过将输入内容改为建立结点而已，比如，利用前序遍历建立二叉树
六。 遍历的python代码
七。解决的问题
简单问了下男朋友，太多了。。。。回家查资料去
