二叉树是度为二的树，二叉树的各节点最多只有两个子节点，且两个子节点有序。
这里介绍几种常见的二叉树类型。
1. 完全二叉树
如果将二叉树的深度设为k，则除去第k层的其他各层(1((k-1 )层) )的节点数达到最大值，并且第k层的所有节点连续集中在最左边的树是完全二叉树。 图：
(照片仅供网友参考，入侵删除) )。
完全二叉树是一种高效的数据结构，但堆是完全二叉树或几乎完全二叉树，使得堆高效的常用排序算法、Dijkstra算法、Prim算法等都必须使用堆进行优化
(以上摘自https://www.Jian Shu.com/p/6a 30657 BF 894 () ) ) ) ) ) ) ) ) )。
2. 满二叉树
二叉树的定义有国内定义和国外(国际)定义两种。
国内定义：在一个二叉树中，当每个层次的节点数达到最大值时，该二叉树将填满二叉树。 图：
国外(国际)定义：如果一棵二叉树的节点是叶的节点，或者有两个子节点，则这样的树将填满二叉树。 (一棵二叉树的每个节点要么是叶节点，要么有两个子节点，但是相反不成立。 因为完全二叉树也满足这个要求，但不是二叉树。 ) :
当然，可以看出国外(国际)的定义已经包括了国内的定义。 也就是说，国内定义是国外定义的子集。
(以上摘录： https://baike.baidu.com/item/二叉树/7773283？ fr=aladdin )
3. 二叉查找树（BST）
二叉搜索树，又称二叉排序树、二叉搜索树。 二叉树是空的树，或者是具有以下性质的二叉树。
在左侧子树不为空的情况下，左侧子树的所有节点的值小于根节点的值； 如果右子树不为空，则右子树中所有节点的值都大于根节点的值。 左、右子树也分别是二叉排序树； 没有键值相等的节点。
4. 平衡二叉树（AVL）
二叉树实际上也是二叉树的搜索树，但与二叉树的搜索树不同。 平衡二叉树包含二叉树的所有特性，但与二叉树不同，平衡二叉树的平衡因子不能超过1。
这意味着它是一棵树，或者左边的子树和右边的子树是平衡的二叉树，并且左边的子树和右边的子树的深度之差的绝对值小于或等于1。
我在网上找了很多关于平衡二叉树的文章，都只阐述了以上原理。 但是，什么是平衡因子？ 以下详细介绍这一点。 图：
因为a树的根节点是节点5，节点5的深度是4，所以a树的深度是4。 计算所有节点的平衡因子。
设节点5、左侧子树的深度为3、右侧子树的深度为2，则节点5的平衡因子为|3-2|=1； 节点2，左侧子树深度为1，右侧子树深度为2，平衡因子为|1-2|=1； 节点6，由于没有左树，左树深度为0，右树深度为1，平衡因子为|0-1|=1； 节点1，因为没有左子树和右子树，所以左右子树的深度都为0，平衡因子为|0-0|=0； 节点4，左部分树深度为1，无右部分树，故右部分树深度为0，平衡因子为|1-0|=1； 节点7，无左子树和右子树，故左右子树深度均为0，平衡因子为|0-0|=0； 节点3，没有左子树和右子树，所以左右子树的深度均为0，平衡因子为|0-0|=0； 通过上述计算，得到的a树所有节点的平衡因子都没有超过1，所以a树是平衡二叉树。 同样计算得到的b树是二叉树，但不是平衡二叉树。
本文主要记录了各种二叉树的类型。 接下来专门写几篇文章。 记录用代码构成各种二叉树的方法。 然后，添加、删除和修改二叉树。 虽然网上有很多类似的文章，但我还是觉得自己试着写，是另一种理解。 我感觉这是一个大项目。 告诉自己，加油~~。
ps :本文从其他地方复制的理论很多，结合自己的理解，可能不是特别完整。 如果有错误的地方，欢迎指出来。 谢谢你~~。
转载于：https://www.cn blogs.com/ghm-777/p/11431270.html