满二叉树、完全二叉树、二叉搜索树、平衡二叉树 “存在即合理”为什么需要每种树，本文不再冗余的总结每种树太多性质，就说重点。 二叉树（Binary Tree）主要包括：满二叉树、完全二叉树、二叉搜索树、平衡二叉树 性质太多，定义太复杂，理解树的样子就行。 1、满二叉树
2、完全二叉树
完全二叉树由满二叉树转化而来，也就是将满二叉树从最后一个节点开始删除，一个一个从后往前删除，剩下的就是完全二叉树。 3、二叉搜索树
二叉搜索树（又叫二叉查找树），它是具有下列性质的二叉树：若左子树不空，则左子树上所有结点的值均小于它的根结点的值；若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；左、右子树也分别为二叉搜索树。 总之：二叉搜索树中，左子树都比其根节点小，右子树都比其根节点大，递归定义。 重点来了！二叉搜索树的中序遍历一定是从小到大排序的。比如上图的中序遍历结果：1，3，4，6，7，8，10，13，14 二叉搜索树的搜索性能： 在最好的情况下，二叉搜索树的查找效率比较高，是 O(logn)，其访问性能近似于二分法； 但最差时候会是 O(n)，比如插入的素是有序的，生成的二叉搜索树就是一个链表，树的一条腿特变长，这种情况下，需要遍历全部素才行（见下图 b）。
如果我们可以保证二叉搜索树不出现上面提到的极端情况（插入的素是有序的，导致变成一个链表），就可以保证很高的搜索效率了。 但这在插入有序的素时不太好控制，按二叉排序树的定义，我们无法判断当前的树是否需要调整。 因此就要用到平衡二叉树（AVL ）了。 4、平衡二叉树 平衡二叉树的提出就是为了保证树不至于出现二叉查找树的极端一条腿长现象，尽量保证两条腿平衡。因此它的定义如下： 定义：平衡二叉树要么是一棵空树，要么保证左右子树的高度之差不大于 1，并且子树也必须是一棵平衡二叉树。
平衡二叉树的性能： 平衡二叉树在添加和删除时需要进行复杂的旋转保持整个树的平衡，最终，插入、查找的时间复杂度都是 O(logn)，性能已经相当好了。 著名的红黑树就是一种平衡二叉树！
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/25808.html
