树在数据结构中占有非常重要的位置，尤其是二叉树。往往是Java面试中必问的部分，二叉树的应用场景确实很常见，需要掌握。
长期以来java二叉树遍历算法，很多同学并没有全面掌握二叉树。今天我将讨论二叉树。我希望你喜欢这个关于 Java 数据结构和算法的话题。仔细阅读后，你会对二叉树有一个比较完整的了解。
将强调以下几点：
1.什么是二叉树
二叉树：是一种树形结构，每个节点只能有两个子节点，俗称“大裤衩”，具有特殊的形象。
通常子树被称为“左子树”（left）和“右子树”（right）。
你可以在下面的图片中看到它。
2.二叉树遍历方法
2.1 二叉树遍历主要有以下三种：
第一（根）顺序遍历（根左右）
中（根）顺序遍历（左根右）
3） post(root)中序遍历(左右根)
2.2 前序遍历（围绕根）
我将从第一个预购遍历开始。主要遍历顺序如下：
1）先访问根节点
2）然后按前序遍历左子树
3）然后按前序遍历右子树
或者举个例子，遍历下图
如果按前序（根左和右）遍历java二叉树遍历算法，结果将是：
2.3 中序遍历（左根右）
1）中序遍历左子树
2）然后是根节点
3）然后依次遍历右子树
或者举个例子，中序遍历同一个二叉树
中序（左根右）遍历，结果为：
2.4 后序遍历
1） 左子树的后序遍历
2） 右子树的后序遍历
3）然后访问根节点
或者举个例子，同一个二叉树的后序遍历
后序遍历（左右根）会导致：
3.二叉树的类型
基本上包括：
我将从一个完整的二叉树开始。
3.1 个完整的二叉树
1）全二叉树
深度为 k 和 2^k-1 个节点的树是完整的二叉树
2）满二叉树的形式
3）满二叉树的特征
所有内部节点都有两个子节点，最底层是叶子节点。
如果一棵树的深度为h，则最大层级为k，深度与最大层级相同，即k=h；
第k层的节点数为：2^(k-1)
总结点是：2^k-1（2的k次幂减一)
节点总数必须是奇数。
树高：h=log2(n+1)
3.2.完全二叉树
1）完全二叉树
如果二叉树的深度设置为h，除第h层外，其他层的节点数（1～h-1)达到最大数，h中的所有节点-th层不断地集中在最左边，这是一棵完全二叉树。
2）完全二叉树的形式
3）完全二叉树的特征
一棵深度为 k 的完全二叉树至少有 2^(k-1) 个节点，最多有 2^k-1 个节点。
树高 h=log2n + 1
满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
3.3.二叉搜索/搜索/排序树 - BST
1）二叉搜索树
Tree BST（/排序树），又称二叉搜索树、二叉排序树
备注：下面我将二叉查找树统称为二叉查找树，但要知道二叉查找树、二叉查找树、二叉排序树其实是一棵树。
2）二叉搜索树的特征
3）二叉搜索树的优缺点
优点：查找速度快，二叉查找树比普通树查找要快
缺点：平衡问题
多次插入和删除后，二叉搜索树可能会得到如下右侧的结构：
搜索性能已经是线性的。因此，在使用二叉搜索树的时候，要尽量保持上图左图的结构，避免上图右图的结构，也就是所谓的“平衡”问题。
4）二叉搜索树的时间复杂度
时间复杂度
二叉查找树比普通树查找要快，查找、插入、删除的时间复杂度为O(logN)。
缺点
二叉搜索树有一个极端的情况，就是会变成类似线性链表的结构。这时候时间复杂度会变成O(N)。为了解决这种情况，下面我要讲的出现了。二叉平衡树。
注：时间复杂度
3.4.平衡二叉树（AVL树）
1）平衡二叉树
平衡二叉树 平衡二叉搜索树的全称，也叫AVL树，是一种自平衡树。它是从上面的二叉搜索树升级而来的，重点是改善平衡问题。
2）平衡二叉树的特征
3）AVL树是如何解决平衡的
主要是通过左旋和右旋来解决，防止在特殊情况下出现下面的线性结构。
因此，上面的平衡问题通过下图的左旋和右旋来解决。
但是，也有相应的缺点。由于需要保持自身的平衡，在插入和删除节点时【干货】Java数据结构与二叉树的区别，你知道吗？，需要经常轮换节点。
4.结束语
通过上面的介绍，我们已经对二叉树有了一个初步的了解。本文介绍的基础知识希望读者能牢牢掌握，并能在脑海中构建二叉树模型，为后续学习数据结构和算法打下坚实的基础。
原文链接：
文章来源:https://blog.csdn.net/weixin_39648824/article/details/110614342