完全二叉树 最全二叉树：完整详解二叉树的遍历以及完全二叉树等6种二叉树
文章图片
Java高薪高级一号站
树在数据结构中占有非常重要的地位，尤其是二叉树。往往是java面试中必不可少的环节，二叉树的应用场景真的很常见，需要把握好。
但是长期以来，很多学生并没有完全掌握二叉树。今天我就来说说二叉树。希望大家喜欢Java数据结构与算法这个话题。仔细阅读后，你会对二叉树有一个完整的理解。
重点将放在以下几点:
二叉树
二叉树的遍历方式
有哪些种类的二叉树
完全二叉树
完全二叉树
二叉查找树
平衡二叉树(AVL)
左手和右手
【完全二叉树 最全二叉树：完整详解二叉树的遍历以及完全二叉树等6种二叉树】1.什么是二叉树
二叉树:是每个节点只能有两个子节点的树形结构，俗称“大裤衩”，形象特殊。
通常，子树被称为“左子树”和“右子树”。
下图一目了然。
2.二叉树的遍历方式
2.1二叉树的遍历主要有三种类型:
1)第一(根)顺序遍历
2)中(根)序遍历
3)后(根)遍历
2.2优先遍历
我将从第一次顺序遍历开始。主要遍历顺序如下:
1)首先访问根节点
2)然后依次遍历左边的子树
3)然后顺序遍历右子树
或者作为示例，首先遍历下图
如果按顺序遍历，结果将是:ABDFECGHI
2.3顺序遍历
1)首先以中间顺序遍历左边的子树
2)然后是根节点
3)然后以中间顺序遍历右子树
或者举个例子，中间顺序遍历同一个二叉树
按照中间顺序，结果是:DBEFAGHCI
2.4序列后遍历
1)依次遍历左边的子树
2)依次遍历右子树
3)然后访问根节点
或者，例如，按顺序遍历同一个二叉树
按照下面的顺序，遍历结果是:DEFBHGICA
3.二叉树的类型
基本包括:
完全二叉树
完全二叉树
二叉查找树
平衡AVL树
红色和黑色的树也属于AVL树
先说完整的二叉树。
3.1全二叉树
1)全二叉树
深度为k和2 k-1个节点的树是完全二叉树
2)全二叉树的形式
3)全二叉树的特征
所有内部节点都有两个子节点，底层是叶节点。
如果一棵树的深度为h，最大层数为k，深度与最大层数相同，即k = h；
第k层中的节点数是2 (k-1)
总点数是:2^k-1 (2 2 k减1)
节点总数必须是奇数。
树高:h=log2(n+1)
3.2.完全二叉树
1)完全二叉树
如果二叉树的深度为h，则除第h层外的所有层(1 ~ h-1)的节点数都达到最大，第h层的所有节点都连续集中在最左侧，这就是一棵完整的二叉树。
2)完全二叉树的形式
3)完全二叉树的特征
深度为k的完全二叉树至少有2个(k-1)节点，最多有2个k-1节点。
树高h=log2n+1
完全二叉树一定是完全二叉树，完全二叉树不一定是完全二叉树
3.3.二分搜索法/搜索/分类树
1)二叉查找树
二叉查找树BST，又名二叉查找树，二元排序树
注意:我会叫它二叉查找树，但是你应该知道二叉查找树，二叉查找树和二进制排序树实际上是同一棵树。
2)二叉查找树的特点
左子树中所有节点的值都小于或等于其根节点的值
右子树中所有节点的值都大于或等于其根节点的值
3)二叉查找树的优势和劣势
优点:搜索速度快，二叉查找树比普通树快
缺点:存在平衡问题
经过多次插入和删除后，二叉查找树可能会导致右边出现以下结构:
搜索性能已经是线性的。所以在使用二叉查找树的时候，要尽量保持左上图的结构，避免右上图的结构，也就是所谓的“平衡”问题。
推荐阅读
- 嫁对人和嫁错人，是完全不同的两种人生
- 如何让你的桃树不流胶或少流胶？看这里
- 星鸦会像松鼠一样储存冬粮吗？生长在汪清保护地的东北豹会经常上树活动吗？
- 夜读丨村上春树：大智若猫
- 林草日历?｜北京乡土树种：栾树、酸枣、拐枣
- 「新春走基层」和村民一起上果树修剪课
- 果树：有收无收在于水，收多收少在于肥
- 湘潭县:茶树下的“动物园” 生态成就靓生活
- 河南一老鼠为躲避猫追击爬上树梢，目击者：猫捕鼠不成急得喵喵叫
- 泰康之家·粤园树立大湾区高品质享老“五美”新典范