二叉树是一种树形结构，二叉树可以是空树（没有任何节点）或有一个根结点下面带有零个、一个或两个子树。每个节点下最多有只有左右两个子节点，分别称之为左子节点和右子节点。
二叉树有一个比较重要的特点是，它的子树摘下来，都是一个二叉树，因此二叉树的任何一个子树都可以看作是一颗二叉树。二叉树的节点可以包含数据和指向左右子节点的指针。
下面是一个简单的二叉树图：
keep（深度） 简称K
Tree（树） 简称T
1 ---K = 1
/ \
2 3 ---K = 2
/ \ / \
4 5 6 7 ---K = 3
在这个二叉树中，根结点是1，它的左子节点是2，右子节点是3。在2和3下，又对应有左子节点4、5和6、7，他们节点最多只有2个，因此称为二叉树。
名次解释
- 根：二叉树就像一个倒过来的树，树只有一个跟，二叉树也是一样的。上图可以看出二叉树的根是1。
- 分支节点：树是有枝干的，枝干上长满了树叶，二叉树也是一样的，如果节点上（除了根）有子节点的话，我们称之为分支节点。不难看出，上图中分支节点分别为2、3。
- 叶子结点：当二叉树的节点下没有子节点，我们称之为叶子节点。叶子结点分别是4、5、6、7。
- 边：边我们理解就是上图的连线，上图总共有6条线，为6个边。
- 度：每个节点单独拎出来我们都可以称之为树，我们看每个树下有多少个子树称之为度，如上图，2、3有两个子树，所以度为2，叶子节点4、5、6、7没有子树，所以叶子节点度为0。
公式
-
任意二叉树，他们第N层最大的节点数公式是：2K-1（K>=1），上图深度为3层，所以最大节点数是在第三层，套入公式23-1 = 4，所以上图为例，最大节点数为4。
-
任意二叉树，他们最大的节点数公式是：2k-1（K>=1），上图深度为3层，所以最多的节点套入公式23-1 = 7，所以上图为例，最多的节点数是7。
-
树的总节点数=所有节点的度数+1。
-
度为0的结点（即叶子结点）总是比度为2的结点多一个。
-
具有n个结点的二叉树，其深度至少为[log2n]+1,其中[log2n]+1表示取log2n的整数部分。
-
具有n个结点的完全二叉树的深度为[log2n]+1。
二叉树基本形态总共分为5种，分别是空树、只有一个根节点的二叉树、只有左子树、只有右子树和完全二叉树。
1. 空树
空树
空树，顾名思义就是啥也没有，一个节点也没有
2. 二叉树只有一根节点
只有一个根节点
只有一个根节点，下面不再有任何子节点
3. 只有左子树
只有左子树
一个根节点下面所有的子节点只有一个度，并且子节点只在左边。
4. 只有右子树
只有右子树
一个根节点下面所有的子节点只有一个度，并且子节点只在右边。
5. 左右子树都非空
左右子树都非空
所有节点都有两个度，每个节点下都挂满左右子节点
二叉树还有另外三种特殊形态，分别为斜二叉树、完全二叉树和满二叉树。
1. 斜二叉树
斜二叉树
如图所示，所有节点都倒向了同一边，我们称之为斜二叉树。
2. 完全二叉树
完全二叉树
在树的左边有N层连续，右边到最右边为N-1层，我们称之为完全二叉树。
3. 满二叉树
满二叉树
所有节点都有两个度，每个节点下都挂满左右子节点
二叉树的遍历
1. 前序遍历：遵循根左右的原则，以次访问根节点、左节点、右节点。
访问顺序为：A B D H I E J C F K G
前序遍历
2. 中序遍历：遵循左根右的原则，以次访问左节点、根节点、右节点。
访问顺序为：H D I B E J A F K C G
中序遍历
3. 后序遍历：遵循左右根的原则，以次访问左节点、右节点、根节点。
访问顺序为：H I D J E B K F G C A
后序遍历
二叉树的增删改查
添加
当添加节点是，只需要遵循左小右大的原则往下追加即可。
查找
二叉树查找
当我们要查找4的时候，步骤如下
- 先从根结点开始判断 4 < 10 ，寻找左子树。
- 4 < 5，继续寻找左子树。
- 4 > 3，寻找到右子树，直到找到为止。
修改
使用查找到对应的子树需要修改修改的节点，改变节点的值就可以了。
删除
删除分三种情况
1.删除的是叶子节点，那么直接删除即可。
删除叶子节点
2.删除的节点只有左（右）子树，需要把子左（右）子树继承皆可。
删除只有左（右）子树节点
2.删除的节点有左和右子树，需要把左子树最大值或者右子树最小值继承过来。（这个我们选的是左子树的最大值）
删除的节点有左和右子树
网友评论